1 Introduction

Although street networks appear to be physically robust, intentional disruption can reduce their performance. To evaluate the reliability of a street network under extreme conditions, it is important to know the best possible performance of the network before and after a disruption. To determine this optimal performance of a street network, we solve the following planning problem. Given is a directed graph with arcs that represent street segments and nodes that represent intersections. Some nodes of the network act as origin or destination nodes. A predetermined amount of traffic must flow from each origin node to each destination node. Every arc of the graph is associated with a piecewise linear and convex function that determines the cost for a given amount of traffic. The goal is to determine the flow of traffic from origin to destination nodes such that total traffic cost is minimized. The resilience of a network can then be evaluated by comparing the total cost of traffic before and after the disruption.

The literature on street network reliability analysis can be roughly divided into two categories. The first category comprises approaches that identify vulnerabilities by analyzing the topology of the street network. Demšar et al. [6] use topological measures such as centrality and betweenness to identify critical nodes or arcs of a street network. They study the urban street network of the Helsinki Metropolitan Area in Finland. Duan and Lu [7] also analyze the robustness of street networks of six cities based on topological measures. They find that the level of granularity at which the network is represented has a strong impact on the identification of critical elements. A simplified representation of a street network could therefore lead to inaccurate conclusions. Jenelius and Mattsson [10] propose a grid-based method to identify areas in the network that are particularly vulnerable to large disruptions such as floods or heavy snowfall. They applied the method to a simplified representation of the Swedish street network. The second category comprises approaches that use optimization techniques to study the robustness of street networks. Brown et al. [5] propose bilevel and trilevel optimization models to identify vulnerabilities in critical infrastructure. Due to the computational complexity of these models, they are only applicable to small networks. Bell et al. [3] consider the problem of how to use a street network if information on several disruption scenarios is available. They present numerical results for an example that is based on the central London street network. Matisziw and Murray [13] propose an integer programming formulation for identifying important links in a truck transport network of Ohio, USA. Lou and Zhang [12] use mathematical programming to determine resilient transport networks under random and targeted attacks. Due to the computational complexity of the approaches in the second category, they are only applicable to relatively small street networks.

In this chapter, we propose an optimization-based decision support system that measures the resilience of a street network against user-defined disruptions. In contrast to existing optimization-based approaches, the proposed decision support system is applicable to nation-wide street networks. The system consists of a graph construction tool that transforms OpenStreetMap data into a directed graph, a simple traffic estimator that defines the traffic volume between origin-destination pairs, and a linear programming formulation that solves the above described planning problem and thus determines a minimum cost traffic flow from origin to destination nodes.

We used the proposed decision support system to analyze real-world street networks in Switzerland. For city-wide street networks, optimal traffic flows can be determined within seconds. The running time for large-scale networks increases considerably with the number of origin-destination pairs. Nevertheless, we were able to determine an optimal traffic flow for the entire Swiss street network with 380 origin-destination pairs.

The chapter is structured as follows. In Sect. 2, we describe the planning problem in detail. In Sect. 3, we describe how OpenStreetMap data is transformed into a directed graph. In Sect. 4, we show a simple method for estimating the traffic between origin-destination nodes. In Sect. 5, we introduce the linear programming formulation. In Sect. 6, we report the computational results. In Sect. 7, we conclude the chapter and provide some directions for future research.

2 Planning Problem

Given is a directed graph with arcs that represent street segments and nodes that represent intersections. Different types of traffic flow through this network. For example, one could differentiate between commercial traffic (trucks and coaches) and private traffic (cars). Some traffic types might not be allowed to traverse specific arcs of the street network (e.g., trucks are not allowed on residential streets). Some nodes of the graph represent origin nodes whereas others represent destination nodes. Traffic flows from origin nodes through the graph to destination nodes. Traffic matrices specify for each traffic type and each origin-destination pair the number of vehicles that flow from the respective origin node to the corresponding destination node. The numbers in the traffic matrices refer to a specific planning horizon which is typically a day. Every arc of the graph is associated with a piecewise linear and convex function that determines the cost for a given amount of traffic. For example, one could specify a piecewise linear function with two line segments for an arc such that the first 90,000 vehicles that traverse this arc within the planning horizon contribute 0.5 Swiss francs per vehicle and kilometer to total cost, whereas every additional vehicle contributes 50 Swiss francs per kilometer. The goal is to find the cheapest possible way to send each type of traffic from origin to destination nodes. This problem corresponds to a multi-commodity network flow problem with piecewise linear and convex costs.

