=Paper=
{{Paper
|id=Vol-3651/BMDA_paper8
|storemode=property
|title=Barcelona Effect: Studying the Instability of Shortest Paths in Urban Settings
|pdfUrl=https://ceur-ws.org/Vol-3651/BMDA-8.pdf
|volume=Vol-3651
|authors=Giuliano Cornacchia,Mirco Nanni,Francesco Grassi
|dblpUrl=https://dblp.org/rec/conf/edbt/CornacchiaNG24
}}
==Barcelona Effect: Studying the Instability of Shortest Paths in Urban Settings==
https://ceur-ws.org/Vol-3651/BMDA-8.pdf
Barcelona Effect: Studying the Instability of Shortest Paths
in Urban Settings
Giuliano Cornacchia1,2 , Mirco Nanni2 and Francesco Grassi1
1
University of Pisa, Pisa, Italy
2
ISTI-CNR, Pisa, Italy
Abstract
Human mobility is one of the important factors affecting the efficiency 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
traffic in an optimal way, the structure of cities across different 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) traffic efficiency. 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 different travel alternatives for
just slightly different trips. A notable case of that, which stimulated this research, is the city of Barcelona, where, apparently,
reaching very close destinations might require very different routes. The concept is implemented and applied to two case
studies at different 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".
Keywords
Urban mobility, Shortest path instability, Road network efficiency
1. Introduction sample of that is shown in Figure 1, where two almost
identical destinations are suggested to follow completely
Vehicular traffic is one of the critical factors affecting the different routes. Thus, the questions we study are: is this
efficiency of cities and the quality of life of their citizens, variability of paths a peculiarity of Barcelona? Or is it a
the economic efficiency of cities, and the environmental peculiarity of all/most large European cities? Is it limited
impact of transportation. Nowadays, traffic 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 traffic management, pollution, and To tackle the questions above, we develop an analytical
road safety. Efficient 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 different 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 efficient 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 traffic loads and resilience to unexpected Our results show that path instability is relatively com-
events (road closures, accidents, extreme traffic for pub- mon, and the overall picture is quite complex. The phe-
lic 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
different paths to reach two very similar destinations. A and mobility aspects of the cities were found, a clear
Published in the Proceedings of the Workshops of the EDBT/ICDT 2024
explanation of the factors leading to instability is still
Joint Conference (March 25-28, 2024), Paestum, Italy missing, requiring further research.
$ giuliano.cornacchia@phd.unipi.it (G. Cornacchia); In the following sections, we review the relevant liter-
mirco.nanni@isti.cnr.it (M. Nanni); fragrassi94@gmail.com ature on the topic (Section 2), describe our approach (Sec-
(F. Grassi) tion 3), present the experiments and results (Sections 4
Copyright © 2024 for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0).
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
Figure 1: Example of two almost identical origin-destination pairs (green and red markers) that lead to different shortest
paths (routes generated by OpenStreetMap).
and 5), and finally provide a discussion and conclusive a plurality of alternative paths between an origin and a
remarks (Sections 6 and 7). destination location in a road network.
There are several ways to compute the alternatives.
Edge-weight-based approaches compute the shortest
2. Related Work paths iteratively, and at each iteration, they update the
edge weights of the road network to compute 𝑘 alterna-
Road networks play a pivotal role in modern transporta-
tive paths [10, 11, 12].
tion systems, serving as the circulatory system that facil-
In contrast, Plateau-based methods generate alterna-
itates the movement of people and goods within urban
tive paths based on plateaus, i.e., common branches be-
landscapes. Understanding and optimizing traffic flow in
tween the origin and destination shortest-path trees [13].
these networks is a fundamental challenge in transporta-
Chondrogiannis et al. [14] propose the 𝑘-Shortest
tion research, with implications for efficiency, safety, and
Paths with Limited Overlap (𝑘SPLO), seeking to recom-
environmental sustainability.
mend 𝑘-alternative paths that are as short as possible
Different works have focused on the topology and
and sufficiently dissimilar. Chondrogiannis et al. [15] for-
properties of road networks. Urban road networks are
malize the 𝑘-Dissimilar Paths with Minimum Collective
well-known to exhibit universal characteristics and scale-
Length (𝑘DPML) providing 𝑘 paths sufficiently dissimilar
invariant patterns despite cities’ different geographical
while having the lowest collective path length. Hacker
and historical contexts [1]. For example, Barthélemy et
et al. [16] propose 𝑘-Most Diverse Near Shortest Paths
al. [2] demonstrate how the evolution of many differ-
(KMD) to recommend the set of 𝑘 near-shortest paths
ent transportation networks follows a simple universal
(based on a user-defined cost threshold) with the highest
mechanism. In [1], the authors explore the detour index
diversity.
(DI), defined as the ratio between the shortest distance
AR solutions may be employed for the Traffic assign-
through the road network and the Euclidean distance
ment (TA) task to allocate vehicle trips on a road network
through the road network for various spatial variables,
to minimize congestion and travel time [17]. In [18], the
and discover universal properties.
authors propose METIS, a one-shot TA algorithm that in-
A lot of research interest has then been applied to
tegrates an AR algorithm (𝑘-Most Diverse Near Shortest
how to navigate road networks efficiently, exploiting the
Paths [16]) into TA, showing how generating alternative
well-known road network characteristics. The shortest
routes may improve Traffic Assignment and reducing
path is the most straightforward way for tracing the
traffic negative externalities.
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 Position of our work
and CO2 emissions [5, 6, 7, 8, 9]. A way to overcome this Our study focuses on an aspect of mobility within road
problem and to distribute the vehicles more evenly on networks closely related to alternative routing, aiming to
the road network is to go beyond the shortest path using understand the intrinsic tendency of a network to sponta-
Alternative Routing (AR) algorithms [10] that provide neously 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 computa-
for 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 different travel alternatives for
slightly different trips. 3.2.1. OD Pairs Generation
To have an accurate idea of a city’s shortest path insta-
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 com-
path 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 net-
different 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 efficiency of transportation for the geographical area of interest from OpenStreetMap
systems. (OSM1 ).
To avoid introducing geographical bias in the sam-
3.1. Path Instability Index pling method, we generate a collection 𝐷 of 𝑁 origin-
destination pairs in which each pair (𝑜, 𝑑) ∈ 𝐷 is se-
To 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 different 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 To compute the instability of the whole road infrastruc-
a metric for similarity and dissimilarity between sets. ture to quantify the tendency of a road network to provide
The Path Instability Index 𝐼 between two routes 𝐴 and very different travel alternatives for just slightly different
𝐵 is then defined as: trips, we need to create the variation of the sampled trips
and assess its Path Instability Index 𝐼.
𝐼(𝐴, 𝐵) = 1 − 𝐽(𝐴, 𝐵) First, we generate four OD variations for each OD pair
(𝑜, 𝑑) ∈ 𝐷 by deterministically displacing the destination
where 𝐴 and 𝐵 are represented by their corresponding location 𝑑 towards the four cardinal points at a distance
set of road segments visited along the path. The Path 𝑟 from the original position. We refer to these variations
Instability Index, like the Jaccard Index, ranges on a scale as (𝑜, 𝑑𝑥,𝑟 ) with x ∈ {N, S, E, W} denoting the displace-
between 0 to 1. A value of 𝐼(𝐴, 𝐵) equal to 0 means that ment direction and 𝑟 representing the distance in meters
the two routes 𝐴 and 𝐵 overlap, denoting complete path from the original point 𝑑.
stability. Conversely, a value of 1 indicates that 𝐴 and 𝐵 Then, for every origin-destination (OD) pair (𝑜, 𝑑), we
do not have any common road segment between the two calculate the shortest path 𝑝 connecting 𝑜 and 𝑑. Subse-
routes, showing total path instability. In summary, the quently, for each variation (𝑜, 𝑑𝑥,𝑟 ) of (𝑜, 𝑑), we compute
closer the Path Instability Index is to 1, the greater the 𝑝𝑥 , the shortest path connecting 𝑜 and 𝑑𝑥,𝑟 in the road
difference between the routes. network.
3.2. City Instability Index 3.2.3. City-level Aggregation of Instability Index
To efficiently 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 re-
ity demand. sults in a multiset of Path Instability Indexes 𝑃𝐷 =
The steps required to quantify the shortest path insta-
bility of a city comprise the generation and selection of 1
https://www.openstreetmap.org/
Figure 2: Geographical areas considered: European capitals (plus Barcelona in red, left) and Municipalities of Tuscany, Italy
(right). Municipalities and cities highlighted in yellow correspond to the top highest Path Instability Index values.
(𝑜,𝑑)∈𝐷 𝐼𝑜,𝑑 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.
5. Results
4. Experimental Settings
In this section, we examine and discuss the results of the
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 analy-
ous urban scenarios and two different 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 different geographical
it was the motivating example of the work. European contexts and to assess the possible influence that the col-
capitals provide several examples of large and highly lected variables may have on the observed phenomenon.
developed cities with complex traffic 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 partic-
sentation 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
Figure 3: Path Instability Index distribution across European Capitals, sorted in descending order by their average Path
Instability Index. The highlighted red box plot specifically represents Barcelona, Spain.
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 affected
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 Euro-
ity 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 different trips in the same area (and thus
gesting that instability greatly depends on which parts their dependence from the specific portion of the munic-
of 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 Central-
The 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
Figure 4: Path Instability Index distribution across municipalities in Tuscany, sorted in descending order by their average
Path Instability Index, which is also represented through bar colors (cold=low, hot=high).
5.3. Correlations Figure 5, where average trip lengths and number of in-
tersections are plotted together with the instability index
To unveil the underlying dynamics of the Path Instability
at the two scales: it is clear how the trip length has a
Index and its potential connections with other urban at-
similar behavior in the two scenarios, while the number
tributes, we analyzed the Pearson correlations between
of intersections is diametrally opposite.
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 short-
one-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 different European cap-
ies, 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 differences in
cantly negatively correlated to the length and duration road network size or urban planning patterns, suggest-
of 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 different 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 different. This is also summarized in in South-Western European areas, particularly those on
Area trip trip num. of oneway complex trip city city city city
length duration inters. streets inters. turns inters. oneways bridges bike lanes
Europe -0.76 -0.76 -0.35 -0.32 -0.29 -0.33 -0.42 -0.18 -0.35 -0.32
Tuscany -0.49 -0.49 0.49 0.52 0.54 0.61 0.27 0.31 0.05 0.32
Table 1
Correlations (Pearson’s coefficients) between Path Instability and various trip and road network features.
European cities Tuscany
PII vs. length
PII vs. intersect.
Figure 5: Relation between trips length (red) and number of visited intersections (green) vs. Path Instability Index (blue).
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 gen-
result in higher road concentrations with a prevalence of eration of perturbed paths.
one-way roads, as there is limited space for expanding Different scales, different results. While less signif-
roads 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 geo-
even going in the opposite direction, leading to a signifi- graphical scales analyzed (Europe vs. Tuscany), which
cantly different 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, neg-
length 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 different 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 devia-
In this paper, we introduced path instability, a phe-
tions whose cost outbalances the faster travel speed.
nomenon that emerges from the road network structure
Intersections impact Path Instability. The Path In-
and is expected to significantly influence the network’s
stability Index exhibits a positive correlation (𝑟 = 0.49)
capability to deal with urban traffic. The framework
with the average number of intersections along paths
we developed allowed us to check and analyze the phe-
within municipalities in Tuscany. This implies that as
nomenon of cities of different natures – capitals of Europe
the density of intersections in a road network increases,
vs. (small) regional municipalities – revealing some inter-
there is a corresponding rise in path instability. In sim-
esting factors but also a high variability across the two
pler terms, more intersections contribute to a greater
groups and within each group. [8] D. Pedreschi, L. Pappalardo, R. Baeza-Yates, A.-
The preliminary results obtained in this work open L. Barabasi, F. Dignum, V. Dignum, T. Eliassi-
the door to other studies needed to fully understand the Rad, F. Giannotti, J. Kertesz, A. Knott, Y. Ioan-
phenomenon of path instability, its relations with charac- nidis, P. Lukowicz, A. Passarella, A. S. Pentland,
teristics of the road network, and its potential impact on J. Shawe-Taylor, A. Vespignani, Social ai and
network efficiency. We believe that instability has strong the challenges of the human-ai ecosystem, 2023.
links with the potential of road networks to generate arXiv:2306.13723.
efficient alternative routings for mobility demand in a [9] L. Pappalardo, E. Manley, V. Sekara, L. Alessandretti,
city and, thus, to better sustain a heavily loaded traffic Future directions in human mobility science, Na-
infrastructure. This kind of knowledge is expected to be ture computational science 3 (2023) 588–600.
valuable in the process of design of city layout and traffic [10] L. Li, M. Cheema, H. Lu, M. Ali, A. N. Toosi, Com-
infrastructures. We plan to pursue this direction, also paring alternative route planning techniques: A
studying its relations with urban planning aspects and comparative user study on melbourne, dhaka and
the historical development of cities. copenhagen road networks, IEEE Trans. Knowl.
Data Eng. 34 (2022) 5552–5557.
Acknowledgments. This work was partially funded
[11] V. Akgün, E. Erkut, R. Batta, On finding
by the Horizon Europe research and innovation pro-
dissimilar paths, European Journal of Op-
gramme under the funding scheme Green.Dat.AI, G.A.
erational Research 121 (2000) 232–246. URL:
101070416.
https://www.sciencedirect.com/science/article/pii/
S0377221799002143. doi:https://doi.org/10.
References 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 effi- study, in: Proceedings of the 12th ACM SIGSPA-
ciency 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 effects 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 SIGSPA-
doi: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 traffic assign-
ing?, 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- traffic assignment with forward-looking penaliza-
ternational 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.