Volume 23, No 2, 2016, P. 63-87

UDC 519.8
A. Yu. Krylatov
Network flow assignment as a fixed point problem

Abstract:
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.

DOI: 10.17377/daio.2016.23.503

Alexander Yu. Krylatov ^1,2
1. Saint Petersburg State University,
7/9 Universitetskaya Nab., 199034 St. Petersburg, Russia
2. Solomenko Institute of Transport Problems of the RAS,
13 12th Line VO, 199178 St. Petersburg, Russia
e-mail: a.krylatov@spbu.ru, aykrylatov@yandex.ru

Received 31 July 2015
Revised 24 November 2015

References

[1] V. M. Verzhbitskii, Osnovy chislennykh metodov (Foundations of Numerical Methods), Vysshaya shkola, Moscow, 2002.

[2] V. V. Zakharov and A. Yu. Krylatov, Traffic flows’ system equilibrium in megapolis and navigators’ strategies: game theory approach, Mat. Teor. Igr. Prilozh., 4, No. 4, 23–44, 2012.

[3] V. V. Zakharov and A. Yu. Krylatov, Competitive routing of traffic flows by navigation providers, Upr. Bol’shimi Sist., No. 49, 129–147, 2014. Translated in Autom. Remote Control, 77, No. 1, 179–189, 2016.

[4] V. V. Zakharov and A. Yu. Krylatov, Wardrop user equilibrium on a transportation network of parallel inhomogeneous routes, in N. V. Smirnov, ed., Protsessy upravleniya i ustoichivost’: Trudy XLV Mezhdunarodnoi nauchnoi konferentsii aspirantov i studentov (Control Processes and Stability: Proc. XLV Int. Student and Postgraduate Scientific Conf.), St. Peterbsburg, Russia, Apr. 1–4, 2014, pp. 476–481, Izd. Dom Fyodorovoi G. V., St. Peterbsburg, 2014.

[5] V. I. Zorkal’tsev and M. A. Kiseleva, Nash equilibrium in a transportation model with quadratic costs, Diskretn. Anal. Issled. Oper., 15, No. 3, 31–42, 2008.

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

[7] V. V. Mazalov, Matematicheskaya teoriya igr i prilozheniya (Mathematical Game Theory and Applications), Lan’, St. Petersburg, 2010.

[8] V. I. Shvetsov, Mathematical modeling of traffic flows, Avtom. Telemekh., No. 11, 3–46, 2003. Translated in Autom. Remote Control, 64, No. 11, 1651–1689, 2003.

[9] E. Altman, R. Combes, Z. Altman, and S. Sorin, Routing games in the many players regime, in Proc. 5th Int. ICST Conf. Perform. Eval. Methodol. Tools, Paris, France, May 16–20, 2011, pp. 525–527, ICST, Brussels, 2011.

[10] E. Altman and L. Wynter, Eguilibrium, games, and pricing in transportation and telecommunication networks, Netw. Spat. Econ., 4, No. 1, 7–21, 2004.

[11] M. J. Beckmann, C. B. McGuire, and C. B. Winsten, Studies in the Economics of Transportation, Yale Univ. Press, New Haven, CT, USA, 1956.

[12] R.-J. Chen and R. R. Meyer, Parallel optimization for traffic assignment, Math. Program., 42, No. 1–3, 327–345, 1988.

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

[14] Y.-C. Chiu, J. Bottom, M. Mahut, A. Paz, R. Balakrishna, T. Waller, and J. Hicks, Dynamic Ttraffic Assignment: A Primer, Transp. Res. Board, Washington, 2011 (Transp. Res. Circular, Vol. E-C153).

[15] R. Z. Farahani, E. Miandoabchi, W. Y. Szeto, and H. Rashidi, A review of urban transportation network design problems, Eur. J. Oper. Res., 229, No. 2, 281–302, 2013.

[16] C. Fisk, A nonlinear equation framework for solving network equilibrium problems, Environ. Plan., Ser. A, 16, No. 1, 67–80, 1984.

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

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

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

[20] M. Patriksson, Sensitivity analysis of traffic equilibria, Transp. Sci., 38, No. 3, 258–281, 2004.

[21] M. Patriksson, A unified description of iterative algorithms for traffic equilibria, Eur. J. Oper. Res., 71, No. 2, 154–176, 1993.

[22] M. Patriksson, The Traffic Assignment Problem: Models and Methods, Dover Publ., Mineola, USA, 2015.

[23] Y. Sheffi, Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods, Prentice Hall, Englewood Cliffs, USA, 1985.

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

[25] H. Yang and H.-J. Huang, The multi-class, multi-criteria traffic network equilibrium and systems optimum problem, Transp. Res. Part B, 38, No. 1, 1–15, 2004.

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

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

[28] V. V. Zakharov and A. Yu. Krylatov, Competitive green-vehicle assignment on a transportation network, in Game Theory and Applications, Vol. 17, pp. 205–234, Nova Sci. Publ., Hauppauge, USA, 2015.

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

[30] H. Zheng and Y.-C. Chiu, A network flow algorithm for the cell-based single-destination system optimal dynamic traffic assignment problem, Transp. Sci., 45, No. 1, 121–137, 2011.