Proposing a Simulation-Based Dynamic System Optimal Traffic Assignment Algorithm for SUMO: An Approximation of Marginal Travel Time
Keywords:Dynamic Traffic Assignment, Simulation of Urban Mobility (SUMO), System Optimal, User Equilibrium, Marginal Travel Time
User equilibrium (UE) and system optimal (SO) are among the essential principles for solving the traffic assignment problem. Many studies have been performed on solving the UE and SO traffic assignment problem; however, the majority of them are either static (which can lead to inaccurate predictions due to long aggregation intervals) or analytical (which is computationally expensive for large-scale networks). Besides, most of the well-known micro/meso traffic simulators, do not provide a SO solution of the traffic assignment problem. To this end, this study proposes a new simulation-based dynamic system optimal (SB-DSO) traffic assignment algorithm for the SUMO simulator, which can be applied on large-scale networks. A new swapping/convergence algorithm, which is based on the logit route choice model, is presented in this study. This swapping algorithm is compared with the Method of Successive Average (MSA) which is very common in the literature. Also, a surrogate model of marginal travel time was implemented in the proposed algorithm, which was tested on real and abstract road networks (both on micro and meso scales). The results indicate that the proposed swapping algorithm has better performance than the classical swapping algorithms (e.g. MSA). Furthermore, a comparison was made between the proposed SB-DSO and the current simulation-based dynamic user equilibrium (SB-DUE) traffic assignment algorithm in SUMO. This proposed algorithm helps researchers to better understand the impacts of vehicles that may follow SO routines in future (e.g., Connected and Autonomous Vehicles (CAVs)).
Ameli, M., Lebacque, J.-P., & Leclercq, L. (2020a). Improving traffic network performance with road banning strategy: A simulation approach comparing user equilibrium and system optimum. Simulation Modelling Practice and Theory, 99, 101995. https://doi.org/https://doi.org/10.1016/j.simpat.2019.101995
Ameli, M., Lebacque, J., & Leclercq, L. (2020b). Simulation‐based dynamic traffic assignment: Meta‐heuristic solution methods with parallel computing. Computer‐Aided Civil and Infrastructure Engineering, 35(10), 1047–1062.
Bagloee, S. A., Sarvi, M., Patriksson, M., & Rajabifard, A. (2017). A mixed user‐equilibrium and system‐optimal traffic flow for connected vehicles stated as a complementarity problem. Computer‐Aided Civil and Infrastructure Engineering, 32(7), 562–580. https://doi.org/https://doi.org/10.1111/mice.12261
Bamdad Mehrabani, B., Sgambi, L., Garavaglia, E., & Madani, N. (2021). Modeling Methods for the Assessment of the Ecological Impacts of Road Maintenance Sites. In P. Singh (Ed.), Environmental Sustainability and Economy 1st Edition. Elsevier. https://www.elsevier.com/books/environmental-sustainability-and-economy/singh/978-0-12-822188-4
Barceló, J, & Ferrer, J. L. (1997). Advanced Interactive Microscopic Simulator for Urban Network. Departement d’Estadística i Investigació Operativa, Universitat Politèctina de Catalunya, User’s Manual Edn.
Barceló, Jaume. (2010). Fundamentals of traffic simulation (Vol. 145). Springer. https://doi.org/10.1007/978-1-4419-6142-6_1
Ben-Akiva, M. E., Koutsopoulos, H. N., Mishalani, R. G., & Yang, Q. (1997). Simulation laboratory for evaluating dynamic traffic management systems. Journal of Transportation Engineering, 123(4), 283–289. https://doi.org/https://doi.org/10.1061/(ASCE)0733-947X(1997)123:4(283)
Chen, R., Becarie, C., & Leclercq, L. (2021). Learning link marginals from dynamic simulation to calculate sustainable system optimum. HEART 2020, 9th Symposium of the European Association for Research in Transportation-Virtual Conference, 13p. https://hal.archives-ouvertes.fr/hal-03154849
Chiu, Y. C., Nava, E., Zheng, H., & Bustillos, B. (2011). DynusT user’s manual. In Department of Engineering, University of Arizona, Tucson.
DLR. (2021). SUMO User Documentation. https://sumo.dlr.de/docs/index.html
Doan, K., & Ukkusuri, S. V. (2015). Dynamic system optimal model for multi-OD traffic networks with an advanced spatial queuing model. Transportation Research Part C: Emerging Technologies, 51, 41–65. https://doi.org/https://doi.org/10.1016/j.trc.2014.10.011
Dobler, C., & Nagel, K. (2016). Within-day replanning. In The Multi-Agent Transport Simulation MATSim (pp. 187–200). Ubiquity Press. https://doi.org/http:// dx.doi.org/10.5334/baw.30
Eclipse. (2022). Eclipse SUMO. https://github.com/eclipse/sumo/blob/master/tools/assign/duaIterate.py
Fellendorf, M. (1996). VISSIM for traffic signal optimisation. Traffic Technology International’96. Annual Review Issue. http://worldcat.org/issn/13569252
Gawron, C. (1998). Simulation-Based Traffic Assignment. Computing user equilibria in large street networks [Universität zu Köln]. http://kups.ub.uni-koeln.de/id/eprint/9257
Ghali, M. O., & Smith, M. J. (1995). A model for the dynamic system optimum traffic assignment problem. Transportation Research Part B: Methodological, 29(3), 155–170. https://doi.org/https://doi.org/10.1016/0191-2615(94)00024-T
Gipps, P. G. (1981). A behavioural car-following model for computer simulation. Transportation Research Part B: Methodological, 15(2), 105–111. https://doi.org/https://doi.org/10.1016/0191-2615(81)90037-0
Hu, T.-Y., Tong, C.-C., Liao, T.-Y., & Chen, L.-W. (2018). Dynamic route choice behaviour and simulation-based dynamic traffic assignment model for mixed traffic flows. KSCE Journal of Civil Engineering, 22(2), 813–822. https://doi.org/10.1007/s12205-017-1025-8
Jayakrishnan, R., Mahmassani, H. S., & Hu, T.-Y. (1994). An evaluation tool for advanced traffic information and management systems in urban networks. Transportation Research Part C: Emerging Technologies, 2(3), 129–147. https://doi.org/https://doi.org/10.1016/0968-090X(94)90005-1
Krauß, S., Wagner, P., & Gawron, C. (1997). Metastable states in a microscopic model of traffic flow. Physical Review E, 55(5), 5597. https://doi.org/https://doi.org/10.1103/PhysRevE.55.5597
Lämmel, G., & Flötteröd, G. (2009). Towards system optimum: Finding optimal routing strategies in time-dependent networks for large-scale evacuation problems. Annual Conference on Artificial Intelligence, 532–539. https://doi.org/https://doi.org/10.1007/978-3-642-04617-9_67
LeBlanc, L. J., Morlok, E. K., & Pierskalla, W. P. (1975). An efficient approach to solving the road network equilibrium traffic assignment problem. Transportation Research, 9(5), 309–318.
Li, C. (2016). Multi-agent dynamic traffic assignment incorporating GPS diary and personalized supernetwork approach [Eindhoven University of Technology]. https://research.tue.nl/en/studentTheses/multi-agent-dynamic-traffic-assignment-incorporating-gps-diary-an
Lighthill, M. J., & Whitham, G. B. (1955). On kinematic waves II. A theory of traffic flow on long crowded roads. Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 229(1178), 317–345. https://doi.org/https://doi.org/10.1098/rspa.1955.0089
Liu, H. X., He, X., & He, B. (2009). Method of successive weighted averages (MSWA) and self-regulated averaging schemes for solving stochastic user equilibrium problem. Networks and Spatial Economics, 9(4), 485–503.
Liu, J., Mirchandani, P., & Zhou, X. (2020). Integrated vehicle assignment and routing for system-optimal shared mobility planning with endogenous road congestion. Transportation Research Part C: Emerging Technologies, 117, 102675. https://doi.org/https://doi.org/10.1016/j.trc.2020.102675
Liu, R. (2010). Traffic simulation with DRACULA. In Fundamentals of traffic simulation (pp. 295–322). Springer. https://doi.org/https://doi.org/10.1007/978-1-4419-6142-6_8
Lopez, P. A., Behrisch, M., Bieker-Walz, L., Erdmann, J., Flötteröd, Y.-P., Hilbrich, R., Lücken, L., Rummel, J., Wagner, P., & Wießner, E. (2018). Microscopic traffic simulation using sumo. 2018 21st International Conference on Intelligent Transportation Systems (ITSC), 2575–2582. https://doi.org/10.1109/ITSC.2018.8569938
Lu, C.-C., Liu, J., Qu, Y., Peeta, S., Rouphail, N. M., & Zhou, X. (2016). Eco-system optimal time-dependent flow assignment in a congested network. Transportation Research Part B: Methodological, 94, 217–239. https://doi.org/https://doi.org/10.1016/j.trb.2016.09.015
Mahmassani, H. S., & Peeta, S. (1993). Network performance under system optimal and user equilibrium dynamic assignments: implications for advanced traveler information systems. Transportation Research Record, 1408, 83. http://onlinepubs.trb.org/Onlinepubs/trr/1993/1408/1408-011.pdf
Mahmassani, H. S., & Peeta, S. (1995). System optimal dynamic assignment for electronic route guidance in a congested traffic network. In Urban Traffic Networks (pp. 3–37). Springer. https://doi.org/https://doi.org/10.1007/978-3-642-79641-8_1
Mahut, M. (2001). A DISCRETE FLOW MODEL FOR DYNAMIC NETWORK LOADING [Universitk de Montreal]. https://trid.trb.org/view/660668
Mansourianfar, M. H., Gu, Z., Waller, S. T., & Saberi, M. (2021). Joint routing and pricing control in congested mixed autonomy networks. Transportation Research Part C: Emerging Technologies, 131, 103338.
Newell, G. F. (2002). A simplified car-following theory: a lower order model. Transportation Research Part B: Methodological, 36(3), 195–205. https://doi.org/https://doi.org/10.1016/S0191-2615(00)00044-8
Ngoduy, D., Hoang, N. H., Vu, H. L., & Watling, D. (2021). Multiclass dynamic system optimum solution for mixed traffic of human-driven and automated vehicles considering physical queues. Transportation Research Part B: Methodological, 145, 56–79. https://doi.org/https://doi.org/10.1016/j.trb.2020.12.008
Patriksson, M. (2015). The traffic assignment problem: models and methods. Courier Dover Publications.
Peeta, S., & Mahmassani, H. S. (1995). System optimal and user equilibrium time-dependent traffic assignment in congested networks. Annals of Operations Research, 60(1), 81–113. https://doi.org/https://doi.org/10.1007/BF02031941
Peeta, S., & Ziliaskopoulos, A. K. (2001). Foundations of dynamic traffic assignment: The past, the present and the future. Networks and Spatial Economics, 1(3), 233–265. https://doi.org/https://doi.org/10.1023/A:1012827724856
Qian, Z. S., Shen, W., & Zhang, H. M. (2012). System-optimal dynamic traffic assignment with and without queue spillback: Its path-based formulation and solution via approximate path marginal cost. Transportation Research Part B: Methodological, 46(7), 874–893. https://doi.org/https://doi.org/10.1016/j.trb.2012.02.008
Rahman, M. R., Siddique, A., & Shahid Mamun, M. (2015). Comparison of User Equilibrium (UE) and System Optimum (SO) Traffic Assignment Methods for Auto Trips. International Conference on Recent Innovation in Civil Engineering for Sustainable Development (IICSD-2015. https://doi.org/10.13140/RG.2.1.2169.3204
Richards, P. I. (1956). Shock waves on the highway. Operations Research, 4(1), 42–51. https://doi.org/https://doi.org/10.1287/opre.4.1.42
Saw, K., Katti, B. K., & Joshi, G. (2015). Literature review of traffic assignment: static and dynamic. International Journal of Transportation Engineering, 2(4), 339–347. https://doi.org/10.22119/IJTE.2015.10447
Sbayti, H., Lu, C.-C., & Mahmassani, H. S. (2007). Efficient implementation of method of successive averages in simulation-based dynamic traffic assignment models for large-scale network applications. Transportation Research Record, 2029(1), 22–30. https://doi.org/https://doi.org/10.3141/2029-03
Sheffi, Y. (1985). Urban transportation networks (Vol. 6). Prentice-Hall, Englewood Cliffs, NJ.
Shen, W., Nie, Y., & Zhang, H. M. (2007). On path marginal cost analysis and its relation to dynamic system-optimal traffic assignment. Transportation and Traffic Theory 2007. Papers Selected for Presentation at ISTTT17Engineering and Physical Sciences Research Council (Great Britain) Rees Jeffreys Road FundTransport Research FoundationTMS ConsultancyOve Arup and Partners, Hong KongTransp. http://worldcat.org/isbn/9780080453750
Shen, W., Nie, Y., & Zhang, H. M. (2006). Path-based system optimal dynamic traffic assignment models: formulations and solution methods. 2006 IEEE Intelligent Transportation Systems Conference, 1298–1303. https://doi.org/10.1109/ITSC.2006.1707402
Shen, W., & Zhang, H. M. (2009). On the morning commute problem in a corridor network with multiple bottlenecks: Its system-optimal traffic flow patterns and the realizing tolling scheme. Transportation Research Part B: Methodological, 43(3), 267–284. https://doi.org/https://doi.org/10.1016/j.trb.2008.07.004
Smith, M., Duncan, G., & Druitt, S. (1995). PARAMICS: microscopic traffic simulation for congestion management. IEE Colloquium on Dynamic Control of Strategic Inter-Urban Road Networks, 1–8. https://doi.org/10.1049/ic:19950249
Taale, H., & Pel, A. (2015). Better convergence for dynamic traffic assignment methods. Transportation Research Procedia, 10, 197–206.
Tajtehranifard, H., Bhaskar, A., Nassir, N., Haque, M. M., & Chung, E. (2018). A path marginal cost approximation algorithm for system optimal quasi-dynamic traffic assignment. Transportation Research Part C: Emerging Technologies, 88, 91–106. https://doi.org/https://doi.org/10.1016/j.trc.2018.01.002
Taylor, N. B. (2003). The CONTRAM dynamic traffic assignment model. Networks and Spatial Economics, 3(3), 297–322. https://doi.org/https://doi.org/10.1023/A:1025394201651
Tsanakas, N. (2019). Emission estimation based on traffic models and measurements (Vol. 1835) [Linköping University Electronic Press]. https://doi.org/10.3384/lic.diva-155771
US-DOT. (1995). TRAF User Reference Guide. Federal Highway Administration.
Van Aerde, M., Hellinga, B., Baker, M., & Rakha, H. (1996). INTEGRATION: An overview of traffic simulation features. Transportation Research Records. http://www.civil.uwaterloo.ca/bhellinga/publications/Publications/TRB 1996 Integration Features.pdf
Wang, J., Peeta, S., & He, X. (2019). Multiclass traffic assignment model for mixed traffic flow of human-driven vehicles and connected and autonomous vehicles. Transportation Research Part B: Methodological, 126, 139–168. https://doi.org/https://doi.org/10.1016/j.trb.2019.05.022
Wang, W., Uehara, M., & Ozaki, H. (2018). System optimum traffic assignment for connected cars. 2018 Sixth International Symposium on Computing and Networking Workshops (CANDARW), 370–375. https://doi.org/10.1109/CANDARW.2018.00074
Wardrop, J. G. (1952). Road paper. some theoretical aspects of road traffic research. Proceedings of the Institution of Civil Engineers, 1(3), 325–362. https://doi.org/https://doi.org/10.1680/ipeds.1952.11259
Wie, B.-W., Friesz, T. L., & Tobin, R. L. (1990). Dynamic user optimal traffic assignment on congested multidestination networks. Transportation Research Part B: Methodological, 24(6), 431–442. https://doi.org/https://doi.org/10.1016/0191-2615(90)90038-Z
Yang, I., & Jayakrishnan, R. (2012). Gradient Projection Method for Simulation-Based Dynamic Traffic Assignment. Transportation Research Record, 2284(1), 70–80. https://doi.org/10.3141/2284-09
Yperman, I. (2007). The link transmission model for dynamic network loading [KU LEUVEN].
Zhang, P., & Qian, S. (2020). Path-based system optimal dynamic traffic assignment: A subgradient approach. Transportation Research Part B: Methodological, 134, 41–63. https://doi.org/https://doi.org/10.1016/j.trb.2020.02.004
Zhou, X., & Taylor, J. (2014). DTALite: A queue-based mesoscopic traffic simulator for fast model evaluation and calibration. Cogent Engineering, 1(1). https://doi.org/https://doi.org/10.1080/23311916.2014.961345
Ziliaskopoulos, A. K. (2000). A linear programming model for the single destination system optimum dynamic traffic assignment problem. Transportation Science, 34(1), 37–49.
How to Cite
Copyright (c) 2022 Behzad Bamdad Mehrabani, Jakob Erdmann, Luca Sgambi, Maaike Snelder
This work is licensed under a Creative Commons Attribution 3.0 Unported License.
Université Catholique de Louvain
Grant numbers Fonds Spéciaux de Recherche