Vehicular traffic is one of the critical factors affecting the efficiency of cities and the quality of life of their citizens, the economic efficiency of cities, and the environmental impact of transportation. Nowadays, traffic optimization is of particular relevance, especially in the current context where cities continue to expand in population and density, impacting traffic management, pollution, and road safety. Efficient and sustainable road mobility is therefore essential to ensure that cities remain livable, competitive, and able to meet the needs of their residents.
As urban mobility forms a complex phenomenon, it is extremely important to understand how the travel infrastructures and the city's mobility needs combine, particularly whether the road network provides the correct connections for smooth mass mobility. One recent line of research deals with this aspect by assessing the reachability of city destinations in terms of efficient alternative paths available, which is a measure of road network robustness to high traffic loads and resilience to unexpected events (road closures, accidents, extreme traffic for public events, etc.). This work focuses on a related topic that stems from an anecdotal observation: in the city of Barcelona, Spain, mobility navigators often provide very different paths to reach two very similar destinations. A sample of that is shown in Figure 1, where two almost identical destinations are suggested to follow completely different routes. Thus, the questions we study are: is this variability of paths a peculiarity of Barcelona? Or is it a peculiarity of all/most large European cities? Is it limited to carefully planned smart cities, or does it happen also in less developed areas? Are there contextual factors that determine the phenomenon?
To tackle the questions above, we develop an analytical framework implementing the concept of path instability -namely, a measure of how much small perturbations to the destination of a trip change the best path to reach it -and then apply it to evaluate empirically the presence and size of the phenomenon in several different cities. In particular, we provide results both at a continental scale, comparing European capitals (some of which provide good examples of very large and/or smart cities), and at a regional scale, comparing the municipalities in an Italian region (most of which are small and with a simple mobility infrastructure).
Our results show that path instability is relatively common, and the overall picture is quite complex. The phenomenon is not limited to a specific class of cities -e.g., large cities, highly populated ones, smart cities, etc.and, while some interesting correlations with features 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 (Section 3), present the experiments and results (Sections 4
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 traffic flow in these networks is a fundamental challenge in transportation research, with implications for efficiency, safety, and environmental sustainability.
Different 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' different geographical and historical contexts [1]. For example, BarthΓ©lemy et al. [2] demonstrate how the evolution of many different 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 efficiently, 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 traffic 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 sufficiently dissimilar. Chondrogiannis et al. [15] formalize the π-Dissimilar Paths with Minimum Collective Length (πDPML) providing π paths sufficiently 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 Traffic 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 Traffic Assignment and reducing traffic 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 paths follow the traditional and simple Dijkstra algorithm for shortest paths. We introduce the shortest path instability concept, quantifying the road network's inclination to present significantly different travel alternatives for slightly different trips.
This section details the procedure to analyse the shortest path instability within a road network. Path instability refers to a road network's propensity to exhibit markedly different route alternatives when the destination location is slightly changed. In this work, we consider the shortest path as the path to reach a destination starting from an origin. Understanding this phenomenon is crucial for enhancing the reliability and efficiency of transportation systems.
To assess the instability of the shortest path within an urban environment, we introduce the Path Instability Index, conceived as an analytical tool to measure and quantify the geographical variance among different routes. It is based on a set representation of routes, associating to a 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:
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 difference between the routes.
To efficiently analyze and quantify the shortest path instability within an urban environment, studying the shortest path instability between several origin-destination pairs (π, π) within the road network is necessary. Such a pair, also denoted as OD pair, represents a trip within a mobility demand.
The steps required to quantify the shortest path instability of a city comprise the generation and selection of OD pairs within the area of interest, the generation of the shortest paths between the OD pairs, and the computation of the Path Instability Index for the paths associated with each OD.
To have an accurate idea of a city's shortest path instability, we need to compute the Path Instability Index for several origin-destination pairs. Clearly, it is not possible to analyse it between every possible OD pairs for computational matters, hence, we need to generate a set of OD pairs which are representative of a city's road network. We model a city's road network as a directed graph πΊ = (π, πΈ) where the set of edges πΈ contains roads, and the set of nodes π contains the intersections between roads. We downloaded the road network representation for the geographical area of interest from OpenStreetMap (OSM1 ).
To avoid introducing geographical bias in the sampling method, we generate a collection π· of π origindestination pairs in which each pair (π, π) β π· is selected through a uniform random process for both the origin π and destination π, while ensuring a minimum distance πΏ between the generated points.
To compute the instability of the whole road infrastructure to quantify the tendency of a road network to provide very different travel alternatives for just slightly different 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.
For each OD pair (π, π) we now have four perturbed paths π π,π = {ππ₯|π₯ β {π, π, πΈ, π }}. At this point, we compare all pairs of perturbations through the Path Instability Index, thus computing the multiset πΌ π,π = {πΌ(ππ₯, ππ¦)|ππ₯ β π π,π , π₯π¦ β π π,π , π₯ ΜΈ = π¦}. This results in a multiset of Path Instability Indexes ππ· =
(π,π)βπ· πΌ π,π for the whole city. We aggregate the values in this multiset either through a global average or through a box-plot distribution.
In this section we summarize the experimental setting adopted to analyze the Path Instability Index across various urban scenarios and two different geographical contexts.
On the large geographical scale, we focus our study on European capitals (Figure 2(left)) plus Barcelona, since it was the motivating example of the work. European capitals provide several examples of large and highly developed cities with complex traffic structures. On a smaller scale, we study the municipalities in Tuscany, Italy (Figure 2(right)). Most municipalities have a small city center, yet some of them cover also a significantly large sub-urban area and have a complex road network. For both contexts, we obtain the road network representation for each geographical area of interest from OpenStreetMap.
Following our experimental strategy, for each urban scenario, we generate N=10,000 OD-pairs having a minimum distance πΏ of 500 meters, considering their displacement towards the four cardinal points with a distance π equal to 50 meters.
To retrieve the routes between an origin location π and a destination location π, we utilize the OSMnx service, built upon OpenStreetMap. Through this service, we obtain a path π representing the shortest route to reach the desired destination π, starting from the specified origin location π. Associated with the shortest path, we col-lected other relevant information about the route, such as its length and expected travel time.
In this section, we examine and discuss the results of the Instability Index analysis on the European capitals and the city of Barcelona, subsequently extending the analysis to the municipalities in Tuscany, Italy. As discussed previously, the goal is to discover, highlight, and understand the dynamics characterizing the presence of the Instability phenomenon within different geographical contexts and to assess the possible influence that the collected variables may have on the observed phenomenon.
Figure 3 illustrates the distribution of the Path Instability Index among European Capitals through box-plots sorted by descending average values, highlighting the particular case of Barcelona. As we expected, the results are significantly heterogeneous. Also, only very few cities lean towards shortest path stability, denoted by a value of πΌ close to 0, while most cities display a more prevalent tendency towards instability in their shortest paths.
Confirming our initial intuition, Barcelona is indeed among the top unstable-path cities, with instability values up to 0.15 and extreme cases close to 0.4. Top cities are quite heterogeneous in terms of size, including large cases like Paris (ranked 3rd) and rather small ones like Nicosia (ranked 4th). Similarly, some large and complex cities like London, Rome, and Moskow are ranked at the bottom, further suggesting that path instability cannot be Additionally, looking at the inter-quartile range of boxes, we can observe that certain cities emerge as stability islands, having an Instability Index that is consistently low for most of the OD pairs and not just on average, e.g., London and Oslo; in contrast, cities such as Lisbon (among the most unstable ones) and Stockholm (among the medium ones) demonstrate a wider dispersion, suggesting that instability greatly depends on which parts of the city are involved in the trips.
The objective of the second case study is to explore the Path Instability Index, redirecting the analysis towards a smaller geographical scale scenario consisting of the municipalities of Tuscany, an Italian region. This approach intends to investigate the dynamics of the Instability Index in an environment characterized by varied urban centers that are relatively small and share a regional identity. Such an approach enables a more nuanced understanding of the Index's behavior.
Since the road networks of some municipalities are too small to create a significant set of distinct OD pairs, the analysis focused on a subset of 50 cases not affected by the issue. Figure 4 shows the distribution of the Path Instability Index for the selected municipalities.
In contrast to the findings from the analysis of European capitals, most Tuscan cities show very low median values, close to zero for all but the top 6 ones. At the same time, a larger portion of municipalities has inter-quartile ranges reaching 0.1, suggesting that the variability of outcomes for different trips in the same area (and thus their dependence from the specific portion of the municipality involved) is even higher than the European-scale case.
Geographically speaking (Figure 2(right)), we can identify a clear cluster of municipalities in the Central-Northern part of the region, approximately around the Pisa-Florence line, which is the strongest communication axis of the region. In addition, a few municipalities along the coast emerged, including two of the top ones in terms of the Instability Index: Forte dei Marmi (ranked 1st) and Viareggio (ranked 6th).
To unveil the underlying dynamics of the Path Instability 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 number of intersections and complex intersections (namely those connecting more than three roads), the number of one-way streets and turns performed; the other family regards the road geometry and infrastructure, including the number of intersections, one-way roads, bridges and bike lanes in the city.
The results, summarized in Table 1 for both case studies, show some interesting outcomes. First, at both European and regional scales, the instability index is significantly negatively correlated to the length and duration of the generated trips. Thus, longer paths appear to be generally more stable than shorter ones. Second, all other features have a smaller, negative correlation to instability at the European level, while they show a positive and typically much larger correlation at the regional level. This highlights the fact that the two scales hide different mechanics, and thus, their relations with the instability index are widely different. This is also summarized in Figure 5, where average trip lengths and number of intersections are plotted together with the instability index at the two scales: it is clear how the trip length has a similar behavior in the two scenarios, while the number of intersections is diametrally opposite.
Path Instability: a universal phenomenon. The shortest path instability phenomenon is not limited to our motivating example of Barcelona, which indeed exhibits high levels of instability, confirming our initial intuition, but manifests universally, although with varying degrees. The analysis performed among different European capitals reveals that path instability in urban pathways is a common characteristic, irrespective of differences in road network size or urban planning patterns, suggesting that beyond architectural and urbanistic specificities, there are mobility and planning dynamics that go beyond geographical boundaries. Results on Tuscany also show that this phenomenon's emergence is not linked to the 'smart city' status, as it can be observed even in simple realities such as the majority of regional municipalities.
The the sea, raises interesting questions about the influence of coastal features on path instability. One potential reason for this phenomenon is that the radial growth of roads in coastal cities may be constrained. This limitation could result in higher road concentrations with a prevalence of one-way roads, as there is limited space for expanding roads in both directions within the city. Consequently, when displacing the destination location towards one of the four cardinal points, it may be assigned to a road that is either not directly connected to the original ones or even going in the opposite direction, leading to a significantly different route.
Trip distance impacts Path Instability. The correlations among the Path Instability Index and the trip length for the European capitals (π = β0.76) and municipalities in Tuscany (π = β0.49) suggest that longer paths are slightly less prone to instability or, as observed, subject to instability with low values.
Longer trips exhibit greater stability, possibly due to the fact that they tend to flow into fast, long-range roads, such as highways and motorways, that represent the 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 highways and fast connections usually requires deviations whose cost outbalances the faster travel speed.
Intersections impact Path Instability. The Path Instability Index exhibits a positive correlation (π = 0.49) with the average number of intersections along paths within municipalities in Tuscany. This implies that as the density of intersections in a road network increases, there is a corresponding rise in path instability. In simpler terms, more intersections contribute to a greater likelihood of paths being perturbed and diversifying the available routes. In essence, the density of intersections emerges as a significant factor influencing the complex dynamics of path instability, fostering a more varied generation of perturbed paths.
Different scales, different results. While less significant than the two cases discussed above, the correlations between path instability and various other features are nevertheless not negligible. Yet, we observed that such correlations have an opposite direction in the two geographical scales analyzed (Europe vs. Tuscany), which requires further investigations. For instance, the number of intersections, which has a strong positive correlation with the instability index in Tuscany, has a weaker, negative correlation in Europe, suggesting that the ways intersections influence paths are completely different in the two cases.
All this evidence leads to the conclusion that the shortest path instability is a complex phenomenon where many factors influence the results, and those identified in this study only partially cover them.
In this paper, we introduced path instability, a phenomenon that emerges from the road network structure and is expected to significantly influence the network's capability to deal with urban traffic. The framework we developed allowed us to check and analyze the phenomenon of cities of different natures -capitals of Europe vs. (small) regional municipalities -revealing some interesting factors but also a high variability across the two 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 efficiency. We believe that instability has strong links with the potential of road networks to generate efficient alternative routings for mobility demand in a city and, thus, to better sustain a heavily loaded traffic infrastructure. This kind of knowledge is expected to be valuable in the process of design of city layout and traffic infrastructures. We plan to pursue this direction, also studying its relations with urban planning aspects and the historical development of cities.
Acknowledgments. This work was partially funded by the Horizon Europe research and innovation programme under the funding scheme Green.Dat.AI, G.A. 101070416.