3 Construction of Graph

An important component of the proposed decision support system is the graph that represents the street network. We suggest to use the Python package OSMnx [4] that retrieves spatial geometries from OpenStreetMap [14] and automatically converts them into a directed graph. The spatial geometries can be retrieved for a specific place, i.e., a city, a region or an entire country. Note that the retrieval of the OSM data for an entire country and the respective graph construction requires considerable running time and memory, especially when the option to include bikable and walkable paths is selected. We therefore suggest to include only drivable street types. Nodes and arcs in the directed graph are associated with several attributes. Tables 1 and 2 list some of these attributes for nodes and arcs, respectively.

Table 1 Node attributes
Full size table
Table 2 Arc attributes
Full size table

The attribute highway is useful to control the complexity of the graph. For example, it is possible to represent only arcs whose highway attribute value is either motorway or motorway_link by removing all arcs with other highway attribute values. The OSMnx package also provides a function to eliminate isolated nodes after the removal of a subset of arcs. Figure 1 shows the directed graph that represents the drivable street network of the city of Bern (Switzerland).

Fig. 1
figure 1

Drivable street network of Bern (Switzerland) represented as a graph

Full size image

The motorway segments that lie within the shaded area of Fig. 1 are enlarged in Fig. 2. The magnification suggests that the graph not only contains nodes to represent intersections, but also a large number of nodes that approximate the curvature of the streets.

Fig. 2
figure 2

Close-up of highlighted motorway segments

Full size image

The OSMnx package provides a function to remove those nodes while keeping the information on the curvature of the streets. Figure 3 shows the simplified representation of the graph visualized in Fig. 2.

Fig. 3
figure 3

Close-up of simplified graph representation

Full size image

Finally, we add dummy nodes that represent origins (origin nodes) and destinations (destination nodes) of traffic flow. Origin nodes are connected to the rest of the graph by introducing arcs from the origin nodes to other nodes of the graph that are within close proximity of the origin nodes. Destination nodes are connected to the rest of the graph by introducing arcs from other nodes that are within close proximity of the destination nodes to the destination nodes. Note that traffic can only flow from origin nodes to the other nodes and from other nodes to destination nodes. Figure 4 visualizes a graph that contains such an origin node.

Fig. 4
figure 4

Illustration of an origin node

Full size image

The daily throughput capacity of the arcs is not contained in the OSM data, such that it has to be determined by the analyst. In the computational analysis that we perform in Sect. 6 of this chapter, we estimate these daily throughput capacities for each arc based on the attributes highway and lanes.

4 Estimation of Traffic Matrices

The second component of our decision support system are so-called traffic matrices. There is one traffic matrix for each traffic type. This matrix specifies a daily traffic volume for each origin-destination pair. Hence, the size of the matrix depends on the number of origins and destinations the analyst considers. We denote the traffic matrix by T. Several approaches have been proposed to estimate the entries of the traffic matrix (see [16]). We use a simple gravity model to estimate the traffic matrix. Gravity models have been successfully used in social science research to model the movement of goods, information, or individuals between geographic regions (e.g., [18]) and, more recently, also for estimating traffic matrices (e.g., [9]).

The basic idea of a gravity model is that the amount of traffic from a given origin to a given destination is proportional to the total traffic to the destination. Analogously to [8], we model the traffic between two cities to be proportional to the product of the two populations divided by the distance between the two cities. Hence, the traffic volume from city i to city j is computed by (1):

$$\displaystyle \begin{aligned} T_{ij} = \sigma\frac{P_iP_j}{d_{ij}}, {} \end{aligned} $$
(1)

