Identifying Achilles-heel roads in real-sized networks

Abstract

Ensuring a minimum operational level of road networks in the presence of unexpected incidents is becoming a hot subject in academic circles as well as industry. To this end, it is important to understand the degree to which each single element of the network contributes to the operation and performance of a network. In other words, a road can become an "Achilles-heel" for the entire network if it is closed due to a simple incident. Such insight of the detrimental loss of the closure of the roads would help us to be more vigilant and prepared. In this study, we develop an index dubbed as Achilles-heel index to quantify detrimental loss of the closure of the respective roads. More precisely, the Achilles-heel index indicates how many drivers are affected by the closure of the respective roads (the number of affected drivers is also called travel demand coverage). To this end, roads with maximum travel demand coverage are sorted as the most critical ones, for which a method--known as "link analysis"--is adopted. In an iterative process, first, a road with highest traffic volume is first labeled as "target link," and second, a portion of travel demand which is captured by the target link is excluded from travel demand. For the next iteration, the trimmed travel demand is then assigned to the network where all links including the target links run on the initial travel times. The process carries on until all links are labeled. The proposed methodology is applied to a large-sized network of Winnipeg, Canada. The results shed light on also bottleneck points of the network which may warrant provision of additional capacity or parallel roads.

J. Mod. Transport. (2017) 25(1):111 DOI 10.1007/s40534-016-0121-7

http://crossmark.crossref.org/dialog/?doi=10.1007/s40534-016-0121-7&domain=pdf

Web End = http://crossmark.crossref.org/dialog/?doi=10.1007/s40534-016-0121-7&domain=pdf

Web End = Identifying Achilles-heel roads in real-sized networks

Saeed Asadi Bagloee1 Majid Sarvi1 Russell George Thompson2

Abbas Rajabifard3

Received: 26 August 2016 / Revised: 14 December 2016 / Accepted: 29 December 2016 / Published online: 13 February 2017 The Author(s) 2017. This article is published with open access at Springerlink.com

Abstract Ensuring a minimum operational level of road networks in the presence of unexpected incidents is becoming a hot subject in academic circles as well as industry. To this end, it is important to understand the degree to which each single element of the network contributes to the operation and performance of a network. In other words, a road can become an Achilles-heel for the entire network if it is closed due to a simple incident. Such insight of the detrimental loss of the closure of the roads would help us to be more vigilant and prepared. In this study, we develop an index dubbed as Achilles-heel index to quantify detrimental loss of the closure of the respective roads. More precisely, the Achilles-heel index indicates how many drivers are affected by the closure of the respective roads (the number of affected drivers is also called travel demand coverage). To this end,

roads with maximum travel demand coverage are sorted as the most critical ones, for which a methodknown as link analysisis adopted. In an iterative process, rst, a road with highest trafc volume is rst labeled as target link, and second, a portion of travel demand which is captured by the target link is excluded from travel demand. For the next iteration, the trimmed travel demand is then assigned to the network where all links including the target links run on the initial travel times. The process carries on until all links are labeled. The proposed methodology is applied to a large-sized network of Winnipeg, Canada. The results shed light on also bottleneck points of the network which may warrant provision of additional capacity or parallel roads.

Keywords Critical roads Achilles-heel roads Sensor

location problem Flow-bundle Link analysis

1 Introduction

Unexpected trafc disruptions and reliability consequences have made academia and the industry more interested in subjects such as resilience, reliability, vulnerability; exibility, robustness, fragility and critical roads [1]. Although these concepts are yet to be unambiguously dened [2], each subject stands on its own merit representing some areas of concerns with a common denominator posed as the following key question: how does the transport system respond at such disruptive events? or what is the damage, given that something happens [3].

The disruption entails a wide spectrum of events from trafc accidents and incident to extreme events such as natural or man-made disasters. During and in the aftermath of such events, the most vital (or so-called critical) roads must be kept at a functioning level.

& Saeed Asadi Bagloee [email protected]

Majid Sarvi [email protected]

Russell George Thompson [email protected]

Abbas Rajabifard [email protected]

1 Smart Cities Transport Group, Department of Infrastructure Engineering, Melbourne School of Engineering, Centre for Disaster Management and Public Safety (CDMPS), The University of Melbourne, Parkville, VIC 3010, Australia

2 Smart Cities Transport Group, Department of Infrastructure Engineering, Melbourne School of Engineering, The University of Melbourne, Parkville, VIC 3010, Australia3 Department of Infrastructure Engineering, Melbourne School of Engineering, Centre for Disaster Management and Public Safety (CDMPS), The University of Melbourne, Parkville, VIC 3010, Australia

123

2 S. A. Bagloee et al.

Identifying a measure of robustness of the network at extreme events is a worthwhile effort which is also pursued in this study. In the rst place, there is no consensus on the denition of network robustness much to the extent of the network stretched in a wide spectrum of disciplines [2, 4]. We adopt an intuitive denition provided by the Institute of Electrical and Electronics Engineers (1990): Robustness is the degree to which the network can function correctly in the presence of stressful conditions [1]. In other words, robustness is a characteristic of a network in withstanding or absorbing disturbances and remaining intact when exposed to disruption [4].

