Human mobility is one of the important factors afecting the eficiency of cities and the quality of life of their dwellers. However, while city planners aim to improve the urban road network design to satisfy the local mobility demand and distribute trafic in an optimal way, the structure of cities across diferent areas and countries vary considerably and in complex ways, sometimes being the result of historical stratifications. One question that emerges, then, is how we can characterize cities in terms of (potential) trafic eficiency. In this work we aim to study the problem from a new perspective, introducing the concept of (shortest) path instability, which quantifies the tendency of a road network to provide very diferent travel alternatives for just slightly diferent trips. A notable case of that, which stimulated this research, is the city of Barcelona, where, apparently, reaching very close destinations might require very diferent routes. The concept is implemented and applied to two case studies at diferent spatial scales, one comparing the European capitals and the other comparing municipalities of an Italian region. Results show that path instability is heterogeneously distributed, with some largely unstable cities and others very stable, and it is not directly determined by simple city characteristics, such as the city size or its "smartness".
sample of that is shown in Figure 1, where two almost identical destinations are suggested to follow completely Vehicular trafic is one of the critical factors afecting the diferent routes. Thus, the questions we study are: is this eficiency of cities and the quality of life of their citizens, variability of paths a peculiarity of Barcelona? Or is it a the economic eficiency of cities, and the environmental peculiarity of all/most large European cities? Is it limited impact of transportation. Nowadays, trafic optimization to carefully planned smart cities, or does it happen also is of particular relevance, especially in the current con- in less developed areas? Are there contextual factors that text where cities continue to expand in population and determine the phenomenon? density, impacting trafic management, pollution, and To tackle the questions above, we develop an analytical road safety. Eficient and sustainable road mobility is framework implementing the concept of path instability therefore essential to ensure that cities remain livable, – namely, a measure of how much small perturbations to competitive, and able to meet the needs of their residents. the destination of a trip change the best path to reach it
As urban mobility forms a complex phenomenon, it – and then apply it to evaluate empirically the presence is extremely important to understand how the travel in- and size of the phenomenon in several diferent cities. In frastructures and the city’s mobility needs combine, par- particular, we provide results both at a continental scale, ticularly whether the road network provides the correct comparing European capitals (some of which provide connections for smooth mass mobility. One recent line of good examples of very large and/or smart cities), and research deals with this aspect by assessing the reacha- at a regional scale, comparing the municipalities in an bility of city destinations in terms of eficient alternative Italian region (most of which are small and with a simple paths available, which is a measure of road network ro- mobility infrastructure). bustness to high trafic loads and resilience to unexpected Our results show that path instability is relatively comevents (road closures, accidents, extreme trafic for pub- mon, and the overall picture is quite complex. The phelic events, etc.). This work focuses on a related topic nomenon is not limited to a specific class of cities – e.g., that stems from an anecdotal observation: in the city of large cities, highly populated ones, smart cities, etc. – Barcelona, Spain, mobility navigators often provide very and, while some interesting correlations with features diferent paths to reach two very similar destinations. A and mobility aspects of the cities were found, a clear explanation of the factors leading to instability is still missing, requiring further research.
In the following sections, we review the relevant literature on the topic (Section 2), describe our approach (SecPublished in the Proceedings of the Workshops of the EDBT/ICDT 2024 Joint Conference (March 25-28, 2024), Paestum, Italy $ giuliano.cornacchia@phd.unipi.it (G. Cornacchia); mirco.nanni@isti.cnr.it (M. Nanni); fragrassi94@gmail.com (F. Grassi)Copyright © 2024 for this paper by its authors. Use permitted under Creative Commons License tion 3), present the experiments and results (Sections 4
Attribution 4.0 International (CC BY 4.0). and 5), and finally provide a discussion and conclusive remarks (Sections 6 and 7).
Road networks play a pivotal role in modern transportation systems, serving as the circulatory system that facilitates the movement of people and goods within urban landscapes. Understanding and optimizing trafic flow in these networks is a fundamental challenge in transportation research, with implications for eficiency, safety, and environmental sustainability.
Diferent works have focused on the topology and properties of road networks. Urban road networks are well-known to exhibit universal characteristics and scaleinvariant patterns despite cities’ diferent geographical and historical contexts [1]. For example, Barthélemy et al. [2] demonstrate how the evolution of many diferent transportation networks follows a simple universal mechanism. In [1], the authors explore the detour index (DI), defined as the ratio between the shortest distance through the road network and the Euclidean distance through the road network for various spatial variables, and discover universal properties.
A lot of research interest has then been applied to how to navigate road networks eficiently, exploiting the well-known road network characteristics. The shortest path is the most straightforward way for tracing the path from origin to destination in a road network [3, 4]. However, from a collective point of view, aggregating all individual fastest paths may increase trafic congestion and CO2 emissions [5, 6, 7, 8, 9]. A way to overcome this problem and to distribute the vehicles more evenly on the road network is to go beyond the shortest path using Alternative Routing (AR) algorithms [10] that provide a plurality of alternative paths between an origin and a destination location in a road network.
There are several ways to compute the alternatives. Edge-weight-based approaches compute the shortest paths iteratively, and at each iteration, they update the edge weights of the road network to compute alternative paths [10, 11, 12].
In contrast, Plateau-based methods generate alternative paths based on plateaus, i.e., common branches between the origin and destination shortest-path trees [13].
Chondrogiannis et al. [14] propose the -Shortest Paths with Limited Overlap (SPLO), seeking to recommend -alternative paths that are as short as possible and suficiently dissimilar. Chondrogiannis et al. [ 15] formalize the -Dissimilar Paths with Minimum Collective Length (DPML) providing paths suficiently dissimilar while having the lowest collective path length. Hacker et al. [16] propose -Most Diverse Near Shortest Paths (KMD) to recommend the set of near-shortest paths (based on a user-defined cost threshold) with the highest diversity.
AR solutions may be employed for the Trafic assignment (TA) task to allocate vehicle trips on a road network to minimize congestion and travel time [17]. In [18], the authors propose METIS, a one-shot TA algorithm that integrates an AR algorithm (-Most Diverse Near Shortest Paths [16]) into TA, showing how generating alternative routes may improve Trafic Assignment and reducing trafic negative externalities.
Our study focuses on an aspect of mobility within road networks closely related to alternative routing, aiming to understand the intrinsic tendency of a network to spontaneously induce some variability in the paths rather than trying to generate them artificially. Indeed, our generated OD pairs within the area of interest, the generation of the paths follow the traditional and simple Dijkstra algorithm shortest paths between the OD pairs, and the computafor shortest paths. We introduce the shortest path insta- tion of the Path Instability Index for the paths associated bility concept, quantifying the road network’s inclination with each OD. to present significantly diferent travel alternatives for slightly diferent trips. 3.2.1. OD Pairs Generation
3. Methods bility, we need to compute the Path Instability Index for several origin-destination pairs. Clearly, it is not possible This section details the procedure to analyse the shortest to analyse it between every possible OD pairs for compath instability within a road network. Path instability putational matters, hence, we need to generate a set of refers to a road network’s propensity to exhibit markedly OD pairs which are representative of a city’s road netdiferent route alternatives when the destination location work. We model a city’s road network as a directed graph is slightly changed. In this work, we consider the shortest = (, ) where the set of edges contains roads, and path as the path to reach a destination starting from an the set of nodes contains the intersections between origin. Understanding this phenomenon is crucial for roads. We downloaded the road network representation enhancing the reliability and eficiency of transportation for the geographical area of interest from OpenStreetMap systems. (OSM1).
To avoid introducing geographical bias in the sam3.1. Path Instability Index pling method, we generate a collection of origindestination pairs in which each pair (, ) ∈ is seTo assess the instability of the shortest path within an ur- lected through a uniform random process for both the ban environment, we introduce the Path Instability Index, origin and destination , while ensuring a minimum conceived as an analytical tool to measure and quantify distance between the generated points. the geographical variance among diferent routes. It is based on a set representation of routes, associating to a 3.2.2. Computing Path Perturbations route the sequence of road segments it traverses, and the Jaccard Index, widely used in the field of data science as a metric for similarity and dissimilarity between sets.
The Path Instability Index between two routes and is then defined as:
ture to quantify the tendency of a road network to provide very diferent travel alternatives for just slightly diferent trips, we need to create the variation of the sampled trips and assess its Path Instability Index .
First, we generate four OD variations for each OD pair (, ) ∈ by deterministically displacing the destination location towards the four cardinal points at a distance from the original position. We refer to these variations as (, ,) with x ∈ {N, S, E, W} denoting the displacement direction and representing the distance in meters from the original point .
Then, for every origin-destination (OD) pair (, ), we calculate the shortest path connecting and . Subsequently, for each variation (, ,) of (, ), we compute , the shortest path connecting and , in the road network.
(, ) = 1 − (, ) where and are represented by their corresponding set of road segments visited along the path. The Path Instability Index, like the Jaccard Index, ranges on a scale between 0 to 1. A value of (, ) equal to 0 means that the two routes and overlap, denoting complete path stability. Conversely, a value of 1 indicates that and do not have any common road segment between the two routes, showing total path instability. In summary, the closer the Path Instability Index is to 1, the greater the diference between the routes. 3.2. City Instability Index To eficiently analyze and quantify the shortest path insta- For each OD pair (, ) we now have four perturbed bility within an urban environment, studying the shortest paths , = {| ∈ {, , , }}. At this point, path instability between several origin-destination pairs we compare all pairs of perturbations through the Path (, ) within the road network is necessary. Such a pair, Instability Index, thus computing the multiset , = also denoted as OD pair, represents a trip within a mobil- {(, )| ∈ ,, ∈ ,, ̸= }. This reity demand. sults in a multiset of Path Instability Indexes =
The steps required to quantify the shortest path instability of a city comprise the generation and selection of 1https://www.openstreetmap.org/ ⋃︀(,)∈ , for the whole city. We aggregate the val- lected other relevant information about the route, such ues in this multiset either through a global average or as its length and expected travel time. through a box-plot distribution.
In this section we summarize the experimental setting Instability Index analysis on the European capitals and adopted to analyze the Path Instability Index across vari- the city of Barcelona, subsequently extending the analyous urban scenarios and two diferent geographical con- sis to the municipalities in Tuscany, Italy. As discussed texts. previously, the goal is to discover, highlight, and under
On the large geographical scale, we focus our study on stand the dynamics characterizing the presence of the European capitals (Figure 2(left)) plus Barcelona, since Instability phenomenon within diferent geographical it was the motivating example of the work. European contexts and to assess the possible influence that the colcapitals provide several examples of large and highly lected variables may have on the observed phenomenon. developed cities with complex trafic structures. On a smaller scale, we study the municipalities in Tuscany, 5.1. European Capitals and Barcelona Italy (Figure 2(right)). Most municipalities have a small city center, yet some of them cover also a significantly Figure 3 illustrates the distribution of the Path Instability large sub-urban area and have a complex road network. Index among European Capitals through box-plots sorted For both contexts, we obtain the road network repre- by descending average values, highlighting the particsentation for each geographical area of interest from ular case of Barcelona. As we expected, the results are OpenStreetMap. significantly heterogeneous. Also, only very few cities
Following our experimental strategy, for each urban lean towards shortest path stability, denoted by a value scenario, we generate N=10,000 OD-pairs having a mini- of close to 0, while most cities display a more prevalent mum distance of 500 meters, considering their displace- tendency towards instability in their shortest paths. ment towards the four cardinal points with a distance Confirming our initial intuition, Barcelona is indeed equal to 50 meters. among the top unstable-path cities, with instability val
To retrieve the routes between an origin location and ues up to 0.15 and extreme cases close to 0.4. Top cities a destination location , we utilize the OSMnx service, are quite heterogeneous in terms of size, including large built upon OpenStreetMap. Through this service, we ob- cases like Paris (ranked 3rd) and rather small ones like tain a path representing the shortest route to reach the Nicosia (ranked 4th). Similarly, some large and complex desired destination , starting from the specified origin cities like London, Rome, and Moskow are ranked at the location . Associated with the shortest path, we col- bottom, further suggesting that path instability cannot be simply attributed to size and road network complexity. of the Index’s behavior.
Analyzing the geographical position of cities (Fig- Since the road networks of some municipalities are ure 2(left)) we can see that most highest-instability ones too small to create a significant set of distinct OD pairs, are located in South-Western areas, with a prevalence of the analysis focused on a subset of 50 cases not afected cities on the sea. by the issue. Figure 4 shows the distribution of the Path
Additionally, looking at the inter-quartile range of Instability Index for the selected municipalities. boxes, we can observe that certain cities emerge as stabil- In contrast to the findings from the analysis of Euroity islands, having an Instability Index that is consistently pean capitals, most Tuscan cities show very low median low for most of the OD pairs and not just on average, values, close to zero for all but the top 6 ones. At the same e.g., London and Oslo; in contrast, cities such as Lisbon time, a larger portion of municipalities has inter-quartile (among the most unstable ones) and Stockholm (among ranges reaching 0.1, suggesting that the variability of the medium ones) demonstrate a wider dispersion, sug- outcomes for diferent trips in the same area (and thus gesting that instability greatly depends on which parts their dependence from the specific portion of the municof the city are involved in the trips. ipality involved) is even higher than the European-scale case. 5.2. Municipalities in Tuscany Geographically speaking (Figure 2(right)), we can identify a clear cluster of municipalities in the CentralThe objective of the second case study is to explore the Northern part of the region, approximately around the Path Instability Index, redirecting the analysis towards a Pisa-Florence line, which is the strongest communication smaller geographical scale scenario consisting of the mu- axis of the region. In addition, a few municipalities along nicipalities of Tuscany, an Italian region. This approach the coast emerged, including two of the top ones in terms intends to investigate the dynamics of the Instability In- of the Instability Index: Forte dei Marmi (ranked 1st) and dex in an environment characterized by varied urban cen- Viareggio (ranked 6th). ters that are relatively small and share a regional identity.
Such an approach enables a more nuanced understanding 5.3. Correlations
Index and its potential connections with other urban attributes, we analyzed the Pearson correlations between the index and two families of attributes: one is related to the general characteristics of the shortest paths generated and includes length and duration of the trip, the num- 6. Discussion ber of intersections and complex intersections (namely those connecting more than three roads), the number of Path Instability: a universal phenomenon. The shortone-way streets and turns performed; the other family est path instability phenomenon is not limited to our regards the road geometry and infrastructure, including motivating example of Barcelona, which indeed exhibits the number of intersections, one-way roads, bridges and high levels of instability, confirming our initial intuition, bike lanes in the city. but manifests universally, although with varying degrees.
The results, summarized in Table 1 for both case stud- The analysis performed among diferent European capies, show some interesting outcomes. First, at both Euro- itals reveals that path instability in urban pathways is pean and regional scales, the instability index is signifi- a common characteristic, irrespective of diferences in cantly negatively correlated to the length and duration road network size or urban planning patterns, suggestof the generated trips. Thus, longer paths appear to be ing that beyond architectural and urbanistic specificities, generally more stable than shorter ones. Second, all other there are mobility and planning dynamics that go beyond features have a smaller, negative correlation to instability geographical boundaries. Results on Tuscany also show at the European level, while they show a positive and that this phenomenon’s emergence is not linked to the typically much larger correlation at the regional level. ’smart city’ status, as it can be observed even in simple This highlights the fact that the two scales hide diferent realities such as the majority of regional municipalities. mechanics, and thus, their relations with the instability The geographical distribution of high instability cities index are widely diferent. This is also summarized in in South-Western European areas, particularly those on
city oneways -0.18 0.31
city bike lanes -0.32 0.32 the sea, raises interesting questions about the influence of likelihood of paths being perturbed and diversifying the coastal features on path instability. One potential reason available routes. In essence, the density of intersections for this phenomenon is that the radial growth of roads in emerges as a significant factor influencing the complex coastal cities may be constrained. This limitation could dynamics of path instability, fostering a more varied genresult in higher road concentrations with a prevalence of eration of perturbed paths. one-way roads, as there is limited space for expanding Diferent scales, diferent results. While less signifroads in both directions within the city. Consequently, icant than the two cases discussed above, the correlations when displacing the destination location towards one of between path instability and various other features are the four cardinal points, it may be assigned to a road that nevertheless not negligible. Yet, we observed that such is either not directly connected to the original ones or correlations have an opposite direction in the two geoeven going in the opposite direction, leading to a signifi- graphical scales analyzed (Europe vs. Tuscany), which cantly diferent route. requires further investigations. For instance, the number
Trip distance impacts Path Instability. The cor- of intersections, which has a strong positive correlation relations among the Path Instability Index and the trip with the instability index in Tuscany, has a weaker, neglength for the European capitals ( = − 0.76) and mu- ative correlation in Europe, suggesting that the ways nicipalities in Tuscany ( = − 0.49) suggest that longer intersections influence paths are completely diferent in paths are slightly less prone to instability or, as observed, the two cases. subject to instability with low values. All this evidence leads to the conclusion that the short
Longer trips exhibit greater stability, possibly due to est path instability is a complex phenomenon where the fact that they tend to flow into fast, long-range roads, many factors influence the results, and those identified such as highways and motorways, that represent the in this study only partially cover them. main part of the trip and remain unchanged when slightly perturbing the destination. In contrast, using such roads might not be convenient for short trips since reaching 7. Conclusion highways and fast connections usually requires deviations whose cost outbalances the faster travel speed. In this paper, we introduced path instability, a phenomenon that emerges from the road network structure staIbniltietyrsIencdteioxnesxhimibpitascat pPoastihtivIensctoarbreillaittyio.nTh(e =Pat0h.4I9n)- and is expected to significantly influence the network’s with the average number of intersections along paths capability to deal with urban trafic. The framework within municipalities in Tuscany. This implies that as we developed allowed us to check and analyze the phethe density of intersections in a road network increases, nomenon of cities of diferent natures – capitals of Europe there is a corresponding rise in path instability. In sim- vs. (small) regional municipalities – revealing some interpler terms, more intersections contribute to a greater esting factors but also a high variability across the two
by the Horizon Europe research and innovation programme under the funding scheme Green.Dat.AI, G.A. 101070416. groups and within each group.
The preliminary results obtained in this work open the door to other studies needed to fully understand the phenomenon of path instability, its relations with characteristics of the road network, and its potential impact on network eficiency. We believe that instability has strong links with the potential of road networks to generate eficient alternative routings for mobility demand in a city and, thus, to better sustain a heavily loaded trafic infrastructure. This kind of knowledge is expected to be valuable in the process of design of city layout and trafic infrastructures. We plan to pursue this direction, also studying its relations with urban planning aspects and the historical development of cities. [8] D. Pedreschi, L. Pappalardo, R. Baeza-Yates, A.
L. Barabasi, F. Dignum, V. Dignum, T. EliassiRad, F. Giannotti, J. Kertesz, A. Knott, Y. Ioannidis, P. Lukowicz, A. Passarella, A. S. Pentland, J. Shawe-Taylor, A. Vespignani, Social ai and the challenges of the human-ai ecosystem, 2023.
arXiv:2306.13723. [9] L. Pappalardo, E. Manley, V. Sekara, L. Alessandretti,
Future directions in human mobility science, Nature computational science 3 (2023) 588–600. [10] L. Li, M. Cheema, H. Lu, M. Ali, A. N. Toosi, Comparing alternative route planning techniques: A comparative user study on melbourne, dhaka and copenhagen road networks, IEEE Trans. Knowl.
Data Eng. 34 (2022) 5552–5557. [11] V. Akgün, E. Erkut, R. Batta, On finding dissimilar paths, European Journal of Operational Research 121 (2000) 232–246. URL: https://www.sciencedirect.com/science/article/pii/ S0377221799002143. doi:https://doi.org/10.
1016/S0377-2217(99)00214-3. [12] D. Cheng, O. Gkountouna, A. Züfle, D. Pfoser, [1] M. Lee, S. Cheon, S.-W. Son, M. J. Lee, S. Lee, Explor- C. Wenk, Shortest-path diversification through ing the relationship between the spatial distribution network penalization: A washington dc area case of roads and universal pattern of travel-route efi- study, in: Proceedings of the 12th ACM SIGSPAciency in urban road networks, Chaos, Solitons & TIAL International Workshop on Computational Fractals 174 (2023). doi:10.1016/j.chaos.2023. Transportation Science, IWCTS’19, Association for 113770. Computing Machinery, New York, NY, USA, 2019. [2] M. Barthélemy, A. Flammini, Modeling URL: https://doi.org/10.1145/3357000.3366137. urban street patterns, Phys. Rev. Lett. [13] C. V. I. T. Ltd., Choice routing, http://www.camvit. 100 (2008) 138702. URL: https://link.aps. com, 2005. org/doi/10.1103/PhysRevLett.100.138702. [14] T. Chondrogiannis, P. Bouros, J. Gamper, U. Leser, doi:10.1103/PhysRevLett.100.138702. D. B. Blumenthal, Finding k-shortest paths with [3] L. Wu, X. Xiao, D. Deng, G. Cong, A. D. Zhu, limited overlap, The VLDB Journal 29 (2020) 1023– S. Zhou, Shortest path and distance queries 1047. doi:10.1007/s00778-020-00604-x. on road networks: An experimental evaluation [15] T. Chondrogiannis, P. Bouros, J. Gamper, U. Leser, (2012). URL: https://arxiv.org/abs/1201.6564. doi:10. D. B. Blumenthal, Finding k-dissimilar paths with 48550/ARXIV.1201.6564. minimum collective length, SIGSPATIAL ’18, As[4] G. Cornacchia, M. Nanni, D. Pedreschi, L. Pap- sociation for Computing Machinery, New York, palardo, The efects of route randomization NY, USA, 2018, p. 404–407. doi:10.1145/3274895. on urban emissions, SUMO Conference Pro- 3274903. ceedings 4 (2023) 75–87. URL: https://www. [16] C. Häcker, P. Bouros, T. Chondrogiannis, E. Althaus, tib-op.org/ojs/index.php/scp/article/view/217. Most diverse near-shortest paths, in: ACM SIGSPAdoi:10.52825/scp.v4i.217. TIAL GIS, 2021, p. 229–239. [5] T. Roughgarden, E. Tardos, How bad is selfish rout- [17] M. E. Campbell, Route selection and trafic assigning?, Journal of the ACM 49 (2002). doi:10.1145/ ment: A compendium of correspondence relating 506147.506153. to a suggested technique, Highway Research Board, [6] G. Cornacchia, M. Böhm, G. Mauro, M. Nanni, D. Pe- 1950.
dreschi, L. Pappalardo, How routing strategies im- [18] G. Cornacchia, M. Nanni, L. Pappalardo, One-shot pact urban emissions, in: Proceedings of the 30th In- trafic assignment with forward-looking penalizaternational Conference on Advances in Geographic tion, SIGSPATIAL ’23, Association for Computing Information Systems, 2022, pp. 1–4. Machinery, New York, NY, USA, 2023. URL: https: [7] G. Cornacchia, M. Nanni, D. Pedreschi, L. Pap- //doi.org/10.1145/3589132.3625637. doi:10.1145/ palardo, Navigation services and urban sustainabil- 3589132.3625637. ity, Fluctuation and Noise Letters (2023) 2450016.