where σ denotes a normalization factor, d ij denotes the distance between city i and city j, and Pi and Pj denote the population of city i and city j, respectively. Ideally, the normalization factor σ is chosen such that when the resulting traffic volumes Tij are routed along the shortest paths between the cities, the resulting total traffic volume for individual arcs corresponds roughly to the data from automatic traffic counting stations for these arcs.

5 Formulation of Traffic Flow Model

The third component of our decision support system is an optimization model that determines a flow of traffic from the origins to the destinations at minimal cost. We propose an extension of the well-known multi-commodity network flow model (see [1]). This extension entails using piecewise-linear functions to compute the total cost of the network flow. In Sect. 5.1, we introduce the notation of the model. In Sect. 5.2, we describe the constraints of the model. In Sect. 5.3, we discuss the objective function of the model.

5.1 Notation

Sets

V :

Nodes

K :

Types of traffic (e.g., commercial traffic or private traffic)

K a :

Types of traffic allowed on arc a ∈ A

V O :

Origin nodes

V D :

Destination nodes

V R :

Regular nodes (neither origin nor destination nodes)

A :

Arcs

\(A^{\mbox{in}}_i\) :

Incoming arcs of node i ∈ V 

\(A^{\mbox{out}}_i\) :

Outgoing arcs of node i ∈ V 

O :

Origin-destination pairs

\(O^{\mbox{org}}_i\) :

Origin-destination pairs that have node i ∈ V O as origin

\(O^{\mbox{des}}_i\) :

Origin-destination pairs that have node i ∈ V D as destination

S a :

Segments of arc a ∈ A

Parameters

T ko :

Traffic volume of type k for origin-destination pair o ∈ O

c as :

Cost per vehicle that moves along segment s ∈ S a on arc a ∈ A

b as :

Upper bound on traffic volume that moves along segment s ∈ S a on arc a ∈ A

Variables

x aks :

Total flow of type k ∈ K a on arc a ∈ A through segment s ∈ S a

x ako :

Total flow of type k ∈ K a on arc a ∈ A associated with origin-destination pair o ∈ O

x a :

Total flow on arc a ∈ A

5.2 Constraints

Constraints (2) ensure that the total flow along an arc a ∈ A is equal to the sum of the flows through the different segments of this arc.

$$\displaystyle \begin{aligned} x_a=\sum_{s \in S_a;~k \in K_a}x_{aks} \qquad (a \in A){} \end{aligned} $$
(2)

Constraints (3) guarantee that the total flow along an arc a ∈ A is equal to the sum of the flows of different types through this arc.

$$\displaystyle \begin{aligned} x_a=\sum_{o \in O;~k \in K_a}x_{ako} \qquad (a \in A){} \end{aligned} $$
(3)

Constraints (4) enforce for each arc a ∈ A that the sum of flow of type k ∈ K a across all segments s ∈ S a is equal to the sum of the flow of type k ∈ K a across all origin-destination pairs o ∈ O.

$$\displaystyle \begin{aligned} \sum_{s \in S_a}x_{aks} =\sum_{o \in O}x_{ako} \qquad (a \in A;~k \in K){} \end{aligned} $$
(4)

Constraints (5) guarantee for each origin node i ∈ V O that the outgoing traffic volume of type k ∈ K is equal to the sum of the traffic volume of this type for all destinations.

$$\displaystyle \begin{aligned} \sum_{a \in A^{\mbox{out}}_i}x_{ako}=T_{ko} \qquad (i \in V^O;~k \in K;~o \in O^{\mbox{org}}_i){} \end{aligned} $$
(5)

Constraints (6) prevent traffic flow from starting from the wrong origin node.

$$\displaystyle \begin{aligned} \sum_{a \in A^{\mbox{out}}_i}x_{ako}=0 \qquad (i \in V^O;~k \in K;~o \in O \setminus O^{\mbox{org}}_i){} \end{aligned} $$
(6)

Constraints (7) guarantee for each destination node i ∈ V D that the incoming traffic volume of type k ∈ K is equal to the sum of the traffic volume of this type from all origins.

