Network Traffic Signal Control with Nonconvex Alternating Direction Method of Multipliers Formulations
Abstract
This paper considers the distributed solution of the online network traffic signal control problem. Toward systemwide optimality, the problem is modeled as a large-scale mixed-integer linear program with the traffic dynamics captured by the cell transmission model. The alternating direction method of multipliers (ADMM) is used to achieve spatial problem decomposition and to design an iterative approach that achieves networkwide solution under a fully distributed architecture, where computation, communication, and control are performed locally at individual intersections. Two ADMM-based algorithms were developed on the basis of appropriate problem reformulations; these algorithms resulted in the solution of convex–nonconvex subproblems with distinct properties. The performance of the algorithms was demonstrated to be close to global optimality and comparative to that of genetic algorithms. Each algorithm offers a different trade-off between communication and computation complexity.
Get full access to this article
View all access and purchase options for this article.
References
1. Binning J., Burtenshaw G., and Crabtree M. TRANSYT 13 User Guide. Transportation Research Laboratory, Crowthorne, Berkshire, United Kingdom, 2009.
2. Lin W.-H., and Wang C. An Enhanced 0–1 Mixed-Integer LP Formulation for Traffic Signal Control. IEEE Transactions on Intelligent Transportation Systems, Vol. 5, No. 4, 2004, pp. 238–245.
3. Beard C., and Ziliaskopoulos A. System Optimal Signal Optimization Formulation. In Transportation Research Record: Journal of the Transportation Research Board, No. 1978, Transportation Research Board of the National Academies, Washington, D.C., 2006, pp. 102–112.
4. Ceylan H., and Bell M. G. Traffic Signal Timing Optimisation Based on Genetic Algorithm Approach, Including Drivers Routing. Transportation Research Part B: Methodological, Vol. 38, No. 4, 2004, pp. 329–342.
5. He Q., Lin W.-H., Liu H., and Head K. Heuristic Algorithms to Solve 0–1 Mixed Integer LP Formulations for Traffic Signal Control Problems. Proc., 2010 IEEE International Conference on Service Operations and Logistics and Informatics (SOLI), Qing Dao, China, IEEE, New York 2010, pp. 118–124.
6. Robertson D., and Bretherton R. Optimizing Networks of Traffic Signals in Real Time—The SCOOT method. IEEE Transactions on Vehicular Technology, Vol. 40, No. 1, 1991, pp. 11–15.
7. Mirchandani P., and Head L. A Real-Time Traffic Signal Control System: Architecture, Algorithms, and Analysis. Transportation Research Part C: Emerging Technologies, Vol. 9, No. 6, 2001, pp. 415–432.
8. Sims A. G., and Dobinson K. The Sydney Coordinated Adaptive Traffic (SCAT) System Philosophy and Benefits. IEEE Transactions on Vehicular Technology, Vol. 29, No. 2, 1980, pp. 130–137.
9. Aboudolas K., Papageorgiou M., Kouvelas A., and Kosmatopoulos E. A Rolling-Horizon Quadratic-Programming Approach to the Signal Control Problem in Large-Scale Congested Urban Road Networks. Transportation Research Part C: Emerging Technologies, Vol. 18, No. 5, 2010, pp. 680–694.
10. Lin S., De Schutter B., Xi Y., and Hellendoorn H. Fast Model Predictive Control for Urban Road Networks via MILP. IEEE Transactions on Intelligent Transportation Systems, Vol. 12, No. 3, 2011, pp. 846–856.
11. Diakaki C., Papageorgiou M., and Aboudolas K. A Multivariable Regulator Approach to Traffic-Responsive Network-Wide Signal Control. Control Engineering Practice, Vol. 10, No. 2, 2002, pp. 183–195.
12. Daganzo C. F. Urban Gridlock: Macroscopic Modeling and Mitigation Approaches. Transportation Research Part B: Methodological, Vol. 41, No. 1, 2007, pp. 49–62.
13. Geroliminis N., and Daganzo C. F. Existence of Urban-Scale Macroscopic Fundamental Diagrams: Some Experimental Findings. Transportation Research Part B: Methodological, Vol. 42, No. 9, 2008, pp. 759–770.
14. Keyvan-Ekbatani M., Kouvelas A., Papamichail I., and Papageorgiou M. Exploiting the Fundamental Diagram of Urban Networks for Feedback-Based Gating. Transportation Research Part B: Methodological, Vol. 46, No. 10, 2012, pp. 1393–1403.
15. Haddad J., and Geroliminis N. On the Stability of Traffic Perimeter Control in Two-Region Urban Cities. Transportation Research Part B: Methodological, Vol. 46, No. 9, 2012, pp. 1159–1176.
16. Keyvan-Ekbatani M., Yildirimoglu M., Geroliminis N., and Papageorgiou M. Traffic Signal Perimeter Control with Multiple Boundaries for Large Urban Networks. Proc., 16th International IEEE Conference on Intelligent Transportation Systems (ITSC), The Hague, Netherlands, 2013, pp. 1004–1009.
17. Aboudolas K., and Geroliminis N. Perimeter and Boundary Flow Control in Multi-Reservoir Heterogeneous Networks. Transportation Research Part B: Methodological, Vol. 55, 2013, pp. 265–281.
18. Haddad J., Ramezani M., and Geroliminis N. Cooperative Traffic Control of a Mixed Network with Two Urban Regions and a Freeway. Transportation Research Part B: Methodological, Vol. 54, 2013, pp. 17–36.
19. Keyvan-Ekbatani M., Papageorgiou M., and Papamichail I. Urban Congestion Gating Control Based on Reduced Operational Network Fundamental Diagrams. Transportation Research Part C: Emerging Technologies, Vol. 33, 2013b, pp. 74–87.
20. Wiering M., van Veenen J., Vreeken J., and Koopman A. Intelligent Traffic Light Control. Technical Report UU-CS-2004-029. Information and Computing Sciences, Utrecht University, Netherlands, 2004.
21. Vasirani M., and Ossowski S. A Computational Market for Distributed Control of Urban Road Traffic Systems. IEEE Transactions on Intelligent Transportation Systems, Vol. 12, No. 2, 2011, pp. 313–321.
22. Wongpiromsarn T., Uthaicharoenpong T., Wang Y., Frazzoli E., and Wang D. Distributed Traffic Signal Control for Maximum Network Throughput. Proc., 15th IEEE International Conference on Intelligent Transportation Systems, Anchorage, Alaska, IEEE, New York, 2012, pp. 588–595.
23. Boyd S., Parikh N., Chu E., Peleato B., and Eckstein J. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. Foundations and Trends in Machine Learning, Vol. 3, No. 1, 2011, pp. 1–122.
24. Daganzo C. F. The Cell Transmission Model: A Dynamic Representation of Highway Traffic Consistent with the Hydrodynamic Theory. Transportation Research Part B: Methodological, Vol. 28, No. 4, 1994, pp. 269–287.
25. Timotheou S., Panayiotou C. G., and Polycarpou M. M. Towards Distributed Online Cooperative Traffic Signal Control Using the Cell Transmission Model. Proc., 16th International IEEE Conference on Intelligent Transportation Systems, The Hague, Netherlands, IEEE, New York, 2013, pp. 1737–1742.
26. Timotheou S., Panayiotou C. G., and Polycarpou M. M. Distributed Traffic Signal Control Using the Cell Transmission Model via the Alternating Direction Method of Multipliers. IEEE Transactions on Intelligent Transportation Systems, Vol. 16, No. 2, 2014, pp. 919–933.
27. Gurobi Optimizer Reference Manual. Gurobi Optimization, Inc., Houston, Tex., 2013.
Cite article
Cite article
Cite article
OR
Download to reference manager
If you have citation software installed, you can download article citation data to the citation manager of your choice
Information, rights and permissions
Information
Published In
Article first published online: January 1, 2015
Issue published: January 2015
Authors
Metrics and citations
Metrics
Journals metrics
This article was published in Transportation Research Record: Journal of the Transportation Research Board.
VIEW ALL JOURNAL METRICSArticle usage*
Total views and downloads: 50
*Article usage tracking started in December 2016
Altmetric
See the impact this article is making through the number of times it’s been read, and the Altmetric Score.
Learn more about the Altmetric Scores
Articles citing this one
Receive email alerts when this article is cited
Web of Science: 0
Crossref: 0
There are no citing articles to show.
Figures and tables
Figures & Media
Tables
View Options
Get access
Access options
If you have access to journal content via a personal subscription, university, library, employer or society, select from the options below:
loading institutional access options
Alternatively, view purchase options below:
Purchase 24 hour online access to view and download content.
Access journal content via a DeepDyve subscription or find out more about this option.
