# Resilience-Based Optimization of Postdisaster Restoration Strategy for Road Networks

Authors: Xinhua Mao; Jibiao Zhou; Changwei Yuan; Dan Liu
Journal: Journal of Advanced Transportation
 (2021)

---

## Abstract

This work proposes a framework for the optimization of postdisaster road network restoration strategies from a perspective of resilience. The network performance is evaluated by the total system travel time (TSTT). After the implementation of a postdisaster restoration schedule, the network flows in a certain period of days are on a disequilibrium state; thus, a link-based day-to-day traffic assignment model is employed to compute TSTT and simulate the traffic evolution. Two indicators are developed to assess the road network resilience, i.e., the resilience of performance loss and the resilience of recovery rapidity. The former is calculated based on TSTT, and the latter is computed according to the restoration makespan. Then, we formulate the restoration optimization problem as a resilience-based bi-objective mixed integer programming model aiming to maximize the network resilience. Due to the NP-hardness of the model, a genetic algorithm is developed to solve the model. Finally, a case study is conducted to demonstrate the effectiveness of the proposed method. The effects of key parameters including the number of work crews, travelers’ sensitivity to travel time, availability of budget, and decision makers’ preference on the values of the two objectives are investigated as well.


---

## Body

## 1. Introduction

Road infrastructure forms the backbone of transport activities, which plays an important role in boosting economic development and increasing accessibility. Due to extreme weather, road networks are inclined to suffer from the disruptions caused by natural disasters such as floods, typhoons, and landslides. Hence, restoration activities are needed to recover the networks as soon as possible. However, the available budget in a short time after the disaster cannot afford to repair all the disrupted road segments. There is an increasing demand for making a cost-effective postdisaster road network restoration strategy (RNRS) [1, 2], which refers to determining the road segments to be repaired and the restoration time sequence.In recent years, resilience has attracted growing attention in the road infrastructure management field [3–6]. How to keep the infrastructure networks at a high level of resilience has become a challenge for transportation agencies. The concept of road network resilience is defined as the ability to absorb disruptive events and recover to normal operation within a reasonable period of time [7, 8]. Based on the definition, a variety of metrics have been introduced to assess the resilience of an infrastructure network. This assessment is indispensable for the optimization of a resilient infrastructure system. Despite the wide range of studies focusing on the resilience-based RNRS, there are still two gaps to be filled. Firstly, it is rare in the literature to investigate a joint optimization of budget allocation and restoration scheduling for an effective RNRS. Secondly, most of the previous studies apply user equilibrium (UE) models to evaluate the total system travel time (TSTT) during the restoration process. UE models assume that the network flow patterns achieve an equilibrium state overnight given new network conditions, which cannot reflect the day-to-day traffic dynamics.In view of this, this study aims to investigate the optimal postdisaster restoration problem for road networks from the perspective of resilience considering the day-to-day network flow fluctuation. The main contribution of our work is to build a resilience-based bi-objective mixed integer programming model combined with a link-based day-to-day traffic assignment model to determine the optimal RNRS based on the tradeoff between the maximal resilience of performance loss and the maximal resilience of recovery rapidity. With our proposed method, decision makers would determine a set of prioritized road segments to be restored and the optimal time sequence of the restoration tasks.The remainder of this paper is organized as follows. Section2 introduces the literature review. Section 3 presents two resilience metrics, proposes a link-based day-to-day dynamics model, and develops a resilience-based optimization model for the postdisaster RNRS. Section 4 proposes a genetic algorithm to solve the optimization model. In Section 5, we employ a case study to validate our proposed method. Conclusions and future work are discussed in Section 6.


## 2. Literature Review

Due to the increasing natural hazards, recovering damaged road networks in a resilient manner has attracted growing attention in recent years. The existing studies in this realm can be classified into two categories, i.e., the budget allocation problem and the restoration scheduling problem. The budget allocation problem aims to determine the road segments to be repaired from a set of damaged road segments with budget limits. For instance, Liu et al. [9] developed a two-stage stochastic programming model to allocate limited retrofit budget over multiple road bridges to maximize the resilience and robustness of the entire road network. In order to mitigate the predisaster risk and improve network resilience, Zhang and Wang [10] proposed a resilience-based optimization model to identify the road network retrofit projects. As for the restoration scheduling problem, it focuses on identifying the time sequence of restoration activities. Bocchini and Frangopol [11] developed a multiobjective optimization model aiming at maximal resilience, minimal restoration time, and minimal restoration cost to formulate the restoration scheduling problem for road-bridge networks after an earthquake. Li et al. [12] established a resilience-based bilevel programming model to investigate the optimization of the road network recovery strategy under uncertainty aiming at the maximization of network resilience. Generally, traffic dynamics is an important issue that needs to be considered in the RNRS problem. Most of the previous studies employ the classic UE traffic assignment model to estimate TSTT  assuming that the traffic flow patterns across the road network are always in an equilibrium state [13]. The only exception is Nogal et al. [14], where a new dynamic equilibrium-restricted assignment model is presented to simulate the postdisaster day-to-day flow evolution process. According to the work of De Palma and Rochat [15], travelers are highly sensitive in their route choice behaviors to the occurrence of an event in the road network. Hence, travelers reselect their routes shortly after the restoration activity of any disrupted road segment is completed, which makes the network flows evolve constantly to reach a new equilibrium state within a period of time from the old equilibrium state. Simulation on a 3 × 3 grid network with 9 nodes, 12 links, and 6 routes by He et al. [16] indicated that all links have some flow fluctuations after a 50% capacity reduction and it takes about 20 days for the network flow patterns to achieve a new equilibrium state. This fluctuating traffic flow pattern is defined as partial UE (PUE) by Sumalee and Watling [17], namely, the network flows in a certain period of time are not on an equilibrium state. Therefore, it is problematic to use the UE model to evaluate TSTT during the network restoration process. The day-to-day model can better capture the PUE [18], which is appropriate for dealing with TSTT calculation in the road network restoration context.Day-to-day traffic assignment models are capable of predicting day-to-day traffic fluctuations and the evolution process itself when the traffic network is perturbed by unexpected events, construction actions, and traffic controls. As noted by Watling and Hazelton [19], day-to-day traffic models have great flexibility, which accommodates a wide range of behavior rules, levels of aggregation, and traffic modes. The first effort can be attributed to Horowitz [20], who proposed a discrete time day-to-day dynamic traffic model for a two-link network from the perspective of system-optimal principle. Generally, two types of day-to-day models have been studied in the literature, i.e., continuous time models and discrete time models, and each type can be subcategorized into two groups, i.e., deterministic models and stochastic models [21, 22]. The continuous time models utilize differential equations to describe traffic evolution based on the assumption that travelers have a perfect perception of travel cost, which can capture the mathematical features in traffic transition [23–25]. The discrete time models assume that travelers repeat their route choice behavior each day following the traffic condition, which is more suited to the real world as mentioned by Watling and Hazelton [19]. Since the uncertainty associated with the random nature exists in the traffic evolution process, stochastic day-to-day traffic models get more attention from scholars than the deterministic day-to-day models. Most stochastic day-to-day traffic models follow Markov processes, which predict the traffic state by calculating transition matrices based on the previous traffic flow patterns [26–29]. Due to the advantages claimed above, day-to-day traffic models recently have been used in combination with other methods to solve some practical transportation problems. For example, Liu et al. [30] combined a path-based day-to-day traffic model with a robust optimization method to investigate distance-based congestion pricing problems. Faturechi and Miller-Hooks [18] developed a methodology framework composed of three-stage stochastic mathematical programming and a day-to-day traffic model to simulate postdisaster travel time resilience of roadway networks. However, most of the previous day-to-day traffic models are path-based and assume that travelers have infinite memories.


## 3. Formulation of the Problem

### 3.1. Assumptions and Notations

This study makes the following assumptions:(1)
The travel demands between each origin-destination (OD) pair keep constant during the restoration process.(2)
Each restoration activity is implemented by a single work crew. Once a restoration activity begins, the work crew has to finish the restoration activity prior to conducting the next restoration activity.(3)
Each restoration activity only begins once during the entire restoration process, i.e., the restoration strategy is non-preemptive.(4)
The capacity of each damaged road segment is reduced when the disaster occurs, and the capacity is not restored to the predisaster level until the damaged road segment is completely restored.(5)
Due to sufficient preparations, the decision makers have a complete understanding of the damage state information for the road network; thus, the restoration time, the restoration cost, and other parameter values are known.The notations used in this study are presented as follows.


#### 3.1.1. Indices

(1)
d: time period(2)
i: road segment to be restored or restoration activity(3)
r: work crew


#### 3.1.2. Parameters

(1)
I: total number of road segments to be restored or restoration activities(2)
ei: duration of restoration activity i, i=1,2,…,I(3)
ci: cost of restoration activity i, i=1,2,…,I(4)
R: total number of work crews(5)
B: availability of budget(6)
Mmax: maximum acceptable makespan of the restoration


#### 3.1.3. Variables

(1)
C: total costs of the restoration(2)
M: makespan of the restoration(3)
πd: network performance on day d, d=1,2,…,Mmax(4)
Td: total system travel time on day d, d=1,2,…,Mmax(5)
Rp: resilience of performance loss(6)
Rr: resilience of recovery rapidity(7)
xid: binary variable that represents xid=1 if road segment i is to be restored on day d; otherwise, xid=0, i=1,2,…,I, d=1,2,…,Mmax(8)
yir: binary variable that means yir=1 if road segment i is to be restored by work crew r; otherwise, yir=0, i=1,2,…,I, r=1,2,…,R.


