Efficient algorithm for solving dynamic user equilibrium traffic assignment
##article.authors##
- Masanao Wakui Graduate School of Information Sciences, Tohoku University
- Takara Sakai Graduate School of Information Sciences, Tohoku University https://orcid.org/0000-0002-3854-4236
-
Takashi Akamatsu
Graduate School of Information Sciences, Tohoku University
https://orcid.org/0000-0002-8545-839X
https://orcid.org/0000-0002-8545-839X
DOI:
https://doi.org/10.51094/jxiv.214Keywords:
dynamic user equilibrium, route choice, linear complementarity problem, Frank-Wolfe algorithmAbstract
This paper presents an efficient algorithm for solving dynamic user equilibrium (DUE) traffic assignment problems with one-to-many origin-destination demand. We first formulate the DUE problem, with the point queue model, as a linear complementarity problem (LCP). Then, we transform the LCP into a quadratic programming problem (QP). The QP enables us to build an efficient algorithm based on the convex combination method (Frank–Wolfe algorithm). Numerical experiments reveal that the proposed algorithm can (i) solve extremely large-scale problems to which no conventional methods can be applied, (ii) calculate the solution more than 1000 times faster than a general-purpose solver for optimization problems, and (iii) yield an extremely accurate equilibrium solution.
Downloads *Displays the aggregated results up to the previous day.
References
Ban, X. J., Liu, H. X., Ferris, M. C. and Ran, B.: A link-node complementarity model and solution algorithm for dynamic user equilibria with exact flow propagations, Transportation Research Part B: Methodological, Vol.42, No.9, pp.823-842, 2008.
Gentile, G.: Solving a dynamic user equilibrium model based on splitting rates with gradient projection algorithms, Transportation Research Part B: Methodological, Vol.92, pp.120-147, 2016.
Friesz, T. L. and Mookherjee, R.: Solving the dynamic network user equilibrium problem with state-dependent time shifts, Transportation Research Part B: Methodological, Vol.40, No.3, pp.207-229, 2006.
Akamatsu, T.: An efficient algorithm for dynamic traffic equilibrium assignment with queues, Transportation Science, Vol.35, No.4, pp.389-404, 2001.
Lo, H. K. and Szeto, W. Y.: A cell-based variational inequality formulation of the dynamic user optimal assignment problem, Transportation Research Part B: Methodological, Vol.36, No.5, pp.421-443, 2002.
Long, J., Huang, H.-J., Gao, Z. and Szeto, W. Y.: An intersection-movement-based dynamic user optimal route choice problem, Operations Research, Vol.61, No.5, pp.1134-1147, 2013.
Long, J., Szeto, W. Y., Gao, Z., Huang, H.-J. and Shi, Q.: The nonlinear equation system approach to solving dynamic user optimal simultaneous route and departure time choice problems, Transportation Research Part B: Methodological, Vol.83, pp.179-206, 2016.
Han, K., Eve, G. and Friesz, T. L.: Computing dynamic user equilibria on large-scale networks with software implementation, Networks and Spatial Economics, Vol.19, No.3, pp.869-902, 2019.
長江剛志, 赤松隆, 清水廉, 符皓然: 経路・出発時刻同時選択型の動的利用者均衡配分の求解法: 二次計画問題アプローチ, 土木学会論文集 D3（土木計画学）, Vol.76, No.3, pp.264-281, 2020. [Nagae, T., Akamatsu, T., Shimizu, R. and Fu, H.: A quadratic programming approach for solving a dynamic user equilibrium with simultaneous departure time and route choice, Transaction of the Japan Society of Civil Engineers, Vol.76, No.3, pp.264-281, 2020.]
Kuwahara, M. and Akamatsu, T.: Dynamic equilibrium assignment with queues for a one-to-many od pattern, Transportation and Traffic Theory, Vol.12, pp.185-204, 1993.
土木学会: 交通ネットワークの均衡分析-最新の理論と解法, pp. 280-281, 丸善, 1998. [the Japan Society of Civil Engineers: koutuu-network no kinnkoubunnseki saishinn norironn to kaihou, pp. 280-281, Maruzenn, 1998.]
Frank, M. and Wolfe, P.: An algorithm for quadratic programming, Naval research logistics quarterly, Vol.3, No.1-2, pp.95-110, 1956.
Dijkstra, E. W.: A note on two problems in connexion with graphs, Numerische mathematik, Vol.1, No.1, pp.269-271, 1959.
Gurobi Optimization, LLC: Gurobi optimizer reference manual, 2022, Accessed 19 Oct., 2022.
Fischer, A.: A special newton-type optimization method, Optimization, Vol.24, No.3-4, pp.269-284, 1992.
Virtanen, P., Gommers, R., Oliphant, T. E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., van der Walt, S. J., Brett, M., Wilson, J., Millman, K. J., Mayorov, N., Nelson, A. R. J., Jones, E., Kern, R., Larson, E., Carey, C. J., Polat, ˙I., Feng, Y., Moore, E. W., VanderPlas, J., Laxalde, D., Perktold, J., Cimrman, R., Henriksen, I., Quintero, E. A., Harris, C. R., Archibald, A. M., Ribeiro, A. H., Pedregosa, F., van Mulbregt, P. and SciPy 1.0 Contributors: SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python, Nature Methods, Vol.17, pp.261-272, 2020.
Dial, R. B.: A probabilistic multipath traffic assignment model which obviates path enumeration, Transportation research, Vol.5, No.2, pp.83-111, 1971.
Transportation Networks for Research Core Team: Transportation Networks for Research, 2022, Accessed 19 Oct., 2022.
井料隆雅: 車両を離散化した動的交通量配分問題のnash均衡解の解法, 土木学会論文集 D3（土木計画学）, Vol.67, No.1, pp.70-83, 2011. [Iryo, T.: Solution algorithm of nash equilibrium in dynamic traffic assignment with discretised vehicles, Transaction of the Japan Society of Civil Engineers, Vol.67, No.1, pp.70-83, 2011.]
Downloads
Posted
Submitted: 2022-11-04 11:40:26 UTC
Published: 2022-11-07 09:52:09 UTC
License
Copyright (c) 2022
Masanao Wakui
Takara Sakai
Takashi Akamatsu
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
