大規模ネットワークにおける動的利用者均衡配分の効率的解法

涌井, 優尚; 酒井, 高良; 赤松, 隆

doi:10.51094/jxiv.214

##article.authors##

涌井, 優尚東北大学大学院情報科学研究科
酒井, 高良東北大学大学院情報科学研究科 https://orcid.org/0000-0002-3854-4236
赤松, 隆東北大学大学院情報科学研究科 https://orcid.org/0000-0002-8545-839X https://orcid.org/0000-0002-8545-839X

DOI:

https://doi.org/10.51094/jxiv.214

キーワード:

動的利用者均衡配分、経路選択、線形相補性問題、 Frank-Wolfe法

抄録

本研究では，一起点多終点ネットワークにおける経路選択DUE配分の効率的解法を開発した．具体的には，まず待ち行列にpoint queue を仮定した上で，DUE 配分を線形相補性問題として定式化した．そしてこの問題と等価な最適化問題に対し，大規模問題に適用可能な効率的アルゴリズムを提案した．数値実験を通して提案解法は，既存研究における数値計算例を大幅に上回る規模の巨大ネットワークに対しても，素朴な解法の100倍から1000 倍程度以上の計算効率を誇り，かつきわめて高精度な均衡解が計算できることが示された．

ダウンロード *前日までの集計結果を表示します

ダウンロード実績データは、公開の翌日以降に作成されます。

引用文献

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.]