Improving the convergence of simulation-based dynamic traffic assignment methodologies.

*(English)*Zbl 1338.90110Summary: 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 |

##### Keywords:

dynamic traffic assignment; convergence; MSA; gradient projection; gradient; based; column generation; simplicial decomposition; simulation; heuristics; stability
PDF
BibTeX
XML
Cite

\textit{M. W. Levin} et al., Netw. Spat. Econ. 15, No. 3, 655--676 (2015; Zbl 1338.90110)

Full Text:
DOI

##### References:

[1] | Bertsekas, D; Gafni, EM, Projected Newton methods and optimization of multi-commodity flows, IEEE Trans Autom Control, 28, 1000-1006, (1983) · Zbl 0525.90042 |

[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, The cell transmission model: a dynamic representation of highway traffic consistent with the hydrodynamic theory, Transp Res B Methodol, 28, 268-287, (1994) |

[6] | Daganzo, C, The cell transmission model, part II: network traffic, Transp Res B Methodol, 29.2, 79-93, (1995) |

[7] | Florian, M; Mahut, M; Tremblay, N, Application of a simulation-based dynamic traffic assignment model, Eur J Oper Res, 198, 1381-1392, (2008) · Zbl 1146.90366 |

[8] | Iryo, T, Multiple equilibria in a dynamic traffic network, Transp Res B Methodol, 45, 867-879, (2011) |

[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 |

[10] | Jayakrishnan, R; Tsai, WK; Prashker, JN; Rajadhyaksha, S, A faster path-based algorithm fortraffic assignment, Transp Res Rec, 1443, 75-83, (1994) |

[11] | Lighthill, MJ; Whitham, JB, On kinematic waves II: a theory of traffic flow on long crowded roads, Proc R Soc A, 229, 317-245, (1955) · Zbl 0064.20906 |

[12] | Liu, HX; He, X; He, B, Method of successive weighted averages (MSWA) and selfregulated averaging schemes for solving stochastic user equilibrium problem, Netw Spat Econ, 9, 485-503, (2009) · Zbl 1178.90066 |

[13] | Lo, H; Chen, A, Reformulating the general traffic equilibrium problem via a smooth gap function, Math Comput Model, 31, 179-195, (2000) · Zbl 1042.90515 |

[14] | Lu, C-C; Mahmassani, HS; Zhou, X, Equivalent gap function-based reformulation and solution algorithm for the dynamic user equilibrium problem, Transp Res B Methodol, 43, 345-364, (2009) |

[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, Route swapping in dynamic traffic networks, Transp Res B Methodol, 45, 102-111, (2011) |

[17] | Powell, W; Sheffi, Y, The convergence of equilibrium algorithms with predetermined step sizes, Transp Sci, 16, 45-55, (1982) |

[18] | Richards, PI, Shockwaves on the highway, Oper Res, 4, 42-51, (1956) |

[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, 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, (2007) |

[21] | Sheffi Y (1985) Urban transportation networks: equilibrium analysis with mathematical programming methods. Prentice-Hall, Inc, p 399 |

[22] | Smith, MJ, The existence, uniqueness and stability of traffic equilibria, Transp Res B Methodol, 13, 295-304, (1979) |

[23] | Szeto, W; Lo, H, Dynamic traffic assignment: properties and extensions, Transportmetrica, 2, 31-52, (2006) |

[24] | Tong, C; Wong, S, Heuristic algorithms for simulation-based dynamic traffic assignment, Transportmetrica, 6, 97-120, (2010) |

[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, Gradient projection method for simulation-based dynamic traffic assignment, Transp Res Rec J Transp Res Board, 2284, 70-80, (2012) |

[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.