Graph-Based Metaheuristic Optimization for Real-Time Urban Traffic Signal Coordination

Authors

  • Hassan Boussouf * Department of Computer Science, Faculty of Mathematics and Computer Science, University of Algiers 1, Algiers, Algeria.
  • Nguyen Minh Duc Department of Information Technology, Vietnam National University, Hanoi, Vietnam.

https://doi.org/10.48313/maa.v1i3.99

Abstract

Urban traffic congestion remains one of the most pressing challenges confronting smart city development worldwide, imposing substantial economic costs, environmental degradation, and diminished quality of life for urban residents. Existing traffic signal control paradigms including fixed-time plans, actuated controllers, and adaptive systems such as Split Cycle Offset Optimisation Technique (SCOOT) and Sydney Coordinated Adaptive Traffic System (SCATS) exhibit significant limitations in network-wide coordination under dynamically varying demand conditions. More recently, Reinforcement Learning (RL)-based approaches have demonstrated promise at isolated intersections but face persistent challenges in scalability, sample efficiency, transferability, and real-time multi-intersection coordination. This paper presents Graph-Based Metaheuristic For Traffic Signal Coordination (GRAPH-TSC), a novel algorithm that models the urban traffic network as a directed graph and employs a graph-aware Ant Colony Optimization (ACO) variant hybridized with local search to jointly optimize cycle lengths, green splits, and offsets across all intersections in real time. GRAPH-TSC introduces four key innovations: 1) a Graph Attention Network (GAT)-based surrogate model that replaces computationally expensive microsimulation for rapid fitness evaluation during optimization, 2) a pheromone diffusion mechanism that propagates pheromone updates along the traffic graph in proportion to inter-intersection traffic flow dependencies, naturally encoding green wave coordination, 3) a hierarchical network decomposition strategy that partitions large networks into overlapping subnetworks for scalable optimization with boundary coordination via shared pheromone, and 4) an adaptive re-optimization trigger based on Cumulative Sum (CUSUM) change detection that initiates re-optimization only upon detected traffic pattern shifts. GRAPH-TSC was evaluated on SUMO-simulated networks modeled after real urban areas in Algiers, Algeria (42 intersections) and Hanoi, Vietnam (67 intersections), as well as synthetic grid networks of up to 100 intersections. Experimental results demonstrate that GRAPH-TSC achieves an 18–27% reduction in average vehicle delay, a 14–22% improvement in network throughput, and an 11–19% reduction in CO2 emissions compared to Webster’s fixed-time, SCATS-like adaptive, standard ACO, Genetic Algorithm (GA), and Deep Q-Network (DQN)-based methods. Re-optimization is completed within 3 seconds for the 67-intersection Hanoi network, confirming the algorithm’s real-time applicability for operational deployment in smart city traffic management systems.

Keywords:

Traffic signal coordination, Metaheuristic optimization, Ant colony optimization, Graph neural network, Smart cities, Urban traffic management, Real-time optimization