The roads are the backbone of a network based on which the operation is conducted. Irrespective of where we stand on the above-mentioned spectrum, the general approach to assessing the robustness (or inversely fragility) of the network is to nd the critical roads, which is a daunting task. Critical roads could act like Achilles-heel that is that the entire network could become hostage to the disruption of few roads. In case of any incident leading to their closures, the network gets at a standstill. It is obvious that nding such Achilles-heel roads holds a central role to develop a mitigation scheme or to be prepared for any eventuality. Perhaps such ndings may warrant investment in expanding the road capacity such as new roads, bridges or lane widening, a type of themes known as network design problem [5]. The criticalness degree of roads can also be looked at as an index to measure their importance which in turn is utilized in road constructions and their prioritization [6, 7]. At the other end of this spectrum, there might be a number of roads whose removal, in fact, improves network performance commonly known as Braesss paradox [810].

According to the ndings in the literature, identifying such critical roads faces two main challenges: computational efciency and theoretical development [11]. To cope with such difculties, we proposed a heuristic method inspired by sensor (loop detector) location problem (SLP) [12]. The SLP basically stands for nding the minimum number and location of counting posts (in trafc count survey) in order to infer all trafc ows in a transport network. The widely accepted solution for the SLP is nding roads which can represent a broader range of origindestination (OD) travel demand. This method is known as OD demand coverage based on which our heuristic method for identifying the Achilles-heel roads is developed. To this end, roads with maximum travel demand coverage are sorted as the most critical one, for which a method widely popular among practitioners known as link analysis is adopted. The proposed methodology is applied to a large-sized network of Winnipeg, Canada. The results shed light on also bottleneck points of the network which may warrant provision of additional capacity or parallel

roads. These roads can also be considered as best possible locations for petrol station or police checkpoints since they represent the maximum number of vehicles passed through.

The impacts of the roads closure are simulated based on user-equilibrium trafc assignment for which the following assumptionswidely used in the literatureare made:(a) travel demand is xed and quantied as a single matrix,(b) commuters have a perfect understanding of the travel time, (c) neither demand nor travel time changes over time. In other words, we solve for a static and deterministic trafc assignment problem (TAP) subject to a xed travel demand. However, by relaxing one or some of the above-mentioned assignmentwhich resulted in stochastic, dynamic and variable travel demand methodsone can increase the realism and delity of the trafc simulation at the costs of additional computational times as well as some other computational complexities. Nevertheless, the consensus in the literature is to resort to the above-mentioned assumptions.

The rest of the article is organized as follows. Section 2 contains a literature review. Section 3 discusses the methodology. Section 4 presents numerical results of two case studies: Gaos test network and a large-size network of Winnipeg, Canada. Conclusion remarks are provided in Sect. 5.

2 Literature review

In this section, we provide a review of the studies related to the concepts of vulnerability followed by the literature related to the SLP.

The subjects such as vulnerability, robustness, exibility and resilience do not have a clear demarcation and denition [4]. Recent thorough reviews have been made by [4, 1315]. Given the extensive breadth of the research, in the present review, we seek only the most recent takes of the literature on the subject of critical roads.

Most of the previous studies are conceptual methods on vulnerability lacking a holistic approach to quantifying and evaluating the vulnerability of transportation networks. Rosenkrantz et al. [16] suggest the idea of a Structure-Based Resilience Matrix to measure the vulnerability/resilience of networks components. Scott et al. [17] used network ows, link capacity and network topology to develop a network robust index measure. Leu et al. [18] used a network analysis to measure the robustness considering physical features of the network. Mattsson and Jenelius [19] provide an overview of recent research on vulnerability and the resilience of transport systems.

The consensus in the literature is to investigate the vulnerability based on the network topology [20, 21]. de Oliveira et al. [22] investigated two performance attributes of road networks, reliability and vulnerability and discuss

123 J. Mod. Transport. (2017) 25(1):111

Identifying Achilles-heel roads in real-sized networks 3

the indicators found in the literature. The results show that the vulnerability indicators are more strongly affected by the characteristics of alternative routes. Aided by geography information systems (GIS), Kermanshah and Derrible [23] developed a data-driven approach to determining vulnerable locations in road networks with respect to land use information, demographic data and travel demand as well as some topological indicators. Similarly, Thekdi and Joshi [24] describe a scenario-based Bayesian approach to evaluate evidence from big-data resources, such as geographical landscape and demographic data, to identify vulnerable sections of the transportation network.

The plethora of the relevant studies can be divided into two groups: (a) A vast number of studies only consider topological characteristics of networks, such as accessibility, connectivity, shortest path [2530]. What is missing in such approaches is the dynamic of the ow on the network. (b) Other studies are primarily concerned with the dynamic characteristic of ow such as commuters route choosing behavior in the road network [1, 20, 31]. This study obviously belongs to the second group.

The critical roads sometimes are dealt with in the context of vulnerability or via resilience or through robustness and fragility. The consensus is to examine removals of the roads to nd their impacts on the respective network. The roads are then attributed with an index based on which the critical ones are agged [1, 32, 33]. Conforming to the aforementioned classication, there are also two major categories of indices to measure the overall performance of the network (also known as a measure of effectiveness): functional and topological [4]. The ow dynamic as an overall network performance index is largely formulated as changes in total travel time [4, 31].

Similarly, Jenelius et al. [3] elicited a number of link importance indices and site exposure indices based on the increase in generalized travel cost when links are closed. These measures are divided into two groups: one reecting an equal opportunities perspective and the other a social efciency perspective pertaining to the connectivity and weighted by travel demand, respectively. The generalized travel costs are measured based on the Dijkstras shortest paths algorithm, and it is called dynamic shortest path algorithm. In other words, the effects of the trafc congestions arising from the disruptions (road closures) are yet to be taken into account.