### 3.2. Resilience Metrics

Consider a road network, denoted asG=N,A, where N is the set of nodes and A is the set of road segments (or links). A disaster caused by extreme weather occurs on day d=ds, which damages I road segments in the network. Hence, the network performance πd drops to πds from the predisaster network performance πd0. Figure 1 plots the postdisaster network performance recovery process. Assume that the restoration is conducted immediately on day d=ds, which aims to recover πd to πd0. Since the restoration budget cannot cover all the disrupted road segments, πd is recovered to πds+M when the budget is exhausted on day d=ds+M. The restoration activities have to be completed with Mmax days. πd will be further improved if more investments are available in the future.Figure 1
Postdisaster network performance recovery process.Since there is a negative relationship between the road network performance and TSTT, we defineπd as the reciprocal of TSTT on day d divided by the reciprocal of the predisaster TSTT on day d0, as in equation (1). πd is the ratio of Td0 to Td, which reveals efficiencies in the use of a road network. The lower TSTT is, the higher πd is.(1)πd=Td−1Td0−1=Td0Td.It is clear thatπd∈0,1 and the predisaster network performance πd0 equals to 1. When all the damaged road segments are restored, πd will be recovered to 1.Then, we develop two resilience metrics, i.e., the resilience of performance loss and resilience of recovery rapidity to evaluate the postdisaster network resilience [12, 31].


#### 3.2.1. Resilience of Performance Loss

The shaded area in Figure1 represents the performance loss. Figure 1 shows that the performance loss still exists after the restoration activities are completed on day d=ds+M. For simplicity, we calculate the total performance loss TPL from day d=ds to day d=ds+Mmax, which is formulated in the following equation:(2)TPL=∫dsds+Mmaxπd0−πxdx≈Mmax×πd0−∑d=dsds+Mmaxπd.Then, we formulate the resilience of performance loss as(3)Rp=1−Mmax×πd0−∑d=dsds+MmaxπdMmax×πd0,where Rp represents the proportion of residual performance (i.e., overall performance minus lost performance) in overall performance within Mmax days and Rp reflects the function of the road network. The higher Rp is, the lower the total performance loss is and the less the traffic congestion is. Rp∈0,1.


#### 3.2.2. Resilience of Recovery Rapidity

Since recovery rapidity has a great priority during the restoration process, we employ the resilience of recovery rapidity as another resilience metric. We normalize and formulate the resilience of recovery rapidity as in the following equation:(4)Rr=1−MMmax,M≤Mmax,0,M>Mmax,where Rr represents the speed of recovery. If M>Mmax, the recovery rapidity is too low, which is unacceptable. If M≤Mmax, the higher Rr, the faster the road network can be repaired. Rr∈0,1.


### 3.3. Link-Based Day-to-Day Dynamics Model

Before modeling the optimal RNRS problem, we first propose a link-based day-to-day dynamics model. For simplicity, we assume that restoration activities are conducted on dayd=ds=1. The restoration activities will result in changes in the travelers’ route choice behaviors, giving rise to day-to-day flow fluctuations. In order to estimate TSTT, a mechanism is needed to simulate the postdisaster network flow evolution trajectory [32]. Since the initial link flow pattern is easily observed by a well-designed field survey and each restoration activity is involved with a road segment, a link-based traffic model is more suitable to predict the network flow evolution trajectory in the context of the road network restoration.In a link-based day-to-day dynamics model, link flows on any dayd, denoted by qd=qi,i∈NT, tend to evolve towards the “target” link flows q^d+1=qi^,i∈NT on day d+1 at a rate of v [16]. Hence, qd+1 can be formulated as a weighted combination in the following equation:(5)qd+1=qd+v⋅q^d+1−qd.For a givenqd, q^d+1 solves the following minimization problem:(6)minQ∈Ωdλ⋅hq,d+1TQ+1−λ⋅Dqd,Q,(7)Ωd=qd|qd=Δfd,Λfd=Θ,fd≥0,where Ωd is a feasibility vector set of link flows on day d. Δ is the link-path incidence matrix, Δ=Δi,k,w,i∈N,k∈Kw,w∈W. Δi,k,w=1 if link i∈N lies on path k∈Kw, and Δi,k,w=0 otherwise. Λ is the OD pair-path incidence matrix, Λ=Λk,w,k∈Kw,w∈W. Λk,w=1 if path k∈Kw connects OD pair w∈W, and Λk,w=0 otherwise. fd is the vector of path flows on day d. fd=fk,wd,k∈Kw,w∈WT. Θ is the vector of traffic demands between OD pairs. Θ=Θw,w∈WT. λ0≤λ≤1 is travelers’ sensitivity to travel time. The larger the parameter value of λ, the more travelers will change their routes. hq,d+1 is the travel time perceived by the travelers on day d+1. Equation (6) is a weighted combination of minQ∈Ωdhq,d+1TQ and minQ∈ΩdDqd,Q. The former aims to minimize the total travel time of qd+1, and the latter guarantees the minimal distance between qd and Q.Dqd,Q can be calculated by(8)Dqd,Q=∑i∈N∫qi,dQi,d+1ti,du−ti,dqi,ddu,where ti,du is the link travel time function.As forhq,d+1 in a link-based day-to-day dynamics model, it can be formulated as a weighted average between their perceived travel time on day d and the experienced travel time on day d [33].(9)hq,d+1=μ⋅tq,d+1−μ⋅hq,d.Then, we expand equation (9) recursively as follows:(10)hq,d+1=μ⋅tq,d+1−μ⋅hq,d=μ⋅tq,d+1−μμ⋅tq,d−1+1−μ⋅hq,d−1=μ⋅tq,d+μ⋅1−μ⋅tq,d−1+1−μ2⋅hq,d−1=μ⋅tq,d+μ⋅1−μ⋅tq,d−1+1−μ2⋅μ⋅tq,d−2+1−μ⋅hq,d−2……=μ⋅tq,d+μ⋅∑s=2d−11−μs−1⋅tq,d−s+1+1−μd⋅hq,1.where tq,d is the travelers’ experienced travel time on day d. The initial perceived travel time hq,1 can be estimated by reassigning the traffic flows following the network capacity reduction on day d=1. q1 is an optimal solution to the following minimization model:(11)minq1∈Ω1∑i∈N∫0qi1tiu,Ci1du,where Ci1is the capacity of link i on day d=1. Ω1 can be obtained using equation (7).Equation (10) reveals that travelers’ perceived travel time is largely dependent on all of their previous experienced travel time. Equation (10) assumes that travelers have infinite memories, which is not realistic. As mentioned by Cascetta [27], travelers’ perceived travel time is mainly affected by their finite memory, namely, travelers cannot remember all of their experiences in the past. Thus, we make the following assumption:Assumption 1.
. Travelers’ perceived travel time on dayd is affected by their most recent m days’ experienced travel time. m is defined as the travelers’ memory length.
Based on Assumption1, equation (10) can be rewritten as follows:(12)hq,d+1=μ⋅tq,d+μ⋅∑s=2m1−μs−1⋅tq,d−s+1+1−μd⋅hq,1.
It is easy to know that the sum of the two coefficients, i.e.,μ and μ⋅∑s=2m1−μs−1 in equation (12) does not equal to 1. Hence, we employ a scaling factor to make the coefficients sum to 1. Equation (12) is further transformed to the following:(13)hq,d+1=μ1−1−μm+1⋅tq,d+μ1−1−μm+1⋅∑s=2m1−μs−1⋅tq,d−s+1+1−μd⋅hq,1,where μ/1−1−μm+1+μ/1−1−μm+1⋅∑s=2m1−μs−1=1.
Hence, TSTT on dayd in equation (1) can be calculated as(14)Td=qd⋅td.
It is easy to know that the postdisaster road network capacity will change when every single road segment is restored, thus giving rise to a new day-to-day flow evolution, namely, there are multiple “new evolutions” during the restoration process. Therefore, when a “new evolution” occurs, i.e., at the end of each restoration activity, the value ofd in the link-based day-to-day dynamics model should be reset to 1.


### 3.4. Optimization Model

In this subsection, we formulate the postdisaster RNRS problem as a resilience-based bi-objective mixed integer programming model under resource constraints, which makes a tradeoff between the maximal resilience of performance loss and the maximal resilience of recovery rapidity. For simplicity, this model assumesds=1.(15)maxRp=1−Mmax×πd0−∑d=dsds+MmaxπdMmax×πd0,(16)maxRr=1−MMmax,M≤Mmax,0,M>Mmax,which subject to the following:(17)maxi∑d=1Mmaxd⋅xid+ei=M≤Mmax,(18)∑d=1Mmaxd⋅xid=1,i=1,2,…,I,(19)∑r=1Ryir=1,i=1,2,…,I,(20)∑τ=max1,d−ei+1d∑i=1Ixiτ⋅yir≤1,d=1,2,…,Mmax,r=1,2,…,R,(21)∑τ=max1,d−ei+1d∑i=1Ixiτ≤R,d=1,2,…,Mmax,(22)∑i=1I∑d=1Mmaxxid⋅ci=C≤B,(23)xid=0,1,(24)yir=0,1.Equations (15) and (16) are two objectives, which maximize the resilience of performance loss and the resilience of recovery rapidity, respectively. Equation (17) defines the makespan of the restoration schedule, i.e., the finish time of the last restoration activity, which cannot exceed Mmax. Equation (18) ensures that each restoration activity is implemented only once during the restoration period, namely, the restoration strategy is non-preemptive. Equation (19) guarantees that each restoration activity is carried out by a single work crew. Equation (20) ensures that each work crew can only conduct one restoration activity at most every single day. Equation (21) makes sure that the number of ongoing restoration activities every single day cannot exceed the number of work crews. Equation (22) is the budget constraint, i.e., the total restoration costs cannot exceed the budget. Equations (23) and (24) define the type of decision variables.


