Geodesic
Network flow assignment as a~fixed point problem
Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 2, pp. 63-87.

Voir la notice de l'article provenant de la source Math-Net.Ru

This paper deals with the user equilibrium problem (flow assignment with equal journey time by alternative routes) and system optimum (flow assignment with minimal average journey time) in a network consisting of parallel routes with a single origin-destination pair. The travel time is simulated by arbitrary smooth nondecreasing functions. We prove that the equilibrium and optimal assignment problems for such a network can be reduced to the fixed point problem expressed explicitly. A simple iterative method of finding equilibrium and optimal flow assignment is developed. The method is proved to converge geometrically; under some fairly natural conditions the method is proved to converge quadratically. Bibliogr. 30.
Keywords: user-equilibrium, system optimum, fixed point, network routes. 
@article{DA_2016_23_2_a3,
     author = {A. Yu. Krylatov},
     title = {Network flow assignment as a~fixed point problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {63--87},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2016_23_2_a3/}
}
TY  - JOUR
AU  - A. Yu. Krylatov
TI  - Network flow assignment as a~fixed point problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2016
SP  - 63
EP  - 87
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2016_23_2_a3/
LA  - ru
ID  - DA_2016_23_2_a3
ER  - 
%0 Journal Article
%A A. Yu. Krylatov
%T Network flow assignment as a~fixed point problem
%J Diskretnyj analiz i issledovanie operacij
%D 2016
%P 63-87
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2016_23_2_a3/
%G ru
%F DA_2016_23_2_a3
A. Yu. Krylatov. Network flow assignment as a~fixed point problem. Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 2, pp. 63-87. http://geodesic.mathdoc.fr/item/DA_2016_23_2_a3/

[1] V. M. Verzhbitskii, Foundations of Numerical Methods, Vysshaya shkola, Moscow, 2002

[2] V. V. Zakharov, A. Yu. Krylatov, “Traffic flows' system equilibrium in megapolis and navigators' strategies: game theory approach”, Mat. Teor. Igr. Prilozh., 4:4 (2012), 23–44 | Zbl

[3] V. V. Zakharov, A. Yu. Krylatov, “Competitive routing of traffic flows by navigation providers”, Autom. Remote Control, 77:1 (2016), 179–189 | DOI | MR | Zbl

[4] V. V. Zakharov, A. Yu. Krylatov, “Wardrop user equilibrium on a transportation network of parallel inhomogeneous routes”, Control Processes and Stability, Proc. XLV Int. Student and Postgraduate Scientific Conf. (St. Peterbsburg, Russia, Apr. 1–4, 2014), ed. N. V. Smirnov, Izd. Dom Fyodorovoi G. V., St. Peterbsburg, 2014, 476–481

[5] V. I. Zorkal'tsev, M. A. Kiseleva, “Nash equilibrium in a transportation model with quadratic costs”, Diskretn. Anal. Issled. Oper., 15:3 (2008), 31–42 | MR | Zbl

[6] A. Yu. Krylatov, “Optimal strategies for traffic flow management on the transportation network of parallel links”, Vestn. St.-Peterbg. Univ., Ser. 10, 2014, no. 2, 121–130

[7] V. V. Mazalov, Mathematical Game Theory and Applications, Lan', St. Petersburg, 2010

[8] V. I. Shvetsov, “Mathematical modeling of traffic flows”, Autom. Remote Control, 64:11 (2003), 1651–1689 | DOI | MR | Zbl

[9] Altman E., Combes R., Altman Z., Sorin S., “Routing games in the many players regime”, Proc. 5th Int. ICST Conf. Performance Evaluation Methodologies and Tools (Paris, May 16–20, 2011), ICST, Brussels, 2011, 525–527

[10] Altman E., Wynter L., “Eguilibrium, games, and pricing in transportation and telecommunication networks”, Netw. Spatial Econ., 4:1 (2004), 7–21 | DOI | Zbl

[11] Beckmann M. J., McGuire C. B., Winsten C. B., Studies in the economics of transportation, Yale Univ. Press, New Haven, CT, 1956, 359 pp.