$$\displaystyle \begin{aligned} \sum_{a \in A^{\mbox{in}}_i}x_{ako}=T_{ko} \qquad (i \in V^D;~k \in K;~o \in O^{\mbox{dest}}_i){} \end{aligned} $$
(7)

Constraints (8) guarantee for each regular node i ∈ V R that the incoming traffic volume of each type k ∈ K is equal to the outgoing traffic volume of this type.

$$\displaystyle \begin{aligned} \sum_{a \in A^{\mbox{in}}_i;~s \in S_a}x_{aks}=\sum_{a \in A^{\mbox{out}}_i;~s \in S_a}x_{aks} \qquad (i \in V^R;~k \in K){} \end{aligned} $$
(8)

Constraints (9) guarantee for each regular node i ∈ V R that the incoming traffic volume of a specific origin-destination pair o ∈ O is equal to the outgoing traffic volume of this origin-destination pair.

$$\displaystyle \begin{aligned} \sum_{a \in A^{\mbox{in}}_i;~k \in K_a}x_{ako}=\sum_{a \in A^{\mbox{out}}_i;~k \in K_a}x_{aks} \qquad (i \in V^R;~o \in O){} \end{aligned} $$
(9)

Constraints (10) impose upper bounds on the flow through each segment s ∈ S a of arc a ∈ A.

$$\displaystyle \begin{aligned} \sum_{k \in K_a}x_{aks}\leq b_{as} \qquad (a \in A;~s \in S_a){} \end{aligned} $$
(10)

5.3 Objective Function

The objective function computes the total cost of the flow in the network:

$$\displaystyle \begin{aligned} \sum_{a \in A}\sum_{k \in K_a}\sum_{s \in S_a}c_{as}x_{aks}{} \end{aligned} $$
(11)

The complete linear programm reads as follows:

