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 equilibriumand optimal flow assignment is developed. The method is proved to converge geometrically; under some fairly natural conditions the method is proved to converge quadratically.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
V. M. Verzhbitskii, Basics of Numerical Methods (Vysshaya Shkola, Moscow, 2002) [in Russian].
V. V. Zakharov and A. Yu. Krylatov, “A Traffic Flow System Equilibrium in Megapolis and the Navigator Strategies: Game Theory Approach,” Mat. Teor. Igr. Prilozh. 4 (4), 23–44 (2012).
V. V. Zakharov and A. Yu. Krylatov, “Competitive Routing of Traffic Flows by Navigation Providers,” Upravl. Bol’shimi Sist. No. 49, 129–147 (2014). [Automat. Remote Control 77 (1), 179–189 (2016)].
V. V. Zakharov and A. Yu. Krylatov, “Wardrop User Equilibrium on a Transportation Network of Parallel Inhomogeneous Routes,” in Control Processes and Stability: Proceedings of XLV Internatioinal Student and Postgraduate Scientific Conference, St. Peterbsburg, Russia, April 1–4, 2014, Ed. by N. V. Smirnov (Izd. Dom Fyodorovoi G. V., St. Peterbsburg, 2014), pp. 476–481.
V. I. Zorkal’tsev and M. A. Kiseleva, “Nash Equilibrium in a Transportation Model with Quadratic Costs,” Diskretn. Anal. Issled. Oper. 15 (3), 31–42 (2008).
A. Yu. Krylatov, “Optimal Strategies for Traffic FlowManagement on the Transportation Network of Parallel Links,” Vestnik St.-Peterbg. Univ. Ser. 10, No. 2, 121–130 (2014).
V. V. Mazalov, Mathematical Game Theory and Applications (Lan’, St. Petersburg, 2010) [in Russian].
V. I. Shvetsov, “Mathematical Modeling of Traffic Flows,” Avtomat. Telemekh. No. 11, 3–46 (2003). [Automat. Remote Control 64 (11), 1651–1689 (2003).
E. Altman, R. Combes, Z. Altman, and S. Sorin, “Routing Games in the Many Players Regime,” in Proceedings of the 5th International ICST Conference on Performance Evaluation Methodologies and Tools (Paris, May 16–20, 2011) (ICST, Brussels, 2011), pp. 525–527.
E. Altman and L. Wynter, “Eguilibrium, Games, and Pricing in Transportation and Telecommunication Networks,” Network. Spatial Econ. 4 (1), 7–21 (2004).
M. J. Beckmann, C. B. McGuire, and C. B. Winsten, Studies in the Economics of Transportation (Yale Univ. Press, New Haven, CT, USA, 1956).
R. -J. Chen and R. R. Meyer, “Parallel Optimization for Traffic Assignment,” Math. Program. 42 (1–3), 327–345 (1988).
S. -W. Chiou, “Optimization of Robust Area Traffic Control with Equilibrium Flow under Demand Uncertainty,” Comput. Oper. Res. 41, 399–411 (2014).
Y. -C. Chiu, J. Bottom, M. Mahut, A. Paz, R. Balakrishna, T. Waller, and J. Hicks, “Dynamic Traffic Assignment: A Primer,” in Transp. Res. Circular, Vol. E–C153. (Transp. Res. Board, Washington, DC, 2011).
R. Z. Farahani, E. Miandoabchi, W. Y. Szeto, and H. Rashidi, “A Review of Urban Transportation Network Design Problems,” European. J. Oper. Res. 229 (2), 281–302 (2013).
C. Fisk, “A Nonlinear Equation Framework for Solving Network Equilibrium Problems,” Environ. Plan. Ser. A, 16 (1), 67–80 (1984).
C. Fisk and S. Nguyen, “A Unified Approach for the Solution of Network Equilibrium Problems,” (Univ. Montreal, Montreal, 1980).
Y. Hollander and J. N. Prashker, “The Applicability ofNon-Cooperative Game Theory in TransportAnalysis,” Transp. 33 (5), 481–496 (2006).
V. Mazalov, Wardrop Equilibrium for Network with Parallel Channels and the BPR Latency Function Int. Game Theory Rev. (2016) (to appear).
M. Patriksson, “Sensitivity Analysis of Traffic Equilibria,” Transp. Sci. 38 (3), 258–281 (2004).
M. Patriksson, “AUnified Description of Iterative Algorithms for Traffic Equilibria,” European J. Oper. Res. 71 (2), 154–176 (1993).
M. Patriksson, The Traffic Assignment Problem: Models and Methods (Dover Publ., Mineola, NY, 2015).
Y. Sheffi, Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods (Prentice-Hall, Englewood Cliffs, NJ, 1985).
J. G. Wardrop, “Some Theoretical Aspects of Road Traffic Research,” Proc. Inst. Civil Eng. 1 (3), 325–362 (1952).
H. Yang and H. -J. Huang, “The Multi-Class, Multi-Criteria Traffic Network Equilibrium and Systems Optimum Problem,” Transp. Res. Part B 38 (1), 1–15 (2004).
V. V. Zakharov and A. Yu. Krylatov, “Equilibrium Assignments in Competitive and Cooperative Traffic Flow Routing,” in Collaborative Systems for Smart Networked Environments: 15th IFIP WG 5. 5 Working Conference on Virtual Enterpises, PRO-VE 2014, Amsterdam, The Netherlands, October 6–8, 2014. Proceedings, Ed. by L. M. Camarinha-Matos and H. Afsarmanesh (Springer, Heidelberg, 2014), pp. 641–648.
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: Proceedings of the 3rd International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences—MCOISMS, Nancy, France, May 11–13, 2015, Pt. II, Ed. by H. A. L. Thi, N. Th. Nguyen, and P. Ph. Dinh (Springer, Cham, Switzerland, 2015), pp. 449–458.
V. V. Zakharov and A. Yu. Krylatov, “Competitive Green-Vehicle Assignment on a Transportation Network,” in Game Theory and Applications, Vol. 17: Game-Theoretic Models in Mathematical Ecology (Nova Sci. Publ., Hauppauge, USA, 2015), pp. 205–234.
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: 14th IFIP WG 5. 5 Working Conference on Virtual Enterpises, PRO-VE 2013, Dresden, Germany, September/October 2013. Proceedings, Ed. by L. M. Camarinha-Matos and R. J. Scherer (Springer, Heidelberg, 2013), pp. 156–163.
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 (1), 121–137 (2011).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © A.Yu. Krylatov, 2016, published in Diskretnyi Analiz i Issledovanie Operatsii, 2016, Vol. 23, No. 2, pp. 63–87.
Rights and permissions
About this article
Cite this article
Krylatov, A.Y. Network flow assignment as a fixed point problem. J. Appl. Ind. Math. 10, 243–256 (2016). https://doi.org/10.1134/S1990478916020095
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1990478916020095