Albert et al. [34] investigated a class of in homogeneously wired networks called scale-free networks, which include the worldwide web, the Internet, social networks, cells as well as road networks. They found out that in response to random failures such networks exhibit an unexpected degree of robustness, to the extent their overall operations become unaffected. However, these networks are extremely vulnerable to targeted attacks aiming at a

few links or nodes that play a vital role in maintaining the networks connectivity. A similar observation has also been reported by [35]. They have also displayed that malfunctioning of a single component of a network can generate a cascading effect, thus causing the entire network to collapse.

Wu et al. [36] have extensively studied the cascading effects of a number of failures scenarios. In contrary to the previous studies, the congestion effects of the failures scenarios are fully taken into account based on the user-equilibrium (UE) trafc assignment. They displayed that two removal schemes ow-based and betweenness-based inict the highest disruption compared to other removal scenarios (betweenness is an indicator of a nodes centrality in a network, and it is equal to the number of shortest paths that pass through the respective node).

As the literature review indicates, though the road networks are resilient to random or natural failures, they are highly fragile to targeted attacks; that is why, we refer to it as Achilles-heel phenomenon.

The SLP has been found to be of the utmost difcult problems known as NP-hard [3739]. The SLP has been of great interest to electrical engineering as well as computer science for which a number of different methods are presented [4045]. Given the fact that SLP is NP-hard, the heuristic methods are deemed valid [46, 47]. Yang and Zhou [47] proposed four heuristic methods including maximal ow fraction, OD demand coverage. Some researchers consider geographical and/or topological dis-aggregation of link ows to place the sensors [38, 48, 49]. Zhang et al. [50] proposed a genetic algorithm hybridized with simulated annealing to nd appropriate trafc count posts to monitor networks trafc ow. Viti et al. [41] provide a solution for the SLP by minimizing a measure of information loss of partial observability. Morrison and Martonosi [51] establish a necessary condition on the location of the sensors to enable the trafc ow to be computed. Larsson et al. [12] present a review of the solution methods of the SLP in the literature and appoint the OD demand coverage (ODDC) as a favorable method.

Based on the literature review, the following can be concluded. The road networks are shown to be of scale-free [52] that is there is a few, but a signicant number of nodes with a lot of connections, whereas there are a high number of nodes with very few connections. This feature emerges from the fact that networks expand continuously by the addition of new nodes, and new nodes attach preferentially to nodes that are already well connected [53]. This is a clear denition of the road networks. Given the fact that the scale-free network is defenseless to targeted attacks, it is of the highest importance to ag these failures which are the mandate of the current study. To this end, the failure is dened as a number of drivers affected by targeted attacks

123

J. Mod. Transport. (2017) 25(1):111

4 S. A. Bagloee et al.

which in turn calls on the SLP. There are a number of methods proposed for the SLP out of which the OD demand coverage is adopted in our research. Furthermore, we will discuss that the OD demand coverage implies the two most detrimental removal scenarios: ow-based and betweenness-based.

3 Methodology

Before proceeding to the next sections to discuss the phased methodology, let us introduce all the notations used in this article as presented in Table 1.

In this section based on the OD demand coverage criterion, a set of highly demanding roads are identied. To put it plainly, the candidate roads must be of highest importance. Such interpretation gives birth to a whole different problem in transportation in which trafc count posts for OD estimation (ODE) are sought. The task of ODE is centered on adjusting an outdated OD demand data based on a recently compiled trafc count of some selected count posts. Obviously, the trafc count posts are placed on the road. Evidently, trafc survey and the count are a costly job, and hence, it is not possible to have trafc

counts on all roads. Now the question to be rst answered is: Which roads must be selected as count posts to be used in the ODE? It is also a valid answer to the SLP.

The ODDC can be mathematically formulated as follows [12]:

ODDC

max X

r2R

qr kr; 1

s:t: X

a2A

Par

la kr r 2 R; 2

X

a2A

la

n; 3

kr

2 0; 1

f g; la 2 0; 1

f g; r 2 R; a 2 A; 4 where the road network is denoted by a set of links, A, and a set of OD pairs, R. The travel demand of OD pair r 2 R is

represented by qr. For every road in the network a 2 A and

each OD pair r 2 R, we consider binary decision variables

la and kr: If a sensor is allocated, la = 1 and la = 0 otherwise; if sensors capture any trips pertaining to the respective OD pair, kr = 1 and kr = 0 otherwise. Furthermore, Par is a matrix of the size of |A| 9 |R| with binary entries: Par = 1 if trafc volume on a 2 A entails

any trips pertaining to r 2 R and Par = 0 otherwise. The

Table 1 Notation glossary used in this manuscript

Symbol Description

ODE Origindestination estimation

ODDC Origindestination demand coverage problem to be solved in phase 1

SLP Sensor (loop detector) location problemA* Set of agged roads as candidate roads deemed critical found at phase 1

A Sets of all roads including the candidate roads (i.e., A , A*)

N Set of nodes of the road network, representing, junctions

xa Trafc volume (in passenger car unit-pcu) on the road a 2 A

ta(xa) Travel cost or time of the road a 2 A, dened by a non-decreasing BPR function of the trafc volume of the respective road xa (called

delay function)

