On the three-stage version of stable dynamic model

A. Gasnikov ; Yu. Dorn ; Yu. Nesterov ; S. Shpirko

Matematičeskoe modelirovanie, Tome 26 (2014) no. 6, pp. 34-70.

Résumé

In this paper we propose a new model of the traffic assignment problem. This model joints the entropy model, flow decomposition and the Stable Dynamic model. All parameters in use have a direct physical meaning and interpretations. We show that this model reduces to a non-smooth convex optimization problem that admits natural primal-dual formulation. For completeness, we present and criticize the standard static traffic assignment models. In particular, we prove that the Beckmann model reduces to the Stable Dynamic Model as a result of some limiting process.

Détail

Keywords: traffic assignment, entropy-linear programming, flow decomposition, large-scale convex optimization, primal-dual method, bounded variation of subgradient.
Mots-clés : original-destination matrix

Bibliographie

[1] Ortuzar J. D., Willumsen L. G., Modelling transport, John Willey Sons, 2011

[2] Beckmann M., McGuire C. B., Winsten C. B., Studies in the economics of transportation, RM-1488, RAND Corporation, Santa Monica, 1955

[3] Sheffi Y., Urban transportation networks: Equilibrium analysis with mathematical programming methods, Prentice-Hall Inc., Englewood Cliffs, N.J., 1985

[4] Stenbrink P. A., Optimizatsiya transportnykh setei, Transport, M., 1981

[5] Patriksson M., The traffic assignment problem. Models and methods, VSP, Utrecht, Netherlands, 1994

[6] Gasnikov A. V., Klenov S. L., Nurminskii E. A., Kholodov Ya. A., Shamrai N. B., Vvedenie v matematicheskoe modelirovanie transportnykh potokov, s prilozheniyami M. L. Blanka, K. V. Vorontsova i dr., 2-e izd., ed. A. V. Gasnikov, MTsNMO, M., 2013, 427 pp.

[7] Nesterov Y., de Palma A., “Stationary Dynamic Solutions in Congested Transportation Networks: Summary and Perspectives”, Networks Spatial Econ., 2003, no. 3(3), 371–395 | DOI | MR

[8] Sandholm W., Population games and Evolutionary dynamics. Economic Learning and Social Evolution, MIT Press, Cambridge, 2010 | MR | Zbl

[9] Ben-Tal A., Ghaoui L. El., Nemirovski A., Robust optimization, Princeton University Press, 2009 | MR | Zbl

[10] Nesterov Y., “Stable traffic equilibria: properties and applications”, Optimization and Engineering, 1 (2000), 29–50 | DOI | MR | Zbl

[11] Arnold V. I., Afraimovich V. S., Ilyashenko Yu. S., Shilnikov L. P., “Teoriya bifurkatsii-1”, Dinamicheskie sistemy-5, Sovr. problemy matematiki. Fund. napravleniya, 5, VINITI, M., 1986, 5–218 | MR

[12] Nesterov Yu. E., Vvedenie v vypukluyu optimizatsiyu, MTsNMO, M., 2010

[13] Magaril-Ilyaev G. G., Tikhomirov V. M., Vypuklyi analiz i ego prilozheniya, URSS, M., 2011

[14] Frenkin B. R., “Teorema Neimana o minimakse — obscheizvestnaya i neizvestnaya”, Matem. prosv., ser. 3, 9, MTsNMO, M., 2005, 78–85

[15] Borisovich Yu. G., Gelman B. D., Myshkis A. D., Obukhovskii V. V., Vvedenie v teoriyu mnogoznachnykh otobrazhenii i differentsialnykh vklyuchenii, URSS, M., 2011 | MR

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

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

[18] Popkov Yu. S., Teoriya makrosistem: Ravnovesnye modeli, URSS, M., 2013 | MR

[19] Gasnikov A. V., Gasnikova E. V., “Ob entropiino-podobnykh funktsionalakh, voznikayuschikh v stokhasticheskoi khimicheskoi kinetike pri kontsentratsii invariantnoi mery i v kachestve funktsii Lyapunova dinamiki kvazisrednikh”, Matematicheskie zametki, 94:6 (2013), 816–824 | DOI

[20] Boss V., Lektsii po matematike, Ucheb. posobie, v. 7, Optimizatsiya:, KomKniga, M., 2010

[21] Sen A., “Maximum likelihood estimation of gravity model parameters”, J. of Regional Science, 26:3 (1986), 461–474 | DOI

[22] Borovkov A. A., Ergodichnost i ustoichivost sluchainykh protsessov, URSS, M., 1999 | MR