[12] Chen R.-J., Meyer R. R., “Parallel optimization for traffic assignment”, Math. Program., 42:1–3 (1988), 327–345 | DOI | MR | Zbl

[13] Chiou S.-W., “Optimization of robust area traffic control with equilibrium flow under demand uncertainty”, Comput. Oper. Res., 41 (2014), 399–411 | DOI | MR

[14] Chiu Y.-C., Bottom J., Mahut M., Paz A., Balakrishna R., Waller T., Hicks J., Transp. Res. Circular No E–C153, Transp. Res. Board, Washington, DC, 2011, 62 pp.

[15] Farahani R. Z., Miandoabchi E., Szeto W. Y., Rashidi H., “A review of urban transportation network design problems”, Eur. J. Oper. Res., 229:2 (2013), 281–302 | DOI | MR | Zbl

[16] Fisk C., “A nonlinear equation framework for solving network equilibrium problems”, Environ. Plan. Ser. A, 16:1 (1984), 67–80 | DOI

[17] Fisk C., Nguyen S., A unified approach for the solution of network equilibrium problems, Publ. Centre Rech. Transp., 169, Univ. Montreal, Montreal, 1980

[18] Hollander Y., Prashker J. N., “The applicability of non-cooperative game theory in transport analysis”, Transp., 33:5 (2006), 481–496

[19] Mazalov V., “Wardrop equilibrium for network with parallel channels and the BPR latency function”, Int. Game Theory Rev., 2016 (to appear)

[20] Patriksson M., “Sensitivity analysis of traffic equilibria”, Transp. Sci., 38:3 (2004), 258–281 | DOI | MR

[21] Patriksson M., “A unified description of iterative algorithms for traffic equilibria”, Eur. J. Oper. Res., 71:2 (1993), 154–176 | DOI | Zbl

[22] Patriksson M., The traffic assignment problem: models and methods, Dover Publ. Inc, Mineola, NY, 2015, 240 pp.

[23] Sheffi Y., Urban transportation networks: equilibrium analysis with mathematical programming methods, Prentice-Hall, Englewood Cliffs, NJ, 1985, 416 pp.

[24] Wardrop J. G., “Some theoretical aspects of road traffic research”, Proc. Inst. Civil Eng., 1:3 (1952), 325–362

[25] Yang H., Huang H.-J., “The multi-class, multi-criteria traffic network equilibrium and systems optimum problem”, Transp. Res. Part B, 38:1 (2004), 1–15 | DOI

[26] Zakharov V. V., Krylatov A. Yu., “Equilibrium assignments in competitive and cooperative traffic flow routing”, Collaborative Systems for Smart Networked Environments, Proc. 15th IFIP WG 5.5 Work. Conf. Virtual Enterp. (Amsterdam, The Netherlands, Oct. 6–8, 2014), IFIP Adv. Inf. Commun. Technol., 434, Springer, Heidelberg, 2014, 641–648 | DOI

[27] Zakharov V. V., Krylatov A. Yu., “Transist network design for green vehicles routing”, Modelling, Computation and Optimization in Information Systems and Management Sciences, Proc. 3rd Int. Conf. MCOISMS (Nancy, France, May 11–13, 2015), Pt. II, Adv. Intell. Syst. Comput., 360, Springer, Cham, Switzerland, 2015, 449–458 | DOI

[28] Zakharov V. V., Krylatov A. Yu., “Competitive green-vehicle assignment on a transportation network”, Game Theoretic Models Math. Ecology, Game Theory and Applications, 17, Nova Sci. Publ., New York, 2015, 205–234

[29] Zakharov V. V., Krylatov A. Yu., Ivanov D. A., “Equilibrium traffic flow assignment in case of two navigation providers”, Collaborative Systems for Reindustrialization, Proc. 14th IFIP WG 5.5 Work. Conf. Virtual Enterp. (Dresden, Germany, Sept. 30 – Oct. 2, 2013), IFIP Adv. Inf. Commun. Technol., 408, Springer, Heidelberg, 2013, 156–163 | DOI

[30] Zheng H., Chiu Y.-C., “A network flow algorithm for the cell-based single-destination system optimal dynamic traffic assignment problem”, Transp. Sci., 45:1 (2011), 121–137 | DOI