A n; An Set of links starting and ending at node n 2 N, respectively; A n; An A

R Set of origindestination pairs, R , N 9 Nqr Travel demand in pcu for origindestination r 2 R

qar Partial trips belonging to OD trips qr traversing the road a 2 A

Pr Set of paths between origindestination r 2 R

hp Trafc ow (in pcu) on path p 2 Pr, r 2 Rkr It is 1 if sensors (placed on the agged road) capture any trips pertaining to OD r 2 R and 0 otherwise

Par It is a matrix of the size of |A| 9 |R| with binary entries: Par = 1 if trafc volume on a 2 A entails any trips pertaining to r 2 R and

Par = 0 otherwise

la It is 1 if road a 2 A is agged to be allocated a sensor and 0 otherwise

n A pre-specied value for the total number of agged roads to be found as Achilles-heels:

n jA j

x A pre-specied value for the residual trafc ow

z The Beckmann objective function to be minimized

dpr;a Link-path incidence (1: if link a belongs to path p between origindestination r, and 0 otherwise) f pr The trafc ow on the path p between origindestination r 2 R

123 J. Mod. Transport. (2017) 25(1):111

Identifying Achilles-heel roads in real-sized networks 5

number of sensors to be allocated to roads is denoted by

n.

Start

In the end, a number of selected roads to be equipped with sensors constitute the set of agged roads A* , A hence

n jA j.

As discussed before, the SLP is proven to be NP-hard. In order to streamline such difculty (especially in facing with real-sized networks), we adopt an intuitive and heuristic approach based on a popular practice among practitioners known as select link analysis or ow-bundle [54] in which, trafc volume seen on a road is traced back and forth to its origins and destinations. In other words, a subset of the OD demand corresponding to the trafc volume of the respective road is rst skimmed off and it is then highlighted in the trafc volume plot. By doing so, the trace of the target trafc volume will be shown on the network. The method is carried out in an iterative course. Given a network with the result of the trafc assignment, in each iteration, a road with highest trafc volume is agged for the sensor. The agged road is then subjected to the ow-bundle procedure to retrieve the corresponding OD trips, and we call it agged trips. For the next iteration, the OD demand is rst shaken off the agged trips, and it is then used for a new trafc assignment (better to be called partial trafc assignment).

The static, deterministic trafc assignment problem is traditionally formulated based on the Wardropian principles, that is, drivers choose the shortest paths:

min zx X

a2A

Z

Initialize

: maximum number of flagged roads; : maximum residual traffic volume;

: set of collected roads flagged.

Carry out complete traffic assignment over network and OD demand

find road with maximum traffic volume

Elicit traffic volume on all roads

Carry out flow-bundle for the road , to find corresponding flagged OD trips:

Carry out partial traffic assignment ,

flag

Save

Trim the OD demand

If and

If

Find maximum residual flow

No

yes

xa

0 taxa dx; 5

s:t: : X

p

End

Fig. 1 Flow-bundle algorithm for the SLP

f pr qr r 2 R; 6

f pr 0 p 2 Pr; r 2 R; 7

xa X

i

X

k

X

p

f pr dpr;a a 2 A; p 2 Pr; r 2 R; 8

where z the Beckmann objective function to be minimized; f pr the trafc ow on the path p between origindestination r 2 R; dpr;a a link-path incidence (1: if link a belongs to the

path p between origindestination r, and 0 otherwise) [55, 56]. The rest of notations have already been introduced. The TAP is solved iteratively such that in each iteration links travel times are updated based on the congestion level and it carries on until the difference of the values of the objective functions in two successive iterations becomes negligible.

Compared to the rst trafc assignment effort, this new (partial) trafc assignment can be computed much more efciently: Any solution algorithm for a TAP needs to start with a feasible solution (trafc volumes on roads for {xa, a 2 A}). In an iterative fashion, links travel times ta

and trafc volumes xa are updated until a satisfactory

convergence criterion is met (the travel times are updated to also update the shortest paths).

For a new trafc assignment, in the absence of any information the algorithm initiates based on the free-ow travel time (called all-or-nothing trafc assignment). If there were a prior knowledge of the travel times close to those of the nal optimal solution, then less number of iterations would be needed to meet the convergence criterion.

In the partial trafc assignment, this prior knowledge exists as discussed in the following. First, the xa from the previous trafc assignment is taken off from the OD travel demand, while the links travel times remain intact which is also corresponding to those of the optimal solutions found in the rst trafc assignment. This is because when a portion of trips is taken off the road network, we do not want to see any changes on drivers routing behavior (still remaining in the road) for tracing the next round of trips. Hence, solving the new trafc assignment can be termed as partial trafc assignment. The process carries out until a certain number of agged roads are obtained or residual trafc volume of the network becomes insignicant. An

123

J. Mod. Transport. (2017) 25(1):111

6 S. A. Bagloee et al.

algorithmic exposition of the method is provided as follows (a pictorial presentation of the algorithm is also provided in Fig. 1):

Step 0: Set two target values for terminations: (a)

n:

common benchmark network to exchange their ndings. Therefore, the results reported in this paper can then be referred and examined in further studies. We then undertake a large-sized network of Winnipeg as a challenging case study to display applicability of the proposed methodology. All delay functions associated with the links conform to BPR-type.

As for the computational technology, we employ a desktop computer with Intel(R) Xeon(R) 3.70 GHz and64.0 GB RAM. The algorithm is coded in EMME 3 using macro the softwares programming language.