[23] Jaynes E. T., Probability theory. The logic of science, Cambridge Univ. Press, Cambridge, 2003 | MR | Zbl

[24] International workshops on Bayesian inference and maximum entropy methods in science and engineering, AIP Conf. Proceedings (holds every year from 1980)

[25] Kapur J. N., Maximum - entropy models in science and engineering, John Wiley Sons, Inc., 1989 | MR | Zbl

[26] Golan A., Judge G., Miller D., Maximum entropy econometrics: Robust estimation with limited data, Wiley, Chichester, 1996 | Zbl

[27] Fang S.-C., Rajasekera J. R., Tsao H.-S. J., Entropy optimization and mathematical programming, Kluwer's International Series, 1997 | MR

[28] Gasnikova E. V., “Dvoistvennye multiplikativnye algoritmy dlya zadach entropiino-lineinogo programmirovaniya”, ZhVM i MF, 49:3 (2009), 453–464 | MR | Zbl

[29] Ethier N. S., Kurtz T. G., Markov processes. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley Sons Inc., New York, 1986 | MR | Zbl

[30] Andersen S. P., de Palma A., Thisse J.-F., Discrete choice theory of product differentiation, MIT Press, Cambridge, 1992 | MR

[31] Gasnikov A. V., Gasnikova E. V., Fedko O. S., “O vozmozhnoi dinamike v modeli ranzhirovaniya web-stranits PageRank i modernizirovannoi modeli rascheta matritsy korrespondentsii”, Trudy MFTI, 4:2 (14) (2012), 101–120

[32] Lidbetter M., Lindgren G., Rotsen Kh., Ekstremumy sluchainykh posledovatelnostei i protsessov, Mir, M., 1989 | MR

[33] Bar-Gera H., Origin-based algorithms for transportation network modeling, Univ. of Illinois at Chicago, 1999

[34] Cressman R., Evolutionary dynamics and extensive form games, MIT Press, Cambridge, Mass., 2003 | MR | Zbl

[35] Gasnikov A. V., Nesterov Yu. E., Spokoinyi V. G., “Ob effektivnosti odnogo metoda randomizatsii zerkalnogo spuska v zadachakh onlain optimizatsii”, Avtomatika i telemekhanika, 2014 (to appear)

[36] Nisan N., Roughgarden T., Trados E., Vazirani V. V. (eds.), Algorithmic game theory, Cambridge Univ. Press, 2007 http://www.eecs.harvard.edu/cs285/Nisan_Non-printable.pdf | MR

[37] Yun S., Sen A., “Computation of maximum likelihood estimates of gravity model parameters”, J. of Regional Science, 34:2 (1994), 199–216 | DOI

[38] Spokoiny V., “Parametric estimation. Finite sample theory”, The Annals of Statistics, 40:6 (2012), 2877–2909, arXiv: 1111.3029v5 | DOI | MR

[39] Hyman G. M., “The calibration of trip distribution models”, Environment and Planning, 1969, no. 1, 105–112 | DOI

[40] Evans A. W., “The calibration of trip distribution models with exponential or similar cost functions”, Transportation research, 5 (1971), 15–38 | DOI

[41] Ahuja R. K., Magnati T. L., Orlin J. B., Network flows: Theory, algorithms and applications, Prentice Hall, 1993 | MR | Zbl

[42] Kormen T. Kh., Leizerson Ch. I., Rivest R. L., Shtain K., Algoritmy: Postroenie i analiz, Vilyams, M., 2005

[43] Korte B., Vigen I., Kombinatornaya optimizatsiya: teoriya i algoritmy, MTsNMO, M., 2014

[44] Nesterov Y., “Gradient methods for minimizing composite functions”, Math. Program. Ser. B, 2012 | DOI | MR

[45] Nesterov Y., “Primal-dual subgradient methods for convex problems”, Math. Program. Ser. B, 120 (2009), 221–259 | DOI | MR | Zbl

[46] Nesterov Y., Minimizing functions with bounded variation of subgradients, CORE Discussion Papers 2005/79

[47] Gasnikov A., Nesterov Y., Dual methods for functions with bounded variation, CORE Discussion Papers, 2014

[48] Nesterov Y., “Characteristic functions of directed graphs and applications to stochastic equilibrium problems”, Optim. Engineering, 8 (2007), 193–214 | DOI | MR | Zbl

[49] Chudak F., Eleuterio V., Nesterov Y., “Static Traffic Assignment Problem. A comparison between Beckmann (1956) and Nesterov de Palma (1998) models”, Conf. Paper STRC, 2007, 1–23