About multistage transportation model and sufficient conditions for its potentiality

Evgeniya V. Gasnikova ; Alexander V. Gasnikov ; Demyan V. Yarmoshik ; Meruza B. Kubentayeva ; Mikhail I. Persiianov ; Irina V. Podlipnova ; Ekaterina V. Kotlyarova ; Ilya A. Sklonin ; Elena D. Podobnaya ; Vladislav V. Matyukhin

Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 15 (2023) no. 2, pp. 3-17.

Résumé

Multistage modeling of traffic flows began to actively develop since the 70s of the last century. Transportation modeling packages were created, which are based on a set of convex optimization problems, whose sequential solution (with appropriate feedback mechanism) converges to the desired equilibrium distribution. An alternative way is to try to find such a general convex optimization problem, the solution of which would give the desired equilibrium. In this paper, we attempt to find sufficient conditions to guarantee that the alternative path will be successful. In particular, the paper has shown that one of the blocks of a multistage model can use a stable dynamics model (rather than the generally accepted Beckmann model), combined with the possibility to choose different types of users and vehicles.

Détail

Keywords: network equilibrium model, combined model, four-stage approach, convex optimization, stable dymanics model.

Bibliographie

[1] Vilson A.Dzh., Entropiinye metody modelirovaniya slozhnykh sistem, Nauka, M., 1978 | MR

[2] Gasnikov A.V., Klenov S.L., Nurminskii E.A., Kholodov Ya.A., Shamrai N.B., Vvedenie v matematicheskoe modelirovanie transportnykh potokov, ed. A.V. Gasnikov, MTsNMO, M., 2013

[3] Gasnikov A.V. i dr., “O trekhstadiinoi versii modeli statsionarnoi dinamiki transportnykh potokov”, Matematicheskoe modelirovanie, 26:6 (2014), 34–70 | Zbl

[4] Gasnikov A.V. i dr., “Evolyutsionnye vyvody entropiinoi modeli rascheta matritsy korrespondentsii”, Matematicheskoe modelirovanie, 28:4 (2016), 111–124 | MR | Zbl

[5] Gasnikov A.V., Gasnikova E.V., Modeli ravnovesnogo raspredeleniya potokov v bolshikh setyakh, MFTI, M., 2020

[6] Gasnikov A.V., Dvurechenskii P.E., Usmanova I.N., “O netrivialnosti bystrykh (uskorennykh) randomizirovannykh metodov”, Trudy Moskovskogo fiziko-tekhnicheskogo instituta, 8:2 (30) (2016), 67–100

[7] Gasnikov A.V., Nesterov Yu.E., “Universalnyi metod dlya zadach stokhasticheskoi kompozitnoi optimizatsii”, Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki, 58:1 (2018), 51–68

[8] Ivanova A.S. i dr., “Kalibrovka parametrov modeli rascheta matritsy korrespondentsii dlya g. Moskvy”, COMPUTER, 12:5 (2020), 961–978

[9] Kotlyarova E.V. i dr., “Poisk ravnovesii v dvukhstadiinykh modelyakh raspredeleniya transportnykh potokov po seti”, Kompyuternye issledovaniya i modelirovanie, 13:2 (2021), 365–379

[10] Kotlyarova E.V. i dr., “Obosnovanie svyazi modeli Bekmana s vyrozhdayuschimisya funktsiyami zatrat s modelyu stabilnoi dinamiki”, Kompyuternye issledovaniya i modelirovanie, 14:2 (2022), 335–342

[11] Kubentaeva M.B., https://github.com/MeruzaKub/TransportNet | Zbl

[12] Mazalov V.V., Chirkova Yu.V., Setevye igry, Lan, 2022

[13] Shvetsov V.I., “Matematicheskoe modelirovanie transportnykh potokov”, Avtomatika i telemekhanika, 2003, no. 11, 3–46 | MR | Zbl

[14] Boyles S.D., Lownes N.E., Unnikrishnan A., Transportation network analysis, v. I, Static and Dynamic Traffic Assignment, 2020

[15] De Cea J., Fernandez J.E., Dekock V. and Soto A., “Solving network equilibrium problems on multimodal urban transportation networks with multiple user classes”, Transport Reviews, 25:3 (2005), 293–317 | DOI

[16] Dvurechensky P. et al., Primal-dual method for searching equilibrium in hierarchical congestion population games, arXiv: 1606.08988

[17] Dvurechensky P., Gasnikov A., Kroshnin A., Computational optimal transport: Complexity by accelerated gradient descent is better than by Sinkhorn's algorithm, arXiv: 1802.04367

[18] Dvurechensky P. et al., “A stable alternative to Sinkhorn's algorithm for regularized optimal transport”, International Conference on Mathematical Optimization Theory and Operations Research, Springer, Cham, 2020, 406–423 | DOI | MR | Zbl

[19] Evans S.P., “Derivation and analysis of some models for combining trip distribution and assignment”, Transportation Research, 10:1 (1976), 37–57 | DOI

[20] Gasnikova E. et al., “An evolutionary view on equilibrium models of transport flows”, Mathematics, 11:4 (2023), 858 | DOI

[21] Kamzolov D., Dvurechensky P., Gasnikov A., “Universal intermediate gradient method for convex problems with inexact oracle”, Optimization Methods and Software, 2020, 1–28 | MR

[22] Kroshnin A. et al., “On the complexity of approximating Wasserstein barycenters”, International conference on machine learning, PMLR, 2019, 3530–3540

[23] Kubentayeva M., Gasnikov A., Finding equilibria in the traffic assignment problem with primal-dual gradient methods for Stable Dynamics model and Beckmann model, arXiv: 2008.02418

[24] Nesterov Y., “Universal gradient methods for convex optimization problems”, Mathematical Programming, 152:1-2 (2015), 381–404 | DOI | MR | Zbl

[25] Nesterov Y. et al., “Primal-dual accelerated gradient methods with small-dimensional relaxation oracle”, Optimization Methods and Software, 2020, 1–38 | MR

[26] Nesterov Y., De Palma A., “Stationary dynamic solutions in congested transportation networks: summary and perspectives”, Networks and spatial economics, 3:3 (2003), 371–395 | DOI

[27] Ortuzar J.D., Willumsen L.G., Modelling transport, John Wiley and Sons, 2002

[28] Patriksson M., The traffic assignment problem: models and methods, Courier Dover Publications, 2015

[29] Peyre G., Cuturi M., “Computational Optimal Transport: With Applications to Data Science”, Foundations and Trends in Machine Learning, 11:5-6 (2019), 355–607 | DOI

[30] Sandholm W., Population games and evolutionary dynamics, MIT press, 2010 | MR | Zbl

[31] Stabler B., Bar-Gera H., Sall E., Transportation Networks for Research Core Team. Transportation Networks for Research, https://github.com/bstabler/TransportationNetworks