Parameters setup of the algorithm is as follows:

The relative gap needed by FrankWolfe algorithm to solve a trafc assignment is conservatively considered to be 0.0001 [58];

As for the number of candidates in Phase 1, one can carry out the process until the maximum trafc volume left on the roads becomes insignicant. For instance, the capacity of a local road can be a good criterion for being insignicant. Regardless, a pre-specied capped number can also be considered. For instance, for the Winnipeg case study, we intentionally extended the number of candidates to 100 agged roads, by which the maximum trafc volume left on the network was found 50. By doing so, we wanted to challenge the performance of the proposed algorithm at such an extreme condition.

4.1 Example 1: Gaos network

Figure 2 illustrates the example network developed by Gao et al. [57], where the delay functions conform to ta

ta 0:008x4a (note: ta is free-ow travel time and is shown

in Fig. 2). The OD travel demand is also presented in Fig. 2 which is fairly different from the original Gaos network. The algorithm runs until the residual ow on the network becomes zero which results in 12 (out of 16) agged roads.

The agged roads are found as follows (start node-end node): 56, 78, 610, 15, 48, 37, 59, 812, 67, 1011, 26, 23; These roads are sorted in descending order based on their respective total demand coverage which are 6.28, 3.79, 3.34, 2, 2, 1.31, 1, 0.98, 0.91, 0.67,0.24, 0.07. As can be seen, in early stages one can observe signicant decreases in the demand coverages.

4.2 Example 2: Winnipeg large-size network

The large-sized road network of the city of Winnipeg, Canada, widely used in the literature [59] is undertaken for the numerical test here as well. This dataset has also been

number of agged roads to allocate sensor, (b)

x:

maximum residual trafc volume. Initialize set A* designated to the roads agged as selected for sensors. Given network A and OD demand {qi, i 2 I}, carry out

trafc assignment to get trafc volume on all roads denoted by {xa, a 2 A};

Step 1: Find a road a with maximum trafc volume (i.e., {xa = max(x), 2 A}) and add it to the agged set

(a ? A*). Carry out ow-bundle for the road a, and nd the corresponding agged OD trips denoted by qar, r 2 R. Subtract the current OD demand from the

agged trips (i.e., qr qr qar, r 2 R). Save Pr2R qar,

as the ODCD of the road a. Now execute a partial trafc assignment.

Step 2: Find number of agged roads and maximum residual trafc volume; if they are less than the target values (

x and

n) and then go to step 1; otherwise, terminate the algorithm.

The outcomes of the algorithm are the agged roads for the sensor. We specify values of the target number of agged roads and maximum residual trafc volume (

x and

n) in the undertaken case studies. By now the agged roads are found. The order at which there are agged as well as their corresponding OD coverage volumes shows their criticalness degree.

As the literature review indicates, the ow-based and betweenness-based removal schemes are more detrimental and disruptive to the networks performance. The OD demand coverage method as implemented above (based on the link analysis) obviously bears traits of these two schemes. It is evidently ow-based because at each iteration the road with highest trafc ow is agged and taken out of the network. Since a new trafc assignment problem is solved for each iteration and hence a new set of the shortest paths are calculated, the algorithm implicitly considers the betweenness (note that the betweenness refers to a total number of shortest paths passing through a respective node).

4 Numerical evaluations

In this section, we rst examine the proposed methodology over a network similar to the Gaos 12-node network [57]. The Gaos network is readily available in the literature and is being used by the researchers as a common currency or a

123 J. Mod. Transport. (2017) 25(1):111

Identifying Achilles-heel roads in real-sized networks 7

OD demand matrix: O D 8 9 10 11 12

1 1 1 1 1 1

2 1 0 1 1 1

3 1 0 0 1 1

4 1 0 0 0 1

5 1 1 1 1 1

Remarks: values on the roads are free flow travel time denoted by in the delay function

Fig. 2 Gaos test network

Fig. 3 Winnipeg network: locations of 100 roads found as agged roads and trafc volume of the no-disruption scenario

provided in the EMME 3 [60]. The road network is comprised of 154 zones, 943 nodes and 3075 directional links. Given a high number of roads, the algorithm runs for 100 iterations to nd 100 agged roads.

Figure 3 along with Table 2 shows the locations and characteristics of the agged roads. In addition to the OD coverage, other characteristics of the roads including free-ow speed (ffs), length, capacity, free-ow travel time (t0)

and travel time are also provided in Table 2. As can be seen in Fig. 3, the critical roads are largely agged on the main roads and roads surrounding the CBD.

Figure 4 depicts how OD demand coverages vary over a descending order of the agged critical roads. The gure shows a deep reduction in the rst 10 roads and a very slight slope in the rest of the roads. Hence, these 10 roads must be pinpointed for further investigations and actions

123

J. Mod. Transport. (2017) 25(1):111

8 S. A. Bagloee et al.

Table2Winnipegnetwork,100candidatesroadssortedbasedontheircorrespondingODcoverages

IDinodejnodeffsLengthCapacityt0TimauODDCIDinodejnodeffsLengthCapacityt0TimauODDC

1705713500.225500.2400.384394151461458250.442001.0561.951191

2607606500.3725000.4440.828393652212213350.417500.7030.704190

3170169500.2318750.2760.656326353507508350.3312500.5660.603183

4457458501.3917001.6681.758299754784811500.2918750.3480.348171