## 3.1. Assumptions and Notations

This study makes the following assumptions:(1)
The travel demands between each origin-destination (OD) pair keep constant during the restoration process.(2)
Each restoration activity is implemented by a single work crew. Once a restoration activity begins, the work crew has to finish the restoration activity prior to conducting the next restoration activity.(3)
Each restoration activity only begins once during the entire restoration process, i.e., the restoration strategy is non-preemptive.(4)
The capacity of each damaged road segment is reduced when the disaster occurs, and the capacity is not restored to the predisaster level until the damaged road segment is completely restored.(5)
Due to sufficient preparations, the decision makers have a complete understanding of the damage state information for the road network; thus, the restoration time, the restoration cost, and other parameter values are known.The notations used in this study are presented as follows.


### 3.1.1. Indices

(1)
d: time period(2)
i: road segment to be restored or restoration activity(3)
r: work crew


### 3.1.2. Parameters

(1)
I: total number of road segments to be restored or restoration activities(2)
ei: duration of restoration activity i, i=1,2,…,I(3)
ci: cost of restoration activity i, i=1,2,…,I(4)
R: total number of work crews(5)
B: availability of budget(6)
Mmax: maximum acceptable makespan of the restoration


### 3.1.3. Variables

(1)
C: total costs of the restoration(2)
M: makespan of the restoration(3)
πd: network performance on day d, d=1,2,…,Mmax(4)
Td: total system travel time on day d, d=1,2,…,Mmax(5)
Rp: resilience of performance loss(6)
Rr: resilience of recovery rapidity(7)
xid: binary variable that represents xid=1 if road segment i is to be restored on day d; otherwise, xid=0, i=1,2,…,I, d=1,2,…,Mmax(8)
yir: binary variable that means yir=1 if road segment i is to be restored by work crew r; otherwise, yir=0, i=1,2,…,I, r=1,2,…,R.


## 3.1.1. Indices

(1)
d: time period(2)
i: road segment to be restored or restoration activity(3)
r: work crew


## 3.1.2. Parameters

(1)
I: total number of road segments to be restored or restoration activities(2)
ei: duration of restoration activity i, i=1,2,…,I(3)
ci: cost of restoration activity i, i=1,2,…,I(4)
R: total number of work crews(5)
B: availability of budget(6)
Mmax: maximum acceptable makespan of the restoration


## 3.1.3. Variables

(1)
C: total costs of the restoration(2)
M: makespan of the restoration(3)
πd: network performance on day d, d=1,2,…,Mmax(4)
Td: total system travel time on day d, d=1,2,…,Mmax(5)
Rp: resilience of performance loss(6)
Rr: resilience of recovery rapidity(7)
xid: binary variable that represents xid=1 if road segment i is to be restored on day d; otherwise, xid=0, i=1,2,…,I, d=1,2,…,Mmax(8)
yir: binary variable that means yir=1 if road segment i is to be restored by work crew r; otherwise, yir=0, i=1,2,…,I, r=1,2,…,R.


## 3.2. Resilience Metrics

Consider a road network, denoted asG=N,A, where N is the set of nodes and A is the set of road segments (or links). A disaster caused by extreme weather occurs on day d=ds, which damages I road segments in the network. Hence, the network performance πd drops to πds from the predisaster network performance πd0. Figure 1 plots the postdisaster network performance recovery process. Assume that the restoration is conducted immediately on day d=ds, which aims to recover πd to πd0. Since the restoration budget cannot cover all the disrupted road segments, πd is recovered to πds+M when the budget is exhausted on day d=ds+M. The restoration activities have to be completed with Mmax days. πd will be further improved if more investments are available in the future.Figure 1
Postdisaster network performance recovery process.Since there is a negative relationship between the road network performance and TSTT, we defineπd as the reciprocal of TSTT on day d divided by the reciprocal of the predisaster TSTT on day d0, as in equation (1). πd is the ratio of Td0 to Td, which reveals efficiencies in the use of a road network. The lower TSTT is, the higher πd is.(1)πd=Td−1Td0−1=Td0Td.It is clear thatπd∈0,1 and the predisaster network performance πd0 equals to 1. When all the damaged road segments are restored, πd will be recovered to 1.Then, we develop two resilience metrics, i.e., the resilience of performance loss and resilience of recovery rapidity to evaluate the postdisaster network resilience [12, 31].


### 3.2.1. Resilience of Performance Loss

The shaded area in Figure1 represents the performance loss. Figure 1 shows that the performance loss still exists after the restoration activities are completed on day d=ds+M. For simplicity, we calculate the total performance loss TPL from day d=ds to day d=ds+Mmax, which is formulated in the following equation:(2)TPL=∫dsds+Mmaxπd0−πxdx≈Mmax×πd0−∑d=dsds+Mmaxπd.Then, we formulate the resilience of performance loss as(3)Rp=1−Mmax×πd0−∑d=dsds+MmaxπdMmax×πd0,where Rp represents the proportion of residual performance (i.e., overall performance minus lost performance) in overall performance within Mmax days and Rp reflects the function of the road network. The higher Rp is, the lower the total performance loss is and the less the traffic congestion is. Rp∈0,1.


### 3.2.2. Resilience of Recovery Rapidity

Since recovery rapidity has a great priority during the restoration process, we employ the resilience of recovery rapidity as another resilience metric. We normalize and formulate the resilience of recovery rapidity as in the following equation:(4)Rr=1−MMmax,M≤Mmax,0,M>Mmax,where Rr represents the speed of recovery. If M>Mmax, the recovery rapidity is too low, which is unacceptable. If M≤Mmax, the higher Rr, the faster the road network can be repaired. Rr∈0,1.


## 3.2.1. Resilience of Performance Loss

The shaded area in Figure1 represents the performance loss. Figure 1 shows that the performance loss still exists after the restoration activities are completed on day d=ds+M. For simplicity, we calculate the total performance loss TPL from day d=ds to day d=ds+Mmax, which is formulated in the following equation:(2)TPL=∫dsds+Mmaxπd0−πxdx≈Mmax×πd0−∑d=dsds+Mmaxπd.Then, we formulate the resilience of performance loss as(3)Rp=1−Mmax×πd0−∑d=dsds+MmaxπdMmax×πd0,where Rp represents the proportion of residual performance (i.e., overall performance minus lost performance) in overall performance within Mmax days and Rp reflects the function of the road network. The higher Rp is, the lower the total performance loss is and the less the traffic congestion is. Rp∈0,1.


## 3.2.2. Resilience of Recovery Rapidity

Since recovery rapidity has a great priority during the restoration process, we employ the resilience of recovery rapidity as another resilience metric. We normalize and formulate the resilience of recovery rapidity as in the following equation:(4)Rr=1−MMmax,M≤Mmax,0,M>Mmax,where Rr represents the speed of recovery. If M>Mmax, the recovery rapidity is too low, which is unacceptable. If M≤Mmax, the higher Rr, the faster the road network can be repaired. Rr∈0,1.


## 3.3. Link-Based Day-to-Day Dynamics Model