$$\displaystyle \begin{aligned}\mbox{TF}\left\{\begin{array}{ll@{\quad }l@{\hspace{1mm}}} \mbox{Min.} & (\text{11}) \\ \mbox{s.t.} & (\text{2})\text{--}(\text{10})\\ & x_{aks} \geq 0 & (s \in S_a;~a \in A;~k \in K_a) \\ & x_{ako} \geq 0 & (a \in A;~k \in K_a) \\ & x_a \geq 0 & (a \in A) \\ \end{array}\right.\end{aligned}$$

6 Computational Results

In this section, we test the proposed decision support system with artificial and real-world data. In Sect. 6.1, we illustrate the proposed traffic model with a simple example. In Sect. 6.2, we use the street network of the city of Bern to demonstrate how the resilience of a network can be evaluated. In Sect. 6.3, we demonstrate the scalability of the proposed decision support system by applying it to the nation-wide street network of Switzerland. Finally, in Sect. 6.4, we discuss how the proposed decision support system could potentially be applied to train networks. We implemented all parts of the decision support system in Python 3.6 and used the Gurobi (7.5.2) solver. All computations were performed on a workstation with Intel Xeon CPUs (model E5-2667 v2) with clock speed 3.30 GHz and 256 GB of RAM.

6.1 Illustrative Example

We consider a directed graph that has four regular nodes, three origin, and three destination nodes. The graph is shown in Fig. 5.

Fig. 5
figure 5

Graph of illustrative example

Full size image

For each arc between regular nodes, a piecewise-linear convex cost function with two segments defines the total cost for a given flow of traffic. Figure 6 displays such a cost function for an arbitrary arc a.

Fig. 6
figure 6

Piecewise linear convex cost function of arc a with two segments

Full size image

Table 3 provides the parameters of the cost functions for different street types. Note that the flow on arcs that connect origin and destination nodes with the rest of the graph is not bounded and does not incur any cost.

Table 3 Illustrative example: parameters of cost function for different street types
Full size table

Finally, Tables 4 and 5 specify the traffic matrices for private and commercial traffic, respectively. Private traffic can use any street type and commercial traffic is restricted to motorways and primary streets. Figure 7 shows an optimal solution to the illustrative example that we obtained in less than a second.

Fig. 7
figure 7

Graph of illustrative example

Full size image
Table 4 Illustrative example: traffic matrix for private traffic [1000 vehicles]
Full size table
Table 5 Illustrative example: traffic matrix for commercial traffic [1000 vehicles]
Full size table

6.2 Application to the Street Network of the City of Bern

In this section, we demonstrate how our decision support system can be used to assess the resilience of a street network against a disruption (e.g., a major accident). For this analysis, we consider the street network of the city of Bern. The proposed model TF is used to determine an optimal traffic flow before and after the disruption. A small difference between the total cost of traffic in these discrete states indicates high resilience and vice versa. The graph is constructed such that it represents all motorways, trunks, primary, secondary, tertiary, and residential streets within the city boundaries. Unclassified streets were eliminated. After simplification and before adding origin and destination nodes, the graph comprises 2733 nodes and 6805 arcs with a total length of 759.6 km.

We also created four artificial cities to capture transit traffic flowing through the city of Bern. This transit traffic originates from adjacent areas to the northeast (from Zurich and Basel), southeast (from Thun), northwest (from Lausanne), and southwest (from Fribourg). For each artificial city, we add one origin and one destination node to the graph. These nodes are connected as described in Sect. 3 to all nodes that lie within a certain radius around the origin and destination nodes. Consistent with the illustrative example above, arcs that connect origin and destination nodes with regular nodes have infinite capacity and zero cost. Table 6 details for each city the longitude and latitude of the origin-destination nodes, the population, and the radius. We determined the populations such that the optimal flow of traffic before the disruption does not exceed any capacity limit. Based on the population and the location of the artificial cities, the traffic matrix is computed using formula (1) with σ = 0.00035. For the sake of simplicity, we did not distinguish here between different types of traffic. Note that in Figs. 8 and 9 the longitude of the destination nodes is increased by 0.001 in order to distinguish them from the origin nodes.

Fig. 8
figure 8

Optimal traffic flow before disruption

Full size image
Fig. 9
figure 9

Optimal traffic flow after disruption

Full size image
Table 6 Location, population, and radius of artificial cities
Full size table

Consistent with our illustrative example, a piecewise-linear convex cost function with two segments defines for each arc between regular nodes the total cost for a given flow of traffic. The first segment represents fluid, the second segment congested traffic. Table 7 provides for each street type and segment the daily capacity and the costs per vehicle and kilometer.

Table 7 Capacity (# vehicles per day) and cost (per vehicle and km) for different street types
Full size table

We derived the maximum capacities for the first segments according to the Road Task Force report’s technical note [15]. Note that these numbers are rough estimates; they could be refined by considering additional information such as the attribute maxspeed and data from automatic traffic counters. The capacity of the second segment is infinite, such that a feasible solution always exists. The costs per vehicle and kilometer for the first segment are derived from average cost calculations in [19]. For the second segment, we multiplied this number with a factor of 100 to account for additional fuel consumption and reduced workforce productivity. By considering these cost types, we follow the approach of [2].

A disruption is specified in terms of location, as indicated by its geographical coordinates, and in terms of magnitude, as measured by its radius. All arcs that have at least one endpoint within the radius of the disruption are assumed to be affected. We set the capacity of all affected arcs to zero. In our example, we assume that the disruption takes place at (46.955889, 7.417909) and has a radius of 400 m.

We applied model TF to determine an optimal traffic flow before and after the disruption. Table 8 presents the number of variables (#Vars), the number of constraints (#Constrs), the running time (Time) in seconds, the value of the objective function (Total cost) and the number of congested arcs (#Congested arcs) for the case without disruption and the case with disruption.Footnote 1

Table 8 Numerical results
Full size table

The results suggest that the disruption significantly increases the total cost of traffic flow. Since it dissects the motorway which links the eastern and western city areas, all motorway traffic must be rerouted through primary and secondary streets. As a result, 68 arcs are congested, implying that the city’s street network is not particularly resilient to disruptions of this magnitude. Figures 8 and 9 show the optimal flow of traffic before and after the disruption.

6.3 Application to the Swiss Street Network

To demonstrate the scalability of the decision support system, we applied it to four large-scale problem instances that are all based on the nation-wide street network of Switzerland. The graph depicting this network is constructed such that it represents all motorways, trunks, primary, secondary, and tertiary streets of Switzerland. Other street types such as unclassified or residential streets were eliminated. After simplification and before adding origin and destination nodes, the graph consists of 26,294 nodes and 61,980 arcs with a total length of 45,291.8 km. Figure 10 shows the graph of the Swiss street network.

Fig. 10
figure 10

Graph of the Swiss street network

Full size image

The problem instances differ with respect to the number of cities that are considered. The largest instance considers the 20 most populated cities in Switzerland. Smaller instances consider only a subset of these cities. Table 9 reports for each instance the considered cities and the normalization parameter σ that was used to compute the respective traffic matrix. For the sake of simplicity, we did not distinguish here between different types of traffic.

Table 9 Large-scale problem instances
Full size table

Origin and destination nodes are added for each city as described in Sect. 6.2. Table 10 contains for each city the longitude and latitude of the origin-destination nodes, the radius, and the population. We obtained population figures from the Swiss Federal Statistical Office [17] and the coordinates from the website https://www.latlong.net/. The traffic matrix is computed according to formula (1) with the normalization parameter specified in Table 9.

Table 10 Location, population, and radius of the 20 largest cities in Switzerland
Full size table

The cost of traffic is determined as in Sect. 6.2, using the data specified in Table 7.

We applied model TF to all four instances, using the same Gurobi solver settings as specified in footnote 2, and solved each instance to optimality. Table 11 presents for each instance the number of origin-destination pairs (#O/D pairs), the number of variables (#Vars), the number of constraints (#Constrs), the running time (Time) in minutes, and the value of the objective function (Total cost).

Table 11 Numerical results
Full size table

From these results, we can conclude that optimal solutions can be obtained in reasonable running time even for very large street networks. The running time, however, increases considerably with the number of origin-destination pairs. Figure 11 shows the optimal flow of traffic for the largest instance with 20 cities.

Fig. 11
figure 11

Optimal traffic flow for instance 4. Note that the origin nodes are co-located with the destination nodes and hence not visible

Full size image

6.4 Application to Train Networks

A major advantage of the proposed decision support system is that it is not restricted to street networks. Particularly, it can be used (with some modification) to study train networks as well. We predict that the OSMnx package can be extended such that it transforms spatial OpenStreetMap information on train routes and networks directly into graphs. Alternatively, OpenRailwayMap could be used as a source for raw data as it contains detailed information on the world’s railway infrastructure. A third option would be to extract the graph from timetable data as described in [11]. Characteristics of a railway system could be incorporated in the traffic flow model by modifying some constraints or changing the objective function. For example, one could introduce capacities that are shared by several arcs to model the flexibility of railway operators to determine whether a track is used in both directions or only in one direction. Additional insights could be gained by considering a traffic system that comprises both street and railroad networks. This integration would allow researchers to investigate higher-order combination effects, e.g. the blockade or destruction of a road-rail bridge on which both vehicles and trains run.

7 Conclusion

We proposed a decision support system that can be used to evaluate the resilience of street networks based on publicly available data. The system consists of three main components: a directed graph that represents the street network, a traffic matrix that defines the traffic volume between origin-destination pairs, and an optimization model that determines an optimal flow of traffic from the origins to the respective destinations. We applied the system to real-world street networks to demonstrate how the model can be used to study the impact of a disruption and to illustrate the scalability of the optimization model. An optimal flow of traffic between 380 origin-destination pairs was determined in a few hours for a nationwide street network with 26,294 nodes and 61,980 arcs.

We suggest that future research could extend our approach by developing more sophisticated traffic matrix estimation techniques that also incorporate available traffic counts for specific street segments, by developing a dynamic traffic flow model that accounts for transfer times, and by applying our decision support system to train networks.