5304412400.3826250.5700.712283755230255501.373751.6441.651156

6414973450.1225000.1600.179203756613614500.1118750.1320.132144

7813811500.2525000.3000.3232019571067493650.2612500.2400.264143

8418890400.1517500.2250.290168258744743350.656251.1141.116137

9592596350.6118751.0461.174158959699730350.447500.7540.756129

102991064400.2917500.4350.472146260602601500.5825000.6960.933126

11790765500.4118750.4920.531145161533582501.4812501.7761.777123

12204205450.2625000.3470.349112662628629500.2418750.2880.288120

13516517500.2525500.3000.306102363839838500.4512500.5400.543117

14441442500.5118750.6120.80595164667669350.5112500.8741.767115

15746745500.2112500.2520.28085865500499500.3412500.4080.494112

16727726500.318750.3600.43684366834833350.26250.3430.354106

17311316350.2218750.3770.38479267222296350.2512500.4290.471103

18756755653.266253.0094.11076368648649500.7612500.9121.061100

19234240550.9825001.0691.07372169336337500.676250.8040.92095

20516608550.1837500.1960.2136707010091008350.1715000.2910.39895

21363378501.3517001.6201.62561071886904350.17500.1710.17590

22221222350.1912500.3260.38258172297294400.5917500.8850.88588

23649651500.7912500.9481.31556573620619500.1218750.1440.14485

24441440500.525500.6000.65756474388387500.9617001.1521.15283

25836837500.5112500.6120.62452975885907350.17500.1710.17283

26483484650.6317500.5820.58848176769765350.837501.4231.42681

27601602500.5818750.6960.83043177171172500.3712500.4440.44579

28576581502.1212502.5442.92842278422417350.3111250.5310.53673

29617616500.3925000.4680.55841779795794500.3712500.4440.45973

30330328500.3418750.4080.57840480409317500.2712500.3240.39372

319821003350.047500.0690.07040281686683350.367500.6170.62072

32777778400.2417500.3600.36539682734733350.297500.4970.50370

33260261350.636251.0801.83738283701682350.3918750.6690.66969

34325409501.0112501.2121.54238284727728500.2218750.2640.26569

35397386500.858501.0201.02636985241219350.643751.0971.13568

36184872650.8325000.7660.76833586454455500.3718750.4440.44468

123 J. Mod. Transport. (2017) 25(1):111

Identifying Achilles-heel roads in real-sized networks 9

4000

3500

OD demand coverage

3000

2500

2000

1500

1000

500

0 0 10 20 30 40 50 60 70 80 90 100

Criticalness degree (or order of flagged roads)

Fig. 4 Winnipeg test, a variation of OD demand coverage over the agged roads

such as preparing mitigation plans, reinforcement measures and.

5 Conclusions

In this study, we developed a heuristic methodology to nd the most critical roads whose closures are devastating as if they act like Achilles-heel, and bring the entire network to a halt. The Achilles-heels is unfortunately in the genes of the road networks since they are proven to be of the scale-free networks that are the networks highly vulnerable to selected and targeted disruptions or attacks.

To this end, a set of roads which represent the travel demand the most are deemed to be critical are agged. To do so, we borrowed the notion of sensor (loop detector) location problem which is proven to be of utmost difcult problems in terms of computational expenses. Such difculties convinced us to resort to a heuristic methodology based on the concept of the maximum OD coverage which is already found as a favorable method for the SLP in the literature.

According to the OD coverage method, highly demanding roads (those that cover the travel demand the most) are found, for which we employed link analysis: methoda popular tool for practitioner in trafc impact studies. We applied the algorithm to the Gaos test network and a real network of Winnipeg, Canada.

The main contribution of this study can be attributed to the way the OD coverage method is implemented in which the two most detrimental removal scenarios (i.e., ow-based and betweenness-based) are considered in one go. Moreover, in terms of the computational expenses, the proposed methodology provides highly efcient methods much owed to the adoption of the partial trafc assignment.

The results can be found of the highest importance to the trafc authorities in their quest to protect the road networks against targeted disruptions which would have cascading disruption across the system.

Table2continued

IDinodejnodeffsLengthCapacityt0TimauODDCIDinodejnodeffsLengthCapacityt0TimauODDC

37728729500.518750.6000.60233487845857501.0718751.2841.28466

38175174500.4518750.5400.68726288605606500.1418750.1680.17864

39686687350.3918750.6690.67725389212211350.497500.8400.84061

40322321650.825000.7380.73924790506592400.3826250.5700.57961

41217218350.347500.5831.04324191540541650.818750.7480.77661

42262275350.193750.3260.33423792612611500.5425000.6481.01560

43655654350.267500.4460.47122793338337500.5312500.6360.65859

44411412400.117500.1500.15522694363364501.036251.2361.23658

45771772350.286250.4800.49422195221219350.273750.4630.48856

46419422350.1912500.3260.34822096751750500.1717000.2040.20456

47790791350.633751.0802.18120997776779350.327500.5490.54956

48711712500.1834000.2160.21720098454452500.7518750.9000.95255

49428427350.2512500.4290.43919899363362500.3312500.3960.41554

50243246350.8812501.5091.549194100445490500.3317000.3960.40254

123

J. Mod. Transport. (2017) 25(1):111

10 S. A. Bagloee et al.