Before modeling the optimal RNRS problem, we first propose a link-based day-to-day dynamics model. For simplicity, we assume that restoration activities are conducted on dayd=ds=1. The restoration activities will result in changes in the travelers’ route choice behaviors, giving rise to day-to-day flow fluctuations. In order to estimate TSTT, a mechanism is needed to simulate the postdisaster network flow evolution trajectory [32]. Since the initial link flow pattern is easily observed by a well-designed field survey and each restoration activity is involved with a road segment, a link-based traffic model is more suitable to predict the network flow evolution trajectory in the context of the road network restoration.In a link-based day-to-day dynamics model, link flows on any dayd, denoted by qd=qi,i∈NT, tend to evolve towards the “target” link flows q^d+1=qi^,i∈NT on day d+1 at a rate of v [16]. Hence, qd+1 can be formulated as a weighted combination in the following equation:(5)qd+1=qd+v⋅q^d+1−qd.For a givenqd, q^d+1 solves the following minimization problem:(6)minQ∈Ωdλ⋅hq,d+1TQ+1−λ⋅Dqd,Q,(7)Ωd=qd|qd=Δfd,Λfd=Θ,fd≥0,where Ωd is a feasibility vector set of link flows on day d. Δ is the link-path incidence matrix, Δ=Δi,k,w,i∈N,k∈Kw,w∈W. Δi,k,w=1 if link i∈N lies on path k∈Kw, and Δi,k,w=0 otherwise. Λ is the OD pair-path incidence matrix, Λ=Λk,w,k∈Kw,w∈W. Λk,w=1 if path k∈Kw connects OD pair w∈W, and Λk,w=0 otherwise. fd is the vector of path flows on day d. fd=fk,wd,k∈Kw,w∈WT. Θ is the vector of traffic demands between OD pairs. Θ=Θw,w∈WT. λ0≤λ≤1 is travelers’ sensitivity to travel time. The larger the parameter value of λ, the more travelers will change their routes. hq,d+1 is the travel time perceived by the travelers on day d+1. Equation (6) is a weighted combination of minQ∈Ωdhq,d+1TQ and minQ∈ΩdDqd,Q. The former aims to minimize the total travel time of qd+1, and the latter guarantees the minimal distance between qd and Q.Dqd,Q can be calculated by(8)Dqd,Q=∑i∈N∫qi,dQi,d+1ti,du−ti,dqi,ddu,where ti,du is the link travel time function.As forhq,d+1 in a link-based day-to-day dynamics model, it can be formulated as a weighted average between their perceived travel time on day d and the experienced travel time on day d [33].(9)hq,d+1=μ⋅tq,d+1−μ⋅hq,d.Then, we expand equation (9) recursively as follows:(10)hq,d+1=μ⋅tq,d+1−μ⋅hq,d=μ⋅tq,d+1−μμ⋅tq,d−1+1−μ⋅hq,d−1=μ⋅tq,d+μ⋅1−μ⋅tq,d−1+1−μ2⋅hq,d−1=μ⋅tq,d+μ⋅1−μ⋅tq,d−1+1−μ2⋅μ⋅tq,d−2+1−μ⋅hq,d−2……=μ⋅tq,d+μ⋅∑s=2d−11−μs−1⋅tq,d−s+1+1−μd⋅hq,1.where tq,d is the travelers’ experienced travel time on day d. The initial perceived travel time hq,1 can be estimated by reassigning the traffic flows following the network capacity reduction on day d=1. q1 is an optimal solution to the following minimization model:(11)minq1∈Ω1∑i∈N∫0qi1tiu,Ci1du,where Ci1is the capacity of link i on day d=1. Ω1 can be obtained using equation (7).Equation (10) reveals that travelers’ perceived travel time is largely dependent on all of their previous experienced travel time. Equation (10) assumes that travelers have infinite memories, which is not realistic. As mentioned by Cascetta [27], travelers’ perceived travel time is mainly affected by their finite memory, namely, travelers cannot remember all of their experiences in the past. Thus, we make the following assumption:Assumption 1.
. Travelers’ perceived travel time on dayd is affected by their most recent m days’ experienced travel time. m is defined as the travelers’ memory length.
Based on Assumption1, equation (10) can be rewritten as follows:(12)hq,d+1=μ⋅tq,d+μ⋅∑s=2m1−μs−1⋅tq,d−s+1+1−μd⋅hq,1.
It is easy to know that the sum of the two coefficients, i.e.,μ and μ⋅∑s=2m1−μs−1 in equation (12) does not equal to 1. Hence, we employ a scaling factor to make the coefficients sum to 1. Equation (12) is further transformed to the following:(13)hq,d+1=μ1−1−μm+1⋅tq,d+μ1−1−μm+1⋅∑s=2m1−μs−1⋅tq,d−s+1+1−μd⋅hq,1,where μ/1−1−μm+1+μ/1−1−μm+1⋅∑s=2m1−μs−1=1.
Hence, TSTT on dayd in equation (1) can be calculated as(14)Td=qd⋅td.
It is easy to know that the postdisaster road network capacity will change when every single road segment is restored, thus giving rise to a new day-to-day flow evolution, namely, there are multiple “new evolutions” during the restoration process. Therefore, when a “new evolution” occurs, i.e., at the end of each restoration activity, the value ofd in the link-based day-to-day dynamics model should be reset to 1.


## 3.4. Optimization Model

In this subsection, we formulate the postdisaster RNRS problem as a resilience-based bi-objective mixed integer programming model under resource constraints, which makes a tradeoff between the maximal resilience of performance loss and the maximal resilience of recovery rapidity. For simplicity, this model assumesds=1.(15)maxRp=1−Mmax×πd0−∑d=dsds+MmaxπdMmax×πd0,(16)maxRr=1−MMmax,M≤Mmax,0,M>Mmax,which subject to the following:(17)maxi∑d=1Mmaxd⋅xid+ei=M≤Mmax,(18)∑d=1Mmaxd⋅xid=1,i=1,2,…,I,(19)∑r=1Ryir=1,i=1,2,…,I,(20)∑τ=max1,d−ei+1d∑i=1Ixiτ⋅yir≤1,d=1,2,…,Mmax,r=1,2,…,R,(21)∑τ=max1,d−ei+1d∑i=1Ixiτ≤R,d=1,2,…,Mmax,(22)∑i=1I∑d=1Mmaxxid⋅ci=C≤B,(23)xid=0,1,(24)yir=0,1.Equations (15) and (16) are two objectives, which maximize the resilience of performance loss and the resilience of recovery rapidity, respectively. Equation (17) defines the makespan of the restoration schedule, i.e., the finish time of the last restoration activity, which cannot exceed Mmax. Equation (18) ensures that each restoration activity is implemented only once during the restoration period, namely, the restoration strategy is non-preemptive. Equation (19) guarantees that each restoration activity is carried out by a single work crew. Equation (20) ensures that each work crew can only conduct one restoration activity at most every single day. Equation (21) makes sure that the number of ongoing restoration activities every single day cannot exceed the number of work crews. Equation (22) is the budget constraint, i.e., the total restoration costs cannot exceed the budget. Equations (23) and (24) define the type of decision variables.


## 4. Model Solution

Bi-objective models are usually solved to obtain a set of Pareto optimal solutions [34]. Although all the obtained Pareto optimal solutions are feasible, the best solution cannot be determined because of the different scales and bounds of the two objectives. In order to solve the issue, we first transform the bi-objective model into a single objective model using the weighted combination method as follows [12]. A genetic algorithm (GA) is then adopted to deal with the single objective model.(25)F=ω⋅Rt+1−ω⋅Rr,where F is the weighted value and ω is the weighting factor, which means the decision makers’ preference for the two resilience metrics.The mixed integer programming model has been widely employed to solve network design and network restoration problems, which are known to be NP-hard. Due to the NP-hardness, finding the exact solution is an intractable issue even for small problems; thus, heuristic algorithms are more suitable than exact algorithms for solving these problems. GA has been well recognized as an effective tool to solve the optimization problem [35–37]. GA searches for the optimal solution by simulating the natural evolution process; specifically, it simulates the solution of problems as a process similar to the crossover and mutation of chromosome genes in biological evolution [38]. GA is also used in combination with other algorithms (e.g., simulated annealing algorithms [39, 40], swarm intelligence algorithms [41], neural network algorithms [42], and tabu search algorithm [43]) to solve optimization problems. Compared with the previous algorithms, GA in this study represents the chromosome with two line sections using the integer coding method, which can reduce the possibility of generating a large number of infeasible solutions and avoid unnecessary searches. The flow chart of GA is presented in Figure 2.Figure 2
Flow chart of GA.


### 4.1. Chromosome Encoding and Decoding

The RNRS problem in this study consists of two subproblems, i.e., the selection of work crews for road segments to be restored and the time sequence of restoration activities. We apply the integer coding method to represent the chromosome with two line sections shown in Figure3. Each line section has I genes. The gen value gi1i=1,2,…,I of line section 1 represents the work crew that will restore the corresponding link. It is noting that the gen value 0 in line section 1 means that the corresponding link will not be restored. gi1=0,1,2,…,R. The gen value gi2i=1,2,…,I of line section 2 indicates the precedence relationship among all restoration activities. gi2=1,2,…,I. The smaller gi2, the higher the priority of the restoration activity. All gen values in line section 2 are different.Figure 3
The chromosome representation.LetMArr=1,2,…,R be the set of restoration activities assigned to work crew r, where restoration activities are ranked by their priorities from high to low, and the number of restoration activities in MAr is Numr. It is noting that these restoration activities with gi1=0 are not included in MAr. We denote EAr as the set of eligible restoration activities, namely, the unscheduled restoration activities that have all predecessor restoration activities scheduled, and we let STrjj=1,2,…,Numr represent the start time of the jth restoration activity in MAr. Then, the following decoding procedure can be used to transform the solution into a restoration schedule.(i)
Step 1. Set r=1, MAr=1, and STr1=0.(ii)
Step 2. Update EAr, i.e., remove the scheduled restoration activities from EAr and put the new eligible restoration activities into EAr.(iii)
Step 3. Judge whether EAr=∅ or not. If the answer is true, output all STrj and go to step 5; otherwise, go to step 4.(iv)
Step 4. Calculate STrj of all the eligible restoration activities, STrj=STr,j−1+dj, and return to step 2.(v)Step 5. Judge whether r=R or not. If the answer is false, let r=r+1 and return to step 2; otherwise, terminate the procedure.


### 4.2. Population Initialization

