×

Improving the convergence of simulation-based dynamic traffic assignment methodologies. (English) Zbl 1338.90110

Summary: The ability of simulation-based dynamic traffic assignment (SBDTA) models to produce reliable solutions is crucial for practical applications, particularly for those involving the comparison of modeling results across multiple scenarios. This work reviews, implements and compares novel and existing techniques for finding equilibrium solutions for SBDTA problems, focusing on their convergence pattern and stability of the results. The considered methodologies, ranging from MSA and gradient-based heuristics to column generation frameworks and partial demand loading schemes, have not been previously compared side-to-side in the literature. This research uses a single SBDTA platform to conduct such comparison on three real networks, including one with more than 200,000 trips. Most analyzed approaches were found to require a similar number of simulation runs to reach near-equilibrium solutions. However, results suggest that the quality of the results for a given convergence level may vary across methodologies.

MSC:

90B20 Traffic problems in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bertsekas D, Gafni EM (1983) Projected Newton methods and optimization of multi-commodity flows. IEEE Trans Autom Control 28(12):1000-1006 · Zbl 0525.90042 · doi:10.1109/TAC.1983.1103183
[2] Boyles S, Duthie J, Melson C, Rambha T (2013) Diverge models and dynamic traffic equilibria. INFORMS Annual Meeting · Zbl 1042.90515
[3] Chiu YC, Bustillos B (2009) A gap function vehicle-based solution procedure for consistent and robust simulation-based dynamic traffic assignment. Transportation Research Board 88th Annual Meeting. No. 09-3721 · Zbl 0064.20906
[4] Chiu YC, Bottom J, Mahut M, Paz A, Balakrishna R, Travis Waller S (2011) Dynamic traffic assignment: a primer. Transportation Research E-Circular E-C153
[5] Daganzo C (1994) The cell transmission model: a dynamic representation of highway traffic consistent with the hydrodynamic theory. Transp Res B Methodol 28(4):268-287 · doi:10.1016/0191-2615(94)90002-7
[6] Daganzo C (1995) The cell transmission model, part II: network traffic. Transp Res B Methodol 29.2:79-93 · doi:10.1016/0191-2615(94)00022-R
[7] Florian M, Mahut M, Tremblay N (2008) Application of a simulation-based dynamic traffic assignment model. Eur J Oper Res 198(3):1381-1392 · Zbl 1146.90366 · doi:10.1016/j.ejor.2006.07.054
[8] Iryo T (2011) Multiple equilibria in a dynamic traffic network. Transp Res B Methodol 45(6):867-879 · doi:10.1016/j.trb.2011.02.010
[9] Iryo T (2013) Investigating factors for existence of multiple equilibria in dynamic traffic network. Netw Spat Econ. doi:10.1007/s11067-013-9206-6 · Zbl 1338.91037
[10] Jayakrishnan R, Tsai WK, Prashker JN, Rajadhyaksha S (1994) A faster path-based algorithm fortraffic assignment. Transp Res Rec 1443:75-83
[11] Lighthill MJ, Whitham JB (1955) On kinematic waves II: a theory of traffic flow on long crowded roads. Proc R Soc A 229:317-245 · Zbl 0064.20906 · doi:10.1098/rspa.1955.0089
[12] Liu HX, He X, He B (2009) Method of successive weighted averages (MSWA) and selfregulated averaging schemes for solving stochastic user equilibrium problem. Netw Spat Econ 9(4):485-503 · Zbl 1178.90066 · doi:10.1007/s11067-007-9023-x
[13] Lo H, Chen A (2000) Reformulating the general traffic equilibrium problem via a smooth gap function. Math Comput Model 31(2/3):179-195 · Zbl 1042.90515 · doi:10.1016/S0895-7177(99)00231-9
[14] Lu C-C, Mahmassani HS, Zhou X (2009) Equivalent gap function-based reformulation and solution algorithm for the dynamic user equilibrium problem. Transp Res B Methodol 43(3):345-364 · doi:10.1016/j.trb.2008.07.005
[15] Mahut M, Florian M, Tremblay N (2008) Comparison of assignment methods for simulation-based dynamic-equilibrium traffic assignment. Proceeding of the Transportation Research Board 87th Annual Meeting (DVD), Washington, DC · Zbl 1146.90366
[16] Mounce R, Carey M (2011) Route swapping in dynamic traffic networks. Transp Res B Methodol 45(1):102-111 · doi:10.1016/j.trb.2010.05.005
[17] Powell W, Sheffi Y (1982) The convergence of equilibrium algorithms with predetermined step sizes. Transp Sci 16:45-55 · doi:10.1287/trsc.16.1.45
[18] Richards PI (1956) Shockwaves on the highway. Oper Res 4:42-51 · doi:10.1287/opre.4.1.42
[19] Robbins H, Monro S (1951) A stochastic approximation method. Ann Math Stat 400-407 · Zbl 0054.05901
[20] Sbayti H, Lu C, Mahmassani H (2007) Efficient implementation of method of successive averages in simulation-based dynamic traffic assignment models for large-scale network applications. Transp Res Rec J Transp Res Board 2029:22-30 · doi:10.3141/2029-03
[21] Sheffi Y (1985) Urban transportation networks: equilibrium analysis with mathematical programming methods. Prentice-Hall, Inc, p 399
[22] Smith MJ (1979) The existence, uniqueness and stability of traffic equilibria. Transp Res B Methodol 13(4):295-304 · doi:10.1016/0191-2615(79)90022-5
[23] Szeto W, Lo H (2006) Dynamic traffic assignment: properties and extensions. Transportmetrica 2:31-52 · doi:10.1080/18128600608685654
[24] Tong C, Wong S (2010) Heuristic algorithms for simulation-based dynamic traffic assignment. Transportmetrica 6(2):97-120 · doi:10.1080/18128600802630281
[25] Torbjörn L, Patriksson M (1992) Simplicial decomposition with disaggregated representation for the traffic assignment problem. Transportation Science 26(1):4-17 · Zbl 0764.90033
[26] Yang I, Jayakrishnan R (2012) Gradient projection method for simulation-based dynamic traffic assignment. Transp Res Rec J Transp Res Board 2284(1):70-80 · doi:10.3141/2284-09
[27] Yperman I (2007) The link transmission model for dynamic network loading. https://lirias.kuleuven.be/handle/1979/946
[28] Ziliaskopoulos AK, Travis Waller S (2000) An internet-based geographic information system that integrates data, models and users for transportation applications. Transportation Research Part C: Emerging Technologies 1:427-444
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.