The subjects such as critical roads, robustness and resilience are seeing interest from different stakeholders such as authorities, practitioners and academia. Knoop et al. [33] have reviewed a variety of research and have assessed the quality of the outcomes. They found there is no consistency in the outcome. Such inconsistency and uncertainty have also reported by others [13]. Future studies can direct to rst establish a consensus in denitions of these themes and their implications. The authors are currently studying on a global index to measure the robustness (or adversely fragility) of the network. Similar indices can be developed for other subjects. We are also working to nd critical scenarios (rather than critical roads) which might consist of critical and non-critical roads. In other words, there can be some non-critical roads; if they become closed at the same time, the network becomes a gridlock Bagloee et al. [61].

Acknowledgements The authors are indebted to Prof. Zhao and two anonymous reviewers whose remarks contributed to improving the quality and the clarity of the nal version.

Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/

Web End =http:// http://creativecommons.org/licenses/by/4.0/

Web End =creativecommons.org/licenses/by/4.0/ ), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

References

1. Nagurney A, Qiang Q (2012) Fragile networks: identifying vulnerabilities and synergies in an uncertain age. Int Trans Oper Res 19(12):123160

2. Maltinti F, Melis D, Annunziata F (2011) Road network vulnerability: a review of the literature. In: Chong WKO, Hermreck C (eds) The international conference on sustainable design and construction (ICSDC). Integrating sustainability practices in the construction industry, March 2325, Kansas City, Missouri

3. Jenelius E, Petersen T, Mattsson L-G (2006) Importance and exposure in road network vulnerability analysis. Transp Res Part A Policy Pract 40(7):537560

4. Faturechi R, Miller-Hooks E (2014) Travel time resilience of roadway networks under disaster. Transp Res Part B Methodol 70:4764

5. Bagloee SA, Tavana M, Ceder A, Bozic C, Asadi M (2013) A hybrid meta-heuristic algorithm for solving real-life transportation network design problems. Int J Logist Syst Manag 16(1):4166

6. Bagloee SA, Tavana M (2012) An efcient hybrid heuristic method for prioritising large transportation projects with interdependent activities. Int J Logist Syst Manag 11(1):114142

7. Bagloee SA, Asadi M (2015) Prioritizing road extension projects with interdependent benets under time constraint. Transp Res Part A Policy Pract 75:196216

8. Bagloee SA, Ceder A, Tavana M, Bozic C (2013) A heuristic methodology to tackle the Braess Paradox detecting problem tailored for real road networks. Transp A Transp Sci 10(5):437456

9. Braess D, Nagurney A, Wakolbinger T (2005) On a paradox of trafc planning. Transp Sci 39(4):446450

10. Braess D (1968)ber ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12(1):258268

11. Taylor MA (2012) Network vulnerability in large-scale transport networks. Transp Res Part A Policy Pract 46(5):743745

12. Larsson T, Lundgren JT, Peterson A (2010) Allocation of link ow detectors for origin-destination matrix estimationa comparative study. Comput-Aided Civil Infrastruct Eng 25(2):116 131

13. Reggiani A, Nijkamp P, Lanzi D (2015) Transport resilience and vulnerability: the role of connectivity. Transp Res Part A Policy Pract 81:415

14. Wang Z, Chan AP, Yuan J, Xia B, Skitmore M, Li Q (2014) Recent advances in modeling the vulnerability of transportation networks. J Infrastruct Syst 21(2):29

15. Bagloee SA, Asadi M, Richardson L (2011) Identifying trafc count posts for origin-destination matrix adjustments: an approach to actual size networks. J Transp Manag 22(1):7988

16. Rosenkrantz DJ, Goel S, Ravi S, Gangolly J (2004) Structure-based resilience metrics for service-oriented networks, pp 345362

17. Scott DM, Novak DC, Aultman-Hall L, Guo F (2006) Network robustness index: a new method for identifying critical links and evaluating the performance of transportation networks. J Transp Geogr 14(3):215227

18. Leu G, Abbass H, Curtis N (2010) Resilience of ground transportation networks: a case study on Melbourne. In: 33rd Australasian transport research forum conference canberra, Australia

19. Mattsson L-G, Jenelius E (2015) Vulnerability and resilience of transport systemsa discussion of recent research. Transp Res Part A Policy Pract 81:1634

20. Jenelius E, Mattsson L-G (2015) Road network vulnerability analysis: conceptualization, implementation and application. Comput Environ Urban Syst 49:136147

21. Kermanshah A, Karduni A, Peiravian F, Derrible S (2014) Impact analysis of extreme events on ows in spatial networks, pp 2934

22. de Oliveira EL, da Silva Portugal L, Junior WP (2016) Indicators of reliability and vulnerability: similarities and differences in ranking links of a complex road system. Transp Res Part A Policy Pract 88:195208

23. Kermanshah A, Derrible S (2016) A geographical and multi-criteria vulnerability assessment of transportation networks against extreme earthquakes. Reliab Eng Syst Saf 153:3949

24. Thekdi SA, Joshi NN (2016) Risk-based vulnerability assessment for transportation infrastructure performance. Int J Crit Infrastruct 12(3):229247

25. Callaway DS, Newman ME, Strogatz SH, Watts DJ (2000) Network robustness and fragility: percolation on random graphs. Phys Rev Lett 85(25):54685471

26. Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D-U (2006) Complex networks: structure and dynamics. Phys Rep 424(4):175308

27. Newman M, Barabasi A-L, Watts DJ (2006) The structure and dynamics of networks. Princeton University Press, Princeton28. Newman ME (2003) The structure and function of complex networks. SIAM Rev 45(2):167256