The initial population consists ofpopSize feasible initial solutions. Each feasible initial solution can be generated using the following steps:(i)
Step 1. Randomly generate a value for gi1, gi1=0,1,2,…,R, i=1,2,…,N, namely, select a work crew for each restoration activity randomly, generating line section 1.(ii)
Step 2. Randomly generate a value for gi2,gi2=1,2,…,N, i=1,2,…,N, namely, set a priority value for each restoration activity randomly, generating line section 2.(iii)
Step 3. Transform the generated gi1 and gi2 into a restoration schedule using the decoding procedure presented in Section 4.1. Judge whether maxi,rSTri+di≤Mmax or not. If the answer is true, a feasible solution has been generated; otherwise, return to step 1 and repeat the procedure until a feasible solution is generated.


### 4.3. Selection

We use equation (25) as the fitness function in this algorithm. The fitness value of the parent individual determines the probability that the child individual is selected. Specifically, the higher the fitness value of the parent individuals, the higher the probability that they will be selected to generate offspring individuals. The roulette wheel method is employed to select individuals. Denote Fkk=1,2,…,popSize as the fitness value of the kth individual. The total fitness value Ftotal of a population of size popSize can be calculated as(26)Ftotal=∑k=1popSizeFk.The selection probabilitypk for each individual k is formulated in the following equation [44]:(27)pk=Ftotal−FkFtotal⋅popSize−1.Then, a random numberφ∈0,1 is generated. If pk−1<φ<pk, the kth individual is selected.


### 4.4. Crossover Operator

A crossover operator is used to generate two new offspring individuals from two parent chromosomes by exchanging their genetic information [45], which can maintain population diversity. The crossover operator is performed based on a crossover rate that determines the probability that two parent individuals will be selected to exchange their genetic information. A single point crossover method is applied in this study. It is noting that only line section 1 is selected to crossover so as to change the job sequence of work crews. The crossover operation is performed by choosing a position i in line section 1 of the chromosome randomly and swapping all the gen values before that position. Thus, the first i gen values in line section 1 of an offspring chromosome are selected from one parent chromosome and the remaining gen values inherit the other parent chromosome. Figure 4 illustrates an example of a single point crossover operation.Figure 4
An example of a single point crossover operation.


### 4.5. Mutation Operator

The mutation operation is performed to a single chromosome, which can help the algorithm to avoid local optima. Based on a mutation rate, the mutation operation randomly changes one or more gene values of a chromosome. The widely used swap mutation strategy [46] that randomly exchanges two gene values of a chromosome is applied to the two line sections. Figure 5 shows an example of a swap mutation strategy.Figure 5
An example of a swap mutation strategy.


## 4.1. Chromosome Encoding and Decoding

The RNRS problem in this study consists of two subproblems, i.e., the selection of work crews for road segments to be restored and the time sequence of restoration activities. We apply the integer coding method to represent the chromosome with two line sections shown in Figure3. Each line section has I genes. The gen value gi1i=1,2,…,I of line section 1 represents the work crew that will restore the corresponding link. It is noting that the gen value 0 in line section 1 means that the corresponding link will not be restored. gi1=0,1,2,…,R. The gen value gi2i=1,2,…,I of line section 2 indicates the precedence relationship among all restoration activities. gi2=1,2,…,I. The smaller gi2, the higher the priority of the restoration activity. All gen values in line section 2 are different.Figure 3
The chromosome representation.LetMArr=1,2,…,R be the set of restoration activities assigned to work crew r, where restoration activities are ranked by their priorities from high to low, and the number of restoration activities in MAr is Numr. It is noting that these restoration activities with gi1=0 are not included in MAr. We denote EAr as the set of eligible restoration activities, namely, the unscheduled restoration activities that have all predecessor restoration activities scheduled, and we let STrjj=1,2,…,Numr represent the start time of the jth restoration activity in MAr. Then, the following decoding procedure can be used to transform the solution into a restoration schedule.(i)
Step 1. Set r=1, MAr=1, and STr1=0.(ii)
Step 2. Update EAr, i.e., remove the scheduled restoration activities from EAr and put the new eligible restoration activities into EAr.(iii)
Step 3. Judge whether EAr=∅ or not. If the answer is true, output all STrj and go to step 5; otherwise, go to step 4.(iv)
Step 4. Calculate STrj of all the eligible restoration activities, STrj=STr,j−1+dj, and return to step 2.(v)Step 5. Judge whether r=R or not. If the answer is false, let r=r+1 and return to step 2; otherwise, terminate the procedure.


## 4.2. Population Initialization

The initial population consists ofpopSize feasible initial solutions. Each feasible initial solution can be generated using the following steps:(i)
Step 1. Randomly generate a value for gi1, gi1=0,1,2,…,R, i=1,2,…,N, namely, select a work crew for each restoration activity randomly, generating line section 1.(ii)
Step 2. Randomly generate a value for gi2,gi2=1,2,…,N, i=1,2,…,N, namely, set a priority value for each restoration activity randomly, generating line section 2.(iii)
Step 3. Transform the generated gi1 and gi2 into a restoration schedule using the decoding procedure presented in Section 4.1. Judge whether maxi,rSTri+di≤Mmax or not. If the answer is true, a feasible solution has been generated; otherwise, return to step 1 and repeat the procedure until a feasible solution is generated.


## 4.3. Selection

We use equation (25) as the fitness function in this algorithm. The fitness value of the parent individual determines the probability that the child individual is selected. Specifically, the higher the fitness value of the parent individuals, the higher the probability that they will be selected to generate offspring individuals. The roulette wheel method is employed to select individuals. Denote Fkk=1,2,…,popSize as the fitness value of the kth individual. The total fitness value Ftotal of a population of size popSize can be calculated as(26)Ftotal=∑k=1popSizeFk.The selection probabilitypk for each individual k is formulated in the following equation [44]:(27)pk=Ftotal−FkFtotal⋅popSize−1.Then, a random numberφ∈0,1 is generated. If pk−1<φ<pk, the kth individual is selected.


## 4.4. Crossover Operator

A crossover operator is used to generate two new offspring individuals from two parent chromosomes by exchanging their genetic information [45], which can maintain population diversity. The crossover operator is performed based on a crossover rate that determines the probability that two parent individuals will be selected to exchange their genetic information. A single point crossover method is applied in this study. It is noting that only line section 1 is selected to crossover so as to change the job sequence of work crews. The crossover operation is performed by choosing a position i in line section 1 of the chromosome randomly and swapping all the gen values before that position. Thus, the first i gen values in line section 1 of an offspring chromosome are selected from one parent chromosome and the remaining gen values inherit the other parent chromosome. Figure 4 illustrates an example of a single point crossover operation.Figure 4
An example of a single point crossover operation.


## 4.5. Mutation Operator

The mutation operation is performed to a single chromosome, which can help the algorithm to avoid local optima. Based on a mutation rate, the mutation operation randomly changes one or more gene values of a chromosome. The widely used swap mutation strategy [46] that randomly exchanges two gene values of a chromosome is applied to the two line sections. Figure 5 shows an example of a swap mutation strategy.Figure 5
An example of a swap mutation strategy.


## 5. Numerical Experiment

### 5.1. Road Network

A road network with 19 nodes and 36 links shown in Figure6 is applied to validate the proposed method. The attributes of all links are presented in Table 1. There are two OD pairs, i.e., 1⟶17 and 8⟶19, the daily OD demands of which are 40,000 and 60,000, respectively. For simplicity, the predisaster link flows are obtained using a UE model.Figure 6
Layout of the testing road network.Table 1
Link attributes of the road network.
Linkti0 (h)Ci (Veh/h)Linkti0 (h)Ci (Veh/h)1–23.61,6009–102.22,0001–41.51,7009–142.81,6002–32.41,70010–111.82,2002–62.12,20010–152.51,7003–71.81,90011–121.52,4004–23.41,60011–151.92,0004–52.32,00012–131.72,2004–102.41,50012–161.82,2005–61.82,20012–172.32,4005–112.11,60013–171.91,6006–72.02,40014–151.71,7006–122.01,40014–181.72,2007–122.42,20015–161.72,0007–131.91,60015–192.01,6008–43.32,00016–171.32,0008–91.42,10016–191.81,7008–184.41,70017–192.92,0009–42.12,20018–192.62,200The link travel time is estimated by the Bureau of Public Roads (BPR) function:(28)tiqi=ti0⋅1+α⋅qiCiβ,∀i∈N,where ti0 is the free flow travel time on link i, Ci is the capacity of link i, and α and β are two parameters, where α=0.15 and β=4.Disasters usually cause two types of damage to the road infrastructure: (1) complete damage, which means that the capacity of each damaged road segment drops to zero and the damaged road segments are out of service, and (2) partial damage, which indicates that the capacity of each damaged road segment is reduced to a certain extent and the damaged road segments have some partial passage. For simplicity, we assume that a disaster, which occurs on dayd=1, completely damages 21 road segments (in the dashed-line circle in Figure 6). It is worth noting that our proposed method can be easily extended to the cases with partially damaged road segments. The damaged road segments are marked by red arrows in the dashed-line circle in Figure 6. The restoration duration and cost of each disrupted link are listed in Table 2, where the unit of ci is fund-unit. The total budget is 5,000 fund-unit. The other parameters are valued as in Table 3. The procedure is coded in MATLAB R2018b (version 11.4). All experiments are conducted on a Windows Server 2012 R2 server with an Intel Xeon E5-2640v4 CPU (2.4GHZ) and 64 GB DDR4 RAM.Table 2
Restoration duration and cost of each disrupted link.
Link IDei (day)ciqi,0(Veh)Link IDei (day)ciqi,0 (Veh)A6360193L7360206B7440548M6290364C4280304N8600353D6370201O5460458E6360255P6500302F7450280Q8510268G8640260R8480630H5170175S5450423I9590752T7420515J5240615U5350832K6340478Table 3
Parameter values used in this study.
ParametersValueMaximum allowed makespanMmax=60Link flow evolution ratev=1Travelers’ sensitivity to travel timeλ=0.5Travelers’ memory lengthm=3Total number of work crewsR=3Population sizepopSize=50Number of generationsGen=300Crossover probabilityPc=0.9Mutation probabilityPm=0.6Decision maker’s preferenceω=0.5


