Е-Публикации
Технически университет - София

Abstract: This paper presents a comparative analysis between classical maximum flow algorithms and modern deep Reinforcement Learning (RL) algorithms applied to traffic optimization in urban environments. Through SUMO simulations and statistical tests, algorithms such as Ford–Fulkerson, Edmonds–Karp, Dinitz, Preflow–Push, Boykov–Kolmogorov and Double (Formula presented.) are compared. Their efficiency and stability are evaluated in terms of metrics such as cumulative vehicle dispersion and the ratio of waiting time to vehicle number. The results show that classical algorithms such as Edmonds–Karp and Dinitz perform stably under deterministic conditions, while Double (Formula presented.) suffers from high variation. Recommendations are made regarding the selection of an appropriate algorithm based on the characteristics of the environment, and opportunities for improvement using DRL techniques such as PPO and A2C are indicated.

References

1. Zhang L. Li J. Zhu Y. Shi H. Hwang K.S. Multi-Agent Reinforcement Learning by the Actor-Critic Model with an Attention Interface Neurocomputing 2022 471 275 284 10.1016/j.neucom.2021.06.049
2. Song X.B. Zhou B. Ma D. Cooperative Traffic Signal Control through a Counterfactual Multi-Agent Deep Actor Critic Approach Transp. Res. Part. C Emerg. Technol. 2024 160 104528 10.1016/j.trc.2024.104528
3. Mao F. Li Z. Lin Y. Li L. Mastering Arterial Traffic Signal Control With Multi-Agent Attention-Based Soft Actor-Critic Model IEEE Trans. Intell. Transp. Syst. 2023 24 3129 3144 10.1109/TITS.2022.3229477
4. Yoon J. Kim S. Byon Y.J. Yeo H. Design of Reinforcement Learning for Perimeter Control Using Network Transmission Model Based Macroscopic Traffic Simulation PLoS ONE 2020 15 e0236655 10.1371/journal.pone.0236655 32730334
5. Chen C. Wei H. Xu N. Zheng G. Yang M. Xiong Y. Xu K. Li Z. Toward a Thousand Lights: Decentralized Deep Reinforcement Learning for Large-Scale Traffic Signal Control Proceedings of the AAAI 2020—34th AAAI Conference on Artificial Intelligence New York, NY, USA 7–12 February 2020 10.1609/aaai.v34i04.5744
6. Hou L. Huang D. Cao J. Ma J. Multi-Agent Deep Reinforcement Learning with Traffic Flow for Traffic Signal Control J. Control Decis. 2023 12 81 92 10.1080/23307706.2023.2195408
7. Fang J. You Y. Xu M. Wang J. Cai S. Multi-Objective Traffic Signal Control Using Network-Wide Agent Coordinated Reinforcement Learning Expert. Syst. Appl. 2023 229 120535 10.1016/j.eswa.2023.120535
8. Tan T. Bao F. Deng Y. Jin A. Dai Q. Wang J. Cooperative Deep Reinforcement Learning for Large-Scale Traffic Grid Signal Control IEEE Trans. Cybern. 2020 50 2687 2700 10.1109/TCYB.2019.2904742
9. Chu T. Wang J. Codeca L. Li Z. Multi-Agent Deep Reinforcement Learning for Large-Scale Traffic Signal Control IEEE Trans. Intell. Transp. Syst. 2020 21 1086 1095 10.1109/TITS.2019.2901791
10. Skuba M. Janota A. Kuchár P. Malobický B. Deep Reinforcement Learning for Traffic Signal Control Transportation Research Procedia Elsevier Amsterdam, The Netherlands 2023 Volume 74 10.1016/j.trpro.2023.11.230
11. Huang H. Hu Z. Lu Z. Wen X. Network-Scale Traffic Signal Control via Multiagent Reinforcement Learning with Deep Spatiotemporal Attentive Network IEEE Trans. Cybern. 2023 53 262 274 10.1109/TCYB.2021.3087228
12. Li Z. Yu H. Zhang G. Dong S. Xu C.Z. Network-Wide Traffic Signal Control Optimization Using a Multi-Agent Deep Reinforcement Learning Transp. Res. Part. C Emerg. Technol. 2021 125 103059 10.1016/j.trc.2021.103059
13. Ha P. Chen S. Du R. Labi S. Scalable Traffic Signal Controls Using Fog-Cloud Based Multiagent Reinforcement Learning Computers 2022 11 38 10.3390/computers11030038
14. Song J. Jin Z. Zhu W.J. Implementing Traffic Signal Optimal Control by Multiagent Reinforcement Learning Proceedings of the 2011 International Conference on Computer Science and Network Technology, ICCSNT 2011 Harbin, China 24–26 December 2011 Volume 4 10.1109/ICCSNT.2011.6182495
15. Higuera C. Lozano F. Camacho E.C. Higuera C.H. Demonstration of Multiagent Reinforcement Learning Applied to Traffic Light Signal Control Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Springer Berlin/Heidelberg, Germany 2019 Volume 11523 10.1007/978-3-030-24209-1_25
16. Abdoos M. Fuzzy Graph and Collective Multiagent Reinforcement Learning for Traffic Signals Control IEEE Intell. Syst. 2021 36 48 55 10.1109/MIS.2020.3000180
17. Michailidis P. Michailidis I. Lazaridis C.R. Kosmatopoulos E. Traffic Signal Control via Reinforcement Learning: A Review on Applications and Innovations Infrastructures 2025 10 114 10.3390/infrastructures10050114
18. Skoropad V.N. Deđanski S. Pantović V. Injac Z. Vujičić S. Jovanović-Milenković M. Jevtić B. Lukić-Vujadinović V. Vidojević D. Bodolo I. Dynamic Traffic Flow Optimization Using Reinforcement Learning and Predictive Analytics: A Sustainable Approach to Improving Urban Mobility in the City of Belgrade Sustainability 2025 17 3383 10.3390/su17083383
19. Khanmohamadi M. Guerrieri M. Smart Intersections and Connected Autonomous Vehicles for Sustainable Smart Cities: A Brief Review Sustainability 2025 17 3254 10.3390/su17073254
20. Bokade R. Jin X. PyTSC: A Unified Platform for Multi-Agent Reinforcement Learning in Traffic Signal Control Sensors 2025 25 1302 10.3390/s25051302
21. Gheorghe C. Soica A. Revolutionizing Urban Mobility: A Systematic Review of AI, IoT, and Predictive Analytics in Adaptive Traffic Control Systems for Road Networks Electronics 2025 14 719 10.3390/electronics14040719
22. Ashkanani M. AlAjmi A. Alhayyan A. Esmael Z. AlBedaiwi M. Nadeem M. A Self-Adaptive Traffic Signal System Integrating Real-Time Vehicle Detection and License Plate Recognition for Enhanced Traffic Management Inventions 2025 10 14 10.3390/inventions10010014
23. Fan L. Yang Y. Ji H. Xiong S. Optimization of Traffic Signal Cooperative Control with Sparse Deep Reinforcement Learning Based on Knowledge Sharing Electronics 2025 14 156 10.3390/electronics14010156
24. Chala T.D. Kóczy L.T. Agent-Based Intelligent Fuzzy Traffic Signal Control System for Multiple Road Intersection Systems Mathematics 2025 13 124 10.3390/math13010124
25. Jia X. Guo M. Lyu Y. Qu J. Li D. Guo F. Adaptive Traffic Signal Control Based on Graph Neural Networks and Dynamic Entropy-Constrained Soft Actor–Critic Electronics 2024 13 4794 10.3390/electronics13234794
26. Wang L. Wang Y.-X. Li J.-K. Liu Y. Pi J.-T. Adaptive Traffic Signal Control Method Based on Offline Reinforcement Learning Appl. Sci. 2024 14 10165 10.3390/app142210165
27. Agrahari A. Dhabu M.M. Deshpande P.S. Tiwari A. Baig M.A. Sawarkar A.D. Artificial Intelligence-Based Adaptive Traffic Signal Control System: A Comprehensive Review Electronics 2024 13 3875 10.3390/electronics13193875
28. Dinitz Y. Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation Available online: https://www.researchgate.net/publication/228057696 (accessed on 18 May 2025)
29. Feige U. A Threshold of ln n for Approximating Set Cover J. ACM 1998 45 634 652 10.1145/285055.285059
30. Goldberg A.V. Tarjan R.E. A New Approach to the Maximum-Flow Problem J. ACM 1988 35 921 940 10.1145/48014.61051
31. Gutin G. Yeo A. Zverovich A. Traveling Salesman Should not be Greedy: Domination Analysis of Greedy-Type Heuristics for the TSP Discrete Appl. Math. 2002 117 81 86 10.1016/S0166-218X(01)00195-0
32. van Hasselt H. Guez A. Silver D. Deep Reinforcement Learning with Double Q-learning Proceedings of the AAAI Conference on Artificial Intelligence Phoenix, AZ, USA 12–17 February 2016 Available online: https://arxiv.org/abs/1509.06461 (accessed on 18 May 2025)
33. Cox T. Thulasiraman P. A Zone-Based Traffic Assignment Algorithm for Scalable Congestion Reduction ICT Express 2017 3 204 208 10.1016/j.icte.2017.11.003
34. Cormen T.H. Leiserson C.E. Rivest R.L. Stein C. Introduction to Algorithms 3rd ed. MIT Press Cambridge, MA, USA 2009
35. Boykov Y. Kolmogorov V. An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision IEEE Trans. Pattern Anal. Mach. Intell. 2004 26 1124 1137 10.1109/TPAMI.2004.60
36. Hopcroft J.E. Karp R.M. An n5/2Algorithm for Maximum Matchings in Bipartite Graphs SIAM J. Comput. 1973 2 225 231 10.1137/0202019
37. Li S. Multi-Agent Deep Deterministic Policy Gradient for Traffic Signal Control on Urban Road Network Proceedings of the 2020 IEEE International Conference on Advances in Electrical Engineering and Computer Applications (AEECA) Dalian, China 25–27 August 2020 896 901 10.1109/AEECA49918.2020.9213511
38. Roderick M. MacGlashan J. Tellex S. Implementing the Deep Q-Network Proceedings of the 30th Conference on Neural Information Processing Systems (NIPS 2016) Barcelona, Spain 5–10 December 2016
39. Boykov Y. Veksler O. Zabih R. Fast approximate energy minimization via graph cuts IEEE Trans. Pattern Anal. Mach. Intell. 2001 23 1222 1239 10.1109/34.969114
40. Shekhar S. Evans M.R. Kang J.M. Modeling and analysis of traffic bottlenecks using graph cut techniques Transp. Res. Rec. 2012 2302 71 79
41. Wang Y. Wu D. Li Y. Traffic flow optimization based on graph cuts and minimal cut algorithms J. Adv. Transp. 2017 2017 8734829

Issue

Copyright MDPI Mathematics