29. Tu Y, Yang C, Chen X (2012) Road network topology vulnerability analysis and application. Proc ICE-Transp 166(2):95104

30. Zhang H, Fata E, Sundaram S (2015) A notion of robustness in complex networks. IEEE Trans Control Netw Syst 2(3):310320

31. Luathep P (2011) Stochastic transport network model and optimization for reliability and vulnerability analysis. Ph.D. dissertation, The Hong Kong Polytechnic University

32. El-Rashidy RA, Grant-Muller SM (2014) An assessment method for highway network vulnerability. J Transp Geogr 34:3443

123 J. Mod. Transport. (2017) 25(1):111

Identifying Achilles-heel roads in real-sized networks 11

33. Knoop VL, Snelder M, van Zuylen HJ, Hoogendoorn SP (2012) Link-level vulnerability indicators for real-world networks. Transp Res Part A Policy Pract 46(5):843854

34. Albert R, Jeong H, Barabsi A-L (2000) Error and attack tolerance of complex networks. Nature 406(6794):378382

35. Crucitti P, Latora V, Marchiori M, Rapisarda A (2004) Error and attack tolerance of complex networks. Phys A 340(1):388394

36. Wu J, Gao Z, Sun H (2007) Effects of the cascading failures on scale-free trafc networks. Phys A 378(2):505511

37. Bianco L, Confessore G, Gentili M (2006) Combinatorial aspects of the sensor location problem. Ann Oper Res 144(1):201234

38. Bianco L, Confessore G, Reverberi P (2001) A network based model for trafc sensor location with implications on O/D matrix estimates. Transp Sci 35(1):5060

39. Chin F, Chrobak M, Yan L (2014) Algorithms for placing monitors in a ow network. Algorithmica 68(1):115

40. Hu S-R, Liou H-T (2014) A generalized sensor location model for the estimation of network origindestination matrices. Transp Res Part C Emerg Technol 40:93110

41. Viti F, Rinaldi M, Corman F, Tampre CM (2014) Assessing partial observability in network sensor location problems. Transp Res Part B Methodol 70:6589

42. Bianco L, Cerrone C, Cerulli R, Gentili M (2014) Locating sensors to observe network arc ows: exact and heuristic approaches. Comput Oper Res 46:1222

43. Castillo E, Grande Z, Calvio A, Szeto WY, Lo HK (2015) A state-of-the-art review of the sensor location, ow observability, estimation, and prediction problems in trafc networks. J Sens. doi:http://dx.doi.org/10.1155/2015/903563

Web End =10.1155/2015/903563

44. Gentili M, Mirchandani P (2012) Locating sensors on trafc networks: models, challenges and research opportunities. Transp Res Part C Emerg Technol 24:227255

45. Fu C, Zhu N, Ling S, Ma S, Huang Y (2016) Heterogeneous sensor location model for path reconstruction. Transp Res Part B Methodol 91:7797

46. Lam W, Lo H (1990) Accuracy of OD estimates from trafc counts. Trafc Eng Control 31(6):358367

47. Yang H, Zhou J (1998) Optimal trafc counting locations for origindestination matrix estimation. Transp Res Part B Methodol 32(2):109126

48. Ehlert A, Bell MG, Grosso S (2006) The optimisation of trafc count locations in road networks. Transp Res Part B Methodol 40(6):460479

49. Yang H, Yang C, Gan L (2006) Models and algorithms for the screen line-based trafc-counting location problems. Comput Oper Res 33(3):836858

50. Zhang J, Zhang X, Wu J (2007) Genetic simulated annealing algorithm for optimal deployment of ow monitors, pp 398402

51. Morrison DR, Martonosi SE (2015) Characteristics of optimal solutions to the sensor location problem. Ann Oper Res 226(1):463478

52. Lammer S, Gehlsen B, Helbing D (2006) Scaling laws in the spatial structure of urban road networks. Phys A 363(1):8995

53. Barabsi A-L, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509512

54. Bar-Gera H, Boyce D, Nie Y (2012) User-equilibrium route ows and the condition of proportionality. Transp Res Part B Methodol 46(3):440462

55. Shef Y (1985) Urban transportation networks: equilibrium analysis with mathematical programming methods. Prentice-Hall, Englewood Cliffs

56. Patriksson P (1994) The trafc assignment problem: models and methods, VSP BV, The Netherlands. Facsimile reproduction published in 2014 by Dover Publications, Inc., Mineola, New York, NY

57. Gao Z, Wu J, Sun H (2005) Solution algorithm for the bi-level discrete network design problem. Transp Res Part B Methodol 39(6):479495

58. Boyce D, Ralevic-Dekic B, Bar-Gera H (2004) Convergence of trafc assignments: how much is enough? J Transp Eng 130(1):4955

59. Bar-Gera H (2016) Transportation network test problems, December 1, 2016. http://www.bgu.ac.il/%7ebargera/tntp/

Web End =http://www.bgu.ac.il/*bargera/tntp/

60. INRO (2009) EMME3 v 3.2. EMME3 Users Guide61. Bagloee SA, Sarvi M, Wolshon B, Dixit V (2017) Identifying critical disruption scenarios and a global robustness index tailored to real life road networks. Transp Res Part E: Logist Transp Rev 98:6081

123

J. Mod. Transport. (2017) 25(1):111