References

  1. [1] Schrank, D., Eisele, B., & Lomax, T. (2021). 2021 urban mobility report. https://static.tti.tamu.edu/tti.tamu.edu/documents/umr/archive/mobility-report-2021.pdf
  2. [2] Cervero, R. (2013). Linking urban transport and land use in developing countries. Journal of transport and land use, 6(1), 7–24. https://www.jstor.org/stable/26202644
  3. [3] Nguyen, H. D. (2016). Saturation flow rate analysis at signalized intersections for mixed traffic conditions in motorcycle dependent cities. Transportation research procedia, 15, 694–708. https://doi.org/10.1016/j.trpro.2016.06.058
  4. [4] Federal Highway Administration (FHWA). (2008). Traffic signal timing manual. https://ops.fhwa.dot.gov/publications/fhwahop08024/fhwa_hop_08_024.pdf
  5. [5] Hunt, P. B., Robertson, D. I., Bretherton, R. D., & Royle, M. C. (1982). The SCOOT on-line traffic signal optimisation technique. Traffic engineering & control, 23(4), 190-192. http://worldcat.org/issn/00410683
  6. [6] Lowrie, P. R. (1990). Scats, sydney co-ordinated adaptive traffic system: A traffic responsive method of controlling urban traffic. https://trid.trb.org/View/488852
  7. [7] Stevanovic, A. (2010). Adaptive traffic control systems: Domestic and foreign state of practice. Transportation Research Board (TRB), National Academies. https://nap.nationalacademies.org/catalog/14364
  8. [8] Head, K. L., Mirchandani, P. B., & Sheppard, D. (1992). Hierarchical framework for real-time traffic control. Transportation research record, 1360, 82–88. https://onlinepubs.trb.org/Onlinepubs/trr/1992/1360/1360-014.pdf
  9. [9] Li, L., Lv, Y., & Wang, F. Y. (2016). Traffic signal timing via deep reinforcement learning. IEEE/CAA journal of automatica sinica, 3(3), 247–254. https://doi.org/10.1109/JAS.2016.7508798
  10. [10] El-Tantawy, S., Abdulhai, B., & Abdelgawad, H. (2013). Multiagent reinforcement learning for integrated network of adaptive traffic signal controllers (MARLIN-ATSC): Methodology and large-scale application on downtown Toronto. IEEE transactions on intelligent transportation systems, 14(3), 1140–1150. https://doi.org/10.1109/TITS.2013.2255286
  11. [11] Chu, T., Wang, J., Codecà, L., & Li, Z. (2019). Multi-agent deep reinforcement learning for large-scale traffic signal control. IEEE transactions on intelligent transportation systems, 21(3), 1086–1095. https://doi.org/10.1109/TITS.2019.2901791
  12. [12] Wei, H., Xu, N., Zhang, H., Zheng, G., Zang, X., Chen, C., ... & Li, Z. (2019). Colight: Learning network-level cooperation for traffic signal control. Proceedings of the 28th ACM international conference on information and knowledge management (pp. 1913-1922). Association for Computing Machinery (ACM). https://doi.org/10.1145/3357384.3357902
  13. [13] Wei, H., Chen, C., Zheng, G., Wu, K., Gayah, V., Xu, K., & Li, Z. (2019). Presslight: Learning max pressure control to coordinate traffic signals in arterial network. Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining (pp. 1290-1298). Association for Computing Machinery (ACM). https://doi.org/10.1145/3292500.3330949
  14. [14] Oroojlooy, A., Nazari, M., Hajinezhad, D., & Silva, J. (2020). Attendlight: Universal attention-based reinforcement learning model for traffic signal control. Advances in neural information processing systems, 33, 4079–4090. https://proceedings.neurips.cc/paper/2020/file/29e48b79ae6fc68e9b6480b677453586-Paper.pdf
  15. [15] Lu, J., Ruan, J., Jiang, H., Li, Z., Mao, H., & Zhao, R. (2023). Dualight: Enhancing traffic signal control by leveraging scenario-specific and scenario-shared knowledge. https://doi.org/10.48550/arXiv.2312.14532
  16. [16] Noaeen, M., Naik, A., Goodman, L., Crebo, J., Abrar, T., Abad, Z. S. H., ... & Far, B. (2022). Reinforcement learning in urban network traffic signal control: A systematic literature review. Expert systems with applications, 199, 116830. https://doi.org/10.1016/j.eswa.2022.116830
  17. [17] Ceylan, H., & Bell, M. G. H. (2004). Traffic signal timing optimisation based on genetic algorithm approach, including drivers’ routing. Transportation research part b: Methodological, 38(4), 329–342. https://doi.org/10.1016/S0191-2615(03)00015-8
  18. [18] Park, B., Messer, C. J., & Urbanik, T. (2000). Enhanced genetic algorithm for signal-timing optimization of oversaturated intersections. Transportation research record, 1727(1), 32-41. https://doi.org/10.3141/1727-05
  19. [19] Garcia-Nieto, J., Olivera, A. C., & Alba, E. (2013). Optimal cycle program of traffic lights with particle swarm optimization. IEEE transactions on evolutionary computation, 17(6), 823–839. https://doi.org/10.1109/TEVC.2013.2260755
  20. [20] Dorigo, M. (2007). Ant colony optimization. Scholarpedia, 2(3), 1461. http://dx.doi.org/10.4249/scholarpedia.1461
  21. [21] D’Acierno, L., Gallo, M., & Montella, B. (2012). An ant colony optimisation algorithm for solving the asymmetric traffic assignment problem. European journal of operational research, 217(2), 459–469. https://doi.org/10.1016/j.ejor.2011.09.035
  22. [22] Osorio, C., & Bierlaire, M. (2013). A simulation-based optimization framework for urban transportation problems. Operations research, 61(6), 1333–1345. https://doi.org/10.1287/opre.2013.1226
  23. [23] Kipf, T. N., & Welling, M. (2016). Semi-supervised classification with graph convolutional networks. https://doi.org/10.48550/arXiv.1609.02907
  24. [24] Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., & Bengio, Y. (2017). Graph attention networks. https://doi.org/10.48550/arXiv.1710.10903
  25. [25] Li, Y., Yu, R., Shahabi, C., & Liu, Y. (2017). Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. https://doi.org/10.48550/arXiv.1707.01926
  26. [26] Yu, B., Yin, H., & Zhu, Z. (2017). Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. https://doi.org/10.48550/arXiv.1709.04875
  27. [27] Manual, H. C. (2000). Highway capacity manual. Washington, Dc, 2(1), 1. https://onlinepubs.trb.org/Onlinepubs/trnews/trnews193-004.pdf
  28. [28] Little, J. D. C. (1966). The synchronization of traffic signals by mixed-integer linear programming. Operations research, 14(4), 568–594. https://doi.org/10.1287/opre.14.4.568
  29. [29] Gartner, N. H., Assman, S. F., Lasaga, F., & Hou, D. L. (1991). A multi-band approach to arterial traffic signal optimization. Transportation research part b: Methodological, 25(1), 55–74. https://doi.org/10.1016/0191-2615(91)90013-9
  30. [30] Zhang, L., Song, Z., Tang, X., & Wang, D. (2016). Signal coordination models for long arterials and grid networks. Transportation research part c: Emerging technologies, 71, 215–230. https://doi.org/10.1016/j.trc.2016.07.015
  31. [31] TS, N. S. P. (2003). NEMA standards publication TS 2-2003: Traffic controller assemblies with NTCIP requirements. National Electrical Manufacturers Association (NEMA). https://www.nema.org/docs/default-source/standards-document-library/nema-ts-2-amendment-3-watermarked.pdf
  32. [32] Aboudolas, K., Papageorgiou, M., & Kosmatopoulos, E. (2009). Store-and-forward based methods for the signal control problem in large-scale congested urban road networks. Transportation research part c: Emerging technologies, 17(2), 163–174. https://doi.org/10.1016/j.trc.2008.10.002
  33. [33] Lin, S., De Schutter, B., Xi, Y., & Hellendoorn, H. (2012). Efficient network-wide model-based predictive control for urban traffic networks. Transportation research part c, 24, 122–140. https://doi.org/10.1016/j.trc.2012.02.003
  34. [34] Varaiya, P. (2013). Max pressure control of a network of signalized intersections. Transportation research part c: Emerging technologies, 36, 177–195. https://doi.org/10.1016/j.trc.2013.08.014
  35. [35] Zheng, G., Xiong, Y., Zang, X., Feng, J., Wei, H., Zhang, H., ... & Li, Z. (2019). Learning phase competition for traffic signal control. Proceedings of the 28th ACM international conference on information and knowledge management (pp. 1963-1972). Association for Computing Machinery (ACM). https://doi.org/10.1145/3357384.3357900
  36. [36] Foy, M. D., Benekohal, R. F., & Goldberg, D. E. (1992). Signal timing determination using genetic algorithms. Transportation research record, (1365), 108. http://onlinepubs.trb.org/Onlinepubs/trr/1992/1365/1365-011.pdf
  37. [37] Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation, 6(2), 182–197. https://doi.org/10.1109/4235.996017
  38. [38] Jia, H., Lin, Y., Luo, Q., Li, Y., & Miao, H. (2019). Multi-objective optimization of urban road intersection signal timing based on particle swarm optimization algorithm. Advances in mechanical engineering, 11(4), 1687814019842498. https://doi.org/10.1177/1687814019842498
  39. [39] Khamis, M. A., & Gomaa, W. (2014). Adaptive multi-objective reinforcement learning with hybrid exploration for traffic signal control based on cooperative multi-agent framework. Engineering applications of artificial intelligence, 29, 134–151. https://doi.org/10.1016/j.engappai.2014.01.007
  40. [40] Wu, Z., Pan, S., Long, G., Jiang, J., & Zhang, C. (2019). Graph wavenet for deep spatial-temporal graph modeling. https://doi.org/10.48550/arXiv.1906.00121
  41. [41] Zheng, C., Fan, X., Wang, C., & Qi, J. (2020). Gman: A graph multi-attention network for traffic prediction. Proceedings of the AAAI conference on artificial intelligence (Vol. 34, No. 01, pp. 1234-1241). Association for the Advancement of Artificial Intelligence (AAAI). https://doi.org/10.1609/aaai.v34i01.5477
  42. [42] Liang, X., Du, X., Wang, G., & Han, Z. (2019). A deep reinforcement learning network for traffic light cycle control. IEEE transactions on vehicular technology, 68(2), 1243–1253. https://doi.org/10.1109/TVT.2018.2890726
  43. [43] Narayanan, S., Makarov, N., & Antoniou, C. (2024). Graph neural networks as strategic transport modelling alternative - A proof of concept for a surrogate. IET intelligent transport systems, 18(11), 2059–2077. https://doi.org/10.1049/itr2.12551
  44. [44] Lopez, P. A., Behrisch, M., Bieker-Walz, L., Erdmann, J., Flötteröd, Y. P., Hilbrich, R., ... & Wießner, E. (2018). Microscopic traffic simulation using sumo. 2018 21st international conference on intelligent transportation systems (ITSC) (pp. 2575-2582). IEEE. https://doi.org/10.1109/ITSC.2018.8569938
  45. [45] Kingma, D. P., & Ba, J. (2014). Adam: A method for stochastic optimization. https://doi.org/10.48550/arXiv.1412.6980
  46. [46] Nelder, J. A., & Mead, R. (1965). A simplex method for function minimization. The computer journal, 7(4), 308–313. https://doi.org/10.1093/comjnl/7.4.308

Published

2024-09-18

Issue

Vol. 1 No. 3 (1): Metaheuristic Algorithms with Applications (MAA)

Section

Articles

How to Cite

Boussouf, H. ., & Minh Duc, N. . (2024). Graph-Based Metaheuristic Optimization for Real-Time Urban Traffic Signal Coordination. Metaheuristic Algorithms With Applications, 1(3), 227-248. https://doi.org/10.48313/maa.v1i3.99

Similar Articles

21-30 of 59

You may also start an advanced similarity search for this article.