### 5.2. Results

We define the solution with the highest fitness value after convergence is the optimal solution. Figure7 illustrates the optimal RNRS generated by the proposed method. Figure 7(a) shows the start time and completion time of the restoration activity for each link, where the number on each bar is the duration of each restoration activity. Figure 7(b) presents the restoration activities assigned to each work crew, where the letter and number on each bar represent the link ID and restoration duration, respectively. This optimal RNRS covers 12 out of 21 disrupted links to be restored by three work crews, given that the restoration budget is 5,000 fund-unit. The makespan is 26 days. Figure 8 depicts the convergence process of the fitness values, which converges after 197 iterations. The best fitness value in the initial GA population is 0.231, and the fitness value reaches 0.612 after convergence.Figure 7
Optimal restoration strategy: (a) time sequence of maintenance; (b) job sequence of work crews.
(a)(b)Figure 8
Convergence process of fitness values.In practice, the empirical restoration strategy, i.e., flow-first strategy (FFS), is commonly used. FFS determines the time sequence of restoration activities by link flows from highest to lowest and covers as many links as possible until the budget is exhausted. According to the link flows listed in Table2, we generate a restoration scheme shown in Figure 9 following the FFS. In order to assess the efficiency of the optimal RNRS, we compare this optimal RNRS with the FFS. Table 4 lists the restoration results of the two strategies. Both strategies exhaust almost the same portion of the budget and cover 12 disrupted links. However, the optimal RNRS has a shorter makespan and produces much higher Rp and Rr. Obviously, the optimal RNRS outperforms the FFS, which indicates that the proposed method can recover the disrupted road network more quickly and generate fewer traffic delays.Figure 9
Flow-first restoration strategy: (a) time sequence of maintenance; (b) job sequence of work crews.
(a)(b)Table 4
Restoration results of the optimal RNRS and FFS.
Evaluation indexOptimal RNRSFFSRp0.4720.404Rr0.5670.533M2628C4,9904,940Figure10 presents the postdisaster TSTT evolution trajectories of the two restoration strategies. It is clear that TSTT has a significant fluctuation following the day-to-day traffic dynamics. Under the optimal RNRS, the postdisaster TSTT increases evidently and reaches the maximum equal to 3.12×106 on day d=2. As more links are recovered, TSTT gradually decreases. It is noting that although all the restoration activities are completed on day d=26, TSTT does not stop immediately and converges to a stationary (equilibrium) state on day d=31. Under the FFS, it takes 7 days for the network flows to reach the equilibrium state after the disaster and the equilibrium state continues for 14 days. This is because the FFS does not recover a new route till day d=20; thus, the network capacity does not increase until day d=20.Figure 10
Total system travel time evolution trajectories of the optimal RNRS and FFS.Since the road network flows cannot reach an equilibrium state overnight due to the network capacity variation, it is problematic to adopt UE models to simulate the traffic dynamics in this case. TSTT during the restoration makespan (i.e., 26 days) obtained by a day-to-day dynamics model and UE model for the two restoration strategies is compared in Figure11. From the comparison of results, it is known that TSTT is less under a UE model than under a day-to-day dynamics model.Figure 11
Total system travel time under a day-to-day dynamics model and UE model.More damage scenarios are generated to verify our proposed method and analyze the two objectives. We consider 3 damage scenarios, where 18–20 links in the dashed-line circle in Figure6 are randomly selected as the damaged road segments. For each scenario, there are C21ii=18,19,20 cases when i road segments are selected randomly to be damaged from the 21 road segments. The box plot for Rp and Rr of each scenario is presented in Figure 12. It can be found from Figure 12(a) that the maximum, minimum, median, upper quartile, and lower quartile of Rp all decrease as more road segments are damaged. As shown in Figure 12(b), the maximum and upper quartile of Rr decrease as more road segments are damaged. This phenomenon is in line with the fact that a network with more damaged road segments has lower resilience. It is also observed from Figure 12(b) that the lower quartile and the minimum of Rr keep constant in the three damage scenarios, which reveals that the three damage scenarios have the same worst-case optimal RNRS.Figure 12
Box plot for (a)Rp and (b).Rr.
(a)(b)


### 5.3. Sensitivity Analysis

In this subsection, we discuss the effects of key parameters including the number of work crews, travelers’ sensitivity to travel time, availability of budget, and decision makers’ preference on the restoration results. The sensitivity of every single parameter is analyzed by assuming other parameters are constant [47,48].


#### 5.3.1. Number of Work Crews

Table5 presents three optimal RNRSs for three different R. It is clear that the variation in R only affects the restoration time sequence but does not change the damaged links to be restored. The optimal RNRS of R=1 has the minimum Rp and Rr, which indicates this restoration schedule is the worst. When R=1, M=76, which is more than 60; thus Rr=0. Obviously, a higher R can reduce M, but the relationship between R and M is nonlinear. Generally, the restoration results are gradually improved with the increase in R. However, the growth rates of Rp and Rr decrease as R increases, i.e., the marginal benefits of manpower decrease. Additional experiments indicate that the marginal benefits of Rp and Rr equal to 0 when R=12, which reveals that overmuch manpower cannot improve the restoration results but produces resource waste. Additionally, insufficient manpower will delay the restoration period. Thus, our proposed methods can be employed to evaluate manpower allocation plans in real-life road network recovery.Table 5
Effect ofR on the optimal RNRS.
R135Rp0.3640.4720.519Rr0.0000.5670.717M762617C4,9904,9904,990Optimal RNRSWork crew 1: E-M-T-I-R-Q-K-J-P-S-U-OWork crew 1: E-I-J-SWork crew 1: E-Q——Work crew 2: M-R-K-UWork crew 2: M-K-U——Work crew 3: T-Q-P-OWork crew 3: T-J-O———Work crew 4: I–S———Work crew 5: R–P


#### 5.3.2. Travelers’ Sensitivity to Travel Time

Table6 shows three optimal RNRSs for three different λ. λ has a significant impact on the optimal RNRS including the restoration time sequence and the damaged links to be restored. As λ increases, the makespan is shortened, and both Rp and Rr increase. The larger the parameter value of λ, the more travelers will change their routes and the faster the link flows evolve to the new equilibrium state, thus causing less TSTT. Hence, in the actual RNRS, timely release of restoration information and effective traffic control strategies should be applied to help travelers to select the optimal route timely, which can improve the restoration schedule.Table 6
Effect ofλ on the optimal RNRS.
λ0.30.50.7Rp0.3570.4720.505Rr0.5330.5670.600M282624C4,9404,9904,480Optimal RNRSWork crew 1: A-K-E-J-UWork crew 1: E-I-J-SWork crew 1: A-I-E—Work crew 2: D-B-T-LWork crew 3: P–F-M-OWork crew 2: M-R-K-U—Work crew 3: T-Q-P-OWork crew 2: G-Q-OWork crew 3: P-T-M-U


#### 5.3.3. Availability of Budget

Table7 lists the optimal RNRSs under three different scenarios of budget constraints. The optimal RNRSs of B=5,000 and B=7,000 differ greatly both in the restoration time sequence and the damaged links to be restored. Compared with B=5,000, the optimal RNRS under B=7,000 covers 5 more damaged links, which extends the makespan by 9 days and has higher Rp but lower Rr. It is noting that the restoration schedule does not change when B increases from 7,000 to 8,000. This is because that the manpower is insufficient. Thus, simply increasing the budget and keeping the workforce unchanged cannot improve the restoration schedule. Therefore, the monetary resources and the manpower should be matched.Table 7
Effect ofB on the optimal RNRS.
B5,0007,0008,000Rp0.4720.5170.517Rr0.5670.3830.383M263737C4,9906,8906,890Optimal RNRSWork crew 1: E-I-J-SWork crew 1: E-A-Q-J-H-DWork crew 1: E-A-Q-J-H-D—Work crew 2: M-R-K-UWork crew 2: M-G-S-I-LWork crew 2: M-G-S-I-L—Work crew 3: T-Q-P-OWork crew 3: T-P-R-K-O-UWork crew 3: T-P-R-K-O-U


#### 5.3.4. Decision Maker’s Preference

Table8 indicates two optimal RNRSs for two different ω. Obviously, ω has a significant effect on the restoration schedule including the restoration time sequence and the damaged links to be restored. Compared with ω=0.5, the optimal RNRS with ω=0.3 is involved with 2 less damaged links, thus resulting in a lower Rp, M, and C but higher Rr, which represents more traffic delays and a shorter makespan. Hence, decision makers should make an optimal tradeoff between Rp and Rr.Table 8
Effect ofω on the optimal RNRS.
ω0.30.5Rp0.4130.472Rr0.6170.567M2326C4,3904,990Optimal RNRSWork crew 1: E-A-B-CWork crew 1: E-I-J-S—Work crew 2: M-G-IWork crew 2: M-R-K-U—Work crew 3: T-P-QWork crew 3: T-Q-P-O


## 5.1. Road Network

A road network with 19 nodes and 36 links shown in Figure6 is applied to validate the proposed method. The attributes of all links are presented in Table 1. There are two OD pairs, i.e., 1⟶17 and 8⟶19, the daily OD demands of which are 40,000 and 60,000, respectively. For simplicity, the predisaster link flows are obtained using a UE model.Figure 6
Layout of the testing road network.Table 1
Link attributes of the road network.
Linkti0 (h)Ci (Veh/h)Linkti0 (h)Ci (Veh/h)1–23.61,6009–102.22,0001–41.51,7009–142.81,6002–32.41,70010–111.82,2002–62.12,20010–152.51,7003–71.81,90011–121.52,4004–23.41,60011–151.92,0004–52.32,00012–131.72,2004–102.41,50012–161.82,2005–61.82,20012–172.32,4005–112.11,60013–171.91,6006–72.02,40014–151.71,7006–122.01,40014–181.72,2007–122.42,20015–161.72,0007–131.91,60015–192.01,6008–43.32,00016–171.32,0008–91.42,10016–191.81,7008–184.41,70017–192.92,0009–42.12,20018–192.62,200The link travel time is estimated by the Bureau of Public Roads (BPR) function:(28)tiqi=ti0⋅1+α⋅qiCiβ,∀i∈N,where ti0 is the free flow travel time on link i, Ci is the capacity of link i, and α and β are two parameters, where α=0.15 and β=4.Disasters usually cause two types of damage to the road infrastructure: (1) complete damage, which means that the capacity of each damaged road segment drops to zero and the damaged road segments are out of service, and (2) partial damage, which indicates that the capacity of each damaged road segment is reduced to a certain extent and the damaged road segments have some partial passage. For simplicity, we assume that a disaster, which occurs on dayd=1, completely damages 21 road segments (in the dashed-line circle in Figure 6). It is worth noting that our proposed method can be easily extended to the cases with partially damaged road segments. The damaged road segments are marked by red arrows in the dashed-line circle in Figure 6. The restoration duration and cost of each disrupted link are listed in Table 2, where the unit of ci is fund-unit. The total budget is 5,000 fund-unit. The other parameters are valued as in Table 3. The procedure is coded in MATLAB R2018b (version 11.4). All experiments are conducted on a Windows Server 2012 R2 server with an Intel Xeon E5-2640v4 CPU (2.4GHZ) and 64 GB DDR4 RAM.Table 2
Restoration duration and cost of each disrupted link.
Link IDei (day)ciqi,0(Veh)Link IDei (day)ciqi,0 (Veh)A6360193L7360206B7440548M6290364C4280304N8600353D6370201O5460458E6360255P6500302F7450280Q8510268G8640260R8480630H5170175S5450423I9590752T7420515J5240615U5350832K6340478Table 3
Parameter values used in this study.
ParametersValueMaximum allowed makespanMmax=60Link flow evolution ratev=1Travelers’ sensitivity to travel timeλ=0.5Travelers’ memory lengthm=3Total number of work crewsR=3Population sizepopSize=50Number of generationsGen=300Crossover probabilityPc=0.9Mutation probabilityPm=0.6Decision maker’s preferenceω=0.5


## 5.2. Results

We define the solution with the highest fitness value after convergence is the optimal solution. Figure7 illustrates the optimal RNRS generated by the proposed method. Figure 7(a) shows the start time and completion time of the restoration activity for each link, where the number on each bar is the duration of each restoration activity. Figure 7(b) presents the restoration activities assigned to each work crew, where the letter and number on each bar represent the link ID and restoration duration, respectively. This optimal RNRS covers 12 out of 21 disrupted links to be restored by three work crews, given that the restoration budget is 5,000 fund-unit. The makespan is 26 days. Figure 8 depicts the convergence process of the fitness values, which converges after 197 iterations. The best fitness value in the initial GA population is 0.231, and the fitness value reaches 0.612 after convergence.Figure 7
Optimal restoration strategy: (a) time sequence of maintenance; (b) job sequence of work crews.
(a)(b)Figure 8
Convergence process of fitness values.In practice, the empirical restoration strategy, i.e., flow-first strategy (FFS), is commonly used. FFS determines the time sequence of restoration activities by link flows from highest to lowest and covers as many links as possible until the budget is exhausted. According to the link flows listed in Table2, we generate a restoration scheme shown in Figure 9 following the FFS. In order to assess the efficiency of the optimal RNRS, we compare this optimal RNRS with the FFS. Table 4 lists the restoration results of the two strategies. Both strategies exhaust almost the same portion of the budget and cover 12 disrupted links. However, the optimal RNRS has a shorter makespan and produces much higher Rp and Rr. Obviously, the optimal RNRS outperforms the FFS, which indicates that the proposed method can recover the disrupted road network more quickly and generate fewer traffic delays.Figure 9
Flow-first restoration strategy: (a) time sequence of maintenance; (b) job sequence of work crews.
(a)(b)Table 4
Restoration results of the optimal RNRS and FFS.
Evaluation indexOptimal RNRSFFSRp0.4720.404Rr0.5670.533M2628C4,9904,940Figure10 presents the postdisaster TSTT evolution trajectories of the two restoration strategies. It is clear that TSTT has a significant fluctuation following the day-to-day traffic dynamics. Under the optimal RNRS, the postdisaster TSTT increases evidently and reaches the maximum equal to 3.12×106 on day d=2. As more links are recovered, TSTT gradually decreases. It is noting that although all the restoration activities are completed on day d=26, TSTT does not stop immediately and converges to a stationary (equilibrium) state on day d=31. Under the FFS, it takes 7 days for the network flows to reach the equilibrium state after the disaster and the equilibrium state continues for 14 days. This is because the FFS does not recover a new route till day d=20; thus, the network capacity does not increase until day d=20.Figure 10
Total system travel time evolution trajectories of the optimal RNRS and FFS.Since the road network flows cannot reach an equilibrium state overnight due to the network capacity variation, it is problematic to adopt UE models to simulate the traffic dynamics in this case. TSTT during the restoration makespan (i.e., 26 days) obtained by a day-to-day dynamics model and UE model for the two restoration strategies is compared in Figure11. From the comparison of results, it is known that TSTT is less under a UE model than under a day-to-day dynamics model.Figure 11
Total system travel time under a day-to-day dynamics model and UE model.More damage scenarios are generated to verify our proposed method and analyze the two objectives. We consider 3 damage scenarios, where 18–20 links in the dashed-line circle in Figure6 are randomly selected as the damaged road segments. For each scenario, there are C21ii=18,19,20 cases when i road segments are selected randomly to be damaged from the 21 road segments. The box plot for Rp and Rr of each scenario is presented in Figure 12. It can be found from Figure 12(a) that the maximum, minimum, median, upper quartile, and lower quartile of Rp all decrease as more road segments are damaged. As shown in Figure 12(b), the maximum and upper quartile of Rr decrease as more road segments are damaged. This phenomenon is in line with the fact that a network with more damaged road segments has lower resilience. It is also observed from Figure 12(b) that the lower quartile and the minimum of Rr keep constant in the three damage scenarios, which reveals that the three damage scenarios have the same worst-case optimal RNRS.Figure 12
Box plot for (a)Rp and (b).Rr.
(a)(b)


## 5.3. Sensitivity Analysis

In this subsection, we discuss the effects of key parameters including the number of work crews, travelers’ sensitivity to travel time, availability of budget, and decision makers’ preference on the restoration results. The sensitivity of every single parameter is analyzed by assuming other parameters are constant [47,48].


### 5.3.1. Number of Work Crews

Table5 presents three optimal RNRSs for three different R. It is clear that the variation in R only affects the restoration time sequence but does not change the damaged links to be restored. The optimal RNRS of R=1 has the minimum Rp and Rr, which indicates this restoration schedule is the worst. When R=1, M=76, which is more than 60; thus Rr=0. Obviously, a higher R can reduce M, but the relationship between R and M is nonlinear. Generally, the restoration results are gradually improved with the increase in R. However, the growth rates of Rp and Rr decrease as R increases, i.e., the marginal benefits of manpower decrease. Additional experiments indicate that the marginal benefits of Rp and Rr equal to 0 when R=12, which reveals that overmuch manpower cannot improve the restoration results but produces resource waste. Additionally, insufficient manpower will delay the restoration period. Thus, our proposed methods can be employed to evaluate manpower allocation plans in real-life road network recovery.Table 5
Effect ofR on the optimal RNRS.
R135Rp0.3640.4720.519Rr0.0000.5670.717M762617C4,9904,9904,990Optimal RNRSWork crew 1: E-M-T-I-R-Q-K-J-P-S-U-OWork crew 1: E-I-J-SWork crew 1: E-Q——Work crew 2: M-R-K-UWork crew 2: M-K-U——Work crew 3: T-Q-P-OWork crew 3: T-J-O———Work crew 4: I–S———Work crew 5: R–P


### 5.3.2. Travelers’ Sensitivity to Travel Time

Table6 shows three optimal RNRSs for three different λ. λ has a significant impact on the optimal RNRS including the restoration time sequence and the damaged links to be restored. As λ increases, the makespan is shortened, and both Rp and Rr increase. The larger the parameter value of λ, the more travelers will change their routes and the faster the link flows evolve to the new equilibrium state, thus causing less TSTT. Hence, in the actual RNRS, timely release of restoration information and effective traffic control strategies should be applied to help travelers to select the optimal route timely, which can improve the restoration schedule.Table 6
Effect ofλ on the optimal RNRS.
λ0.30.50.7Rp0.3570.4720.505Rr0.5330.5670.600M282624C4,9404,9904,480Optimal RNRSWork crew 1: A-K-E-J-UWork crew 1: E-I-J-SWork crew 1: A-I-E—Work crew 2: D-B-T-LWork crew 3: P–F-M-OWork crew 2: M-R-K-U—Work crew 3: T-Q-P-OWork crew 2: G-Q-OWork crew 3: P-T-M-U


### 5.3.3. Availability of Budget

Table7 lists the optimal RNRSs under three different scenarios of budget constraints. The optimal RNRSs of B=5,000 and B=7,000 differ greatly both in the restoration time sequence and the damaged links to be restored. Compared with B=5,000, the optimal RNRS under B=7,000 covers 5 more damaged links, which extends the makespan by 9 days and has higher Rp but lower Rr. It is noting that the restoration schedule does not change when B increases from 7,000 to 8,000. This is because that the manpower is insufficient. Thus, simply increasing the budget and keeping the workforce unchanged cannot improve the restoration schedule. Therefore, the monetary resources and the manpower should be matched.Table 7
Effect ofB on the optimal RNRS.
B5,0007,0008,000Rp0.4720.5170.517Rr0.5670.3830.383M263737C4,9906,8906,890Optimal RNRSWork crew 1: E-I-J-SWork crew 1: E-A-Q-J-H-DWork crew 1: E-A-Q-J-H-D—Work crew 2: M-R-K-UWork crew 2: M-G-S-I-LWork crew 2: M-G-S-I-L—Work crew 3: T-Q-P-OWork crew 3: T-P-R-K-O-UWork crew 3: T-P-R-K-O-U


### 5.3.4. Decision Maker’s Preference

Table8 indicates two optimal RNRSs for two different ω. Obviously, ω has a significant effect on the restoration schedule including the restoration time sequence and the damaged links to be restored. Compared with ω=0.5, the optimal RNRS with ω=0.3 is involved with 2 less damaged links, thus resulting in a lower Rp, M, and C but higher Rr, which represents more traffic delays and a shorter makespan. Hence, decision makers should make an optimal tradeoff between Rp and Rr.Table 8
Effect ofω on the optimal RNRS.
ω0.30.5Rp0.4130.472Rr0.6170.567M2326C4,3904,990Optimal RNRSWork crew 1: E-A-B-CWork crew 1: E-I-J-S—Work crew 2: M-G-IWork crew 2: M-R-K-U—Work crew 3: T-P-QWork crew 3: T-Q-P-O


## 5.3.1. Number of Work Crews

Table5 presents three optimal RNRSs for three different R. It is clear that the variation in R only affects the restoration time sequence but does not change the damaged links to be restored. The optimal RNRS of R=1 has the minimum Rp and Rr, which indicates this restoration schedule is the worst. When R=1, M=76, which is more than 60; thus Rr=0. Obviously, a higher R can reduce M, but the relationship between R and M is nonlinear. Generally, the restoration results are gradually improved with the increase in R. However, the growth rates of Rp and Rr decrease as R increases, i.e., the marginal benefits of manpower decrease. Additional experiments indicate that the marginal benefits of Rp and Rr equal to 0 when R=12, which reveals that overmuch manpower cannot improve the restoration results but produces resource waste. Additionally, insufficient manpower will delay the restoration period. Thus, our proposed methods can be employed to evaluate manpower allocation plans in real-life road network recovery.Table 5
Effect ofR on the optimal RNRS.
R135Rp0.3640.4720.519Rr0.0000.5670.717M762617C4,9904,9904,990Optimal RNRSWork crew 1: E-M-T-I-R-Q-K-J-P-S-U-OWork crew 1: E-I-J-SWork crew 1: E-Q——Work crew 2: M-R-K-UWork crew 2: M-K-U——Work crew 3: T-Q-P-OWork crew 3: T-J-O———Work crew 4: I–S———Work crew 5: R–P


## 5.3.2. Travelers’ Sensitivity to Travel Time

Table6 shows three optimal RNRSs for three different λ. λ has a significant impact on the optimal RNRS including the restoration time sequence and the damaged links to be restored. As λ increases, the makespan is shortened, and both Rp and Rr increase. The larger the parameter value of λ, the more travelers will change their routes and the faster the link flows evolve to the new equilibrium state, thus causing less TSTT. Hence, in the actual RNRS, timely release of restoration information and effective traffic control strategies should be applied to help travelers to select the optimal route timely, which can improve the restoration schedule.Table 6
Effect ofλ on the optimal RNRS.
λ0.30.50.7Rp0.3570.4720.505Rr0.5330.5670.600M282624C4,9404,9904,480Optimal RNRSWork crew 1: A-K-E-J-UWork crew 1: E-I-J-SWork crew 1: A-I-E—Work crew 2: D-B-T-LWork crew 3: P–F-M-OWork crew 2: M-R-K-U—Work crew 3: T-Q-P-OWork crew 2: G-Q-OWork crew 3: P-T-M-U


## 5.3.3. Availability of Budget

Table7 lists the optimal RNRSs under three different scenarios of budget constraints. The optimal RNRSs of B=5,000 and B=7,000 differ greatly both in the restoration time sequence and the damaged links to be restored. Compared with B=5,000, the optimal RNRS under B=7,000 covers 5 more damaged links, which extends the makespan by 9 days and has higher Rp but lower Rr. It is noting that the restoration schedule does not change when B increases from 7,000 to 8,000. This is because that the manpower is insufficient. Thus, simply increasing the budget and keeping the workforce unchanged cannot improve the restoration schedule. Therefore, the monetary resources and the manpower should be matched.Table 7
Effect ofB on the optimal RNRS.
B5,0007,0008,000Rp0.4720.5170.517Rr0.5670.3830.383M263737C4,9906,8906,890Optimal RNRSWork crew 1: E-I-J-SWork crew 1: E-A-Q-J-H-DWork crew 1: E-A-Q-J-H-D—Work crew 2: M-R-K-UWork crew 2: M-G-S-I-LWork crew 2: M-G-S-I-L—Work crew 3: T-Q-P-OWork crew 3: T-P-R-K-O-UWork crew 3: T-P-R-K-O-U


## 5.3.4. Decision Maker’s Preference

Table8 indicates two optimal RNRSs for two different ω. Obviously, ω has a significant effect on the restoration schedule including the restoration time sequence and the damaged links to be restored. Compared with ω=0.5, the optimal RNRS with ω=0.3 is involved with 2 less damaged links, thus resulting in a lower Rp, M, and C but higher Rr, which represents more traffic delays and a shorter makespan. Hence, decision makers should make an optimal tradeoff between Rp and Rr.Table 8
Effect ofω on the optimal RNRS.
ω0.30.5Rp0.4130.472Rr0.6170.567M2326C4,3904,990Optimal RNRSWork crew 1: E-A-B-CWork crew 1: E-I-J-S—Work crew 2: M-G-IWork crew 2: M-R-K-U—Work crew 3: T-P-QWork crew 3: T-Q-P-O


## 6. Conclusions

This paper focuses on the resilience-based optimization of postdisaster road network restoration strategy. A TSTT-based function is used as the network performance indicator. Since the equilibrium-based methods cannot capture partial user equilibrium, a link-based day-to-day traffic model is employed to compute TSTT. We develop two resilience metrics to evaluate the effectiveness of the restoration strategy, i.e., the resilience of performance loss and the resilience of recovery rapidity. The former is calculated based on the network performance, and the latter is developed according to the restoration makespan. The restoration optimization problem is formulated as a resilience-based bi-objective mixed integer programming model, which aims to maximize the network resilience considering resource constraints. Then, a genetic algorithm is applied as the model solution.The proposed method is validated through a case study. The results show that our method can provide an effective reference for transportation agencies to schedule postdisaster restoration activities. Compared with FFS, the optimal restoration strategy can reduce traffic congestion and shorten makespan. The comparison between the computational results using the day-to-day dynamics model and UE model explains why a link-based day-to-day dynamics model is preferred in this study. The sensitivity analyses of several key parameters reveal that the increase in the number of work crew or budget can improve the restoration schedule, but the marginal benefits of these two kinds of resources decrease. When either of the two resources exceeds a certain level, the restoration schedule will not be further improved. Travelers’ sensitivity to travel time or decision makers’ preference has a significant effect on the restoration schedule including the restoration time sequence and the damaged links to be restored. As travelers’ sensitivity to travel time increases, the resilience of performance loss and the resilience of recovery rapidity will increase.Future work should (1) consider some uncertainties, e.g., duration of restoration activities, traffic demands, and the restoration cost during the decision process; (2) develop a path-based day-to-day traffic model to simulate the PUE during the restoration process; (3) investigate the joint optimization of road network restoration and traffic control strategy; and (4) develop more intelligent algorithms and compare the efficiency of these algorithms to find a more suitable model solution.



---

*Source: 8871876-2021-02-12.xml*