Edge Ranking in a Transport Graph of Petrozavodsk Basing on Equilibrium Flows
Abstract
Game-theoretic methods are frequently used to model the dynamic processes in urban road networks and evaluate network efficiency. One of the key concepts in this field is a Wardrop equilibrium (user equilibrium), the situation where no driver can reduce their journey time by unilaterally choosing another route. The concept is widely used in the literature to model the distribution of regular trips in a transport network. In general case, the equilibrium is unstable, and the construction of a new equilibrium trip distribution may require significant time. At the same time, when analyzing transport networks, one is often interested in the impact of short-term changes, when a road is closed for a short time, and the drivers do not seek for a new equilibrium but rather select acceptable routes in the current situation. Here, Wardrop equilibrium can be seen as the basic flow distribution, and the temporal changes in agents’ strategies have some impact on local or global characteristics of the network. One may predict the scale of this impact by estimating the importance of the edge being temporarily unavailable. In this work, we analyze edge centralities within a Wardrop equilibrium in the transport graph of Petrozavodsk. We propose a modification of edge betweenness centrality that incorporates precalculated equilibrium flows passing through the road segment. We illustrate how the resulting edge ranking can be used to enhance the classical betweenness centrality to consider not only the topological graph properties, but also the actual flow distribution. One can use the modified centrality measure to estimate the properties of Wardrop equilibrium and to increase the efficiency of its recalculation upon graph modifications. The results can be used in the traffic analysis and planning the development of the transport network.
Keywords:
transport graph, betweenness centrality, Wardrop equilibrium
Downloads
References
Ahmad, F., Al-Fagih, L. (2023). Game Theory Applications in Micro and Macroscopic Simulation in Transportation Network: A Comprehensive Review. IEEE Access 11, 93635–93663.
Akbarzadeh, M., Memarmontazerin, S., Derrible, S., Salehi Reihani, S. F. (2019). The role of travel demand and network centrality on the connectivity and resilience of an urban street system. Transportation 46, 1127–1141.
Bavelas, A. (1948). A mathematical model for group structures. Hum. organ. 7, 16–30.
Chirkova, J. V. (2024). Analysis of traffic flows on the road graph of Petrozavodsk. In: XIV All-Russia Control Conference (VSPU-2024): proceedings, 17-20 June 2024 (Novikov, D. A., ed), pp. 3990-3994. V.A. Trapeznikov Inst. of Control Sciences of the Russian Academy of Sciences: Moscow (in Russian).
Englert, M., Franke, T., Olbrich, L. (2010). Sensitivity of Wardrop Equilibria. Theory Comput. Syst. 47, 3–14.
Ermolin, N. A., Khitraya, V. A., Khitryi, A. V., Mazalov, V. V., Nikitina, N. N. (2022). Modeling of the City's Transport Network Using Game-Theoretic Methods on the Example of Petrozavodsk. Contributions to Game Theory and Management 15, 18–31.
Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry 1, 35–41.
Kurmankhojayev, D., Li, G., Chen, A. (2024). Link criticality index: Refinement, framework extension, and a case study. Reliability Engineering & System Safety 243, 109889.
Mattsson, L.-G., Jenelius, E. (2015). Vulnerability and resilience of transport systems – A discussion of recent research. Transportation Research Part A 81, 16–34.
Mylonas, C., Mitsakis, E., Kepaptsoglou, K. (2023). Criticality analysis in road networks with graph-theoretic measures, traffic assignment, and simulation. Physica A: Statistical Mechanics and its Applications 629, 129197.
U.S. Bureau of Public Roads (1964). Traffic Assignment Manual. U.S. Department of Commerce, Washington, D.C., 1964.
Wardrop, J. G. (1952). Some theoretical aspects of road traffic research. Proc. Institute of Civil Engineers, Part II 1, 325–378.
Zadeh, A. S. M., Rajabi, M. A. (2013). Analyzing the effect of the street network configuration on the efficiency of an urban transportation system. Cities 31, 285–297.
Downloads
Published
How to Cite
Issue
Section
License
Articles of "Contributions to Game Theory and Management" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.
