# Resilience-Based Restoration Sequence Optimization for Metro Networks: A Case Study in China

Authors: Jiefei Zhang; Gang Ren; Jianhua Song
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

Metro station restoration sequence optimization is crucial during post-disaster recovery. Taking both budget limitations and repair time uncertainty into account, this paper proposes a resilience-based optimization model for choosing an optimal restoration sequence scheme, maximizing the global average efficiency, under the condition that the network accessibility meets given resilience requirements. Evolutionary algorithm NSGA-II is applied to solve the model. A Case study in Nanjing and Zhengzhou gives insights into restoration sequence strategies for decision-makers. Results show that a ring network is more robust than a radial network under the same scale attack. Under limited budget, the optimal restoration sequence is closely related to the damaged stations’ location and repair time. Specifically, if damaged stations’ distribution is relatively centralized and transfer stations need more repair time, giving repair priority to transfer stations is not always the best strategy. If damaged stations’ distribution is relatively scattered and all stations’ repair time is the same, the station with a bigger node degree should be repaired earlier. However, this conclusion may be invalid if transfer stations repair time is far longer than others. Sensitivity analysis show that the total budget is more sensitive than one day’s budget in the entire restoration phase. However, in the emergency phase, increasing one day’s budget is more significant for shortening recovery time. The proposed model can contribute to effective and flexible decision-making for metro network restorations.


---

## Body

## 1. Introduction

As one of the fastest and high-capacity means of transportation, metros have become an effective way of solving congestion problems. However, metro networks can be vulnerable to certain natural disasters, terrorist attacks or equipment failures, and any damages can cause severe socio-economic losses [1–3]. In order to mitigate losses caused by these types of disruptions, damages need to be repaired immediately. Working with a limited budget, decision-makers need to determine a set of criteria for a restoration sequence to ensure the system’s rapid and effective recovery.Some research has been done in the pursuit of the optimal restoration sequence scheme for transportation networks, which can be conceptualised as a network design problem (NDP). Throughout the last decade, researchers have combined resilience evaluation and the NDP to explore the methodology of the resilience-based optimal restoration plan. Infrastructure resilience is an ability to absorb, adapt to, and rapidly recover from potentially disruptive or destructive events [4, 5]. The advantage of resilience analyses is to reduce the disruption’s risks and improve the system’s recovery ability. The resilience index has been widely used to quantify the system’s recovery ability [6–8].Resilience-based restoration optimization was widely used in road network or road-bridge network, but few studies applied to the metro network. Previous research considered various network metrics, including (1) connectivity [2, 9, 10]; (2) travel delay cost [11]; and (3) network capacity [12, 13]. However, as these studies focus on a single metric, ignoring the trade-offs or connections between different metrics, they cannot meet the needs for multi-objective decision processes, especially for long-term restoration. Focusing on network topology characteristics, this paper proposes an optimal metro restoration sequence model to guide multi-objective decision-making. In existing research, node degree, network accessibility, and global average efficiency are the main network topology characteristics for metro networks [14–16]. Those metrics have all been considered in our model.Some researchers considered multi-objective optimization, such as Matisziw’s [17], Liu, Zhai, and Dong [18], Somy, Shafaei, and Ramezanian [19]. They all adopted a weighting method to deal with a multi-objective problem. However, different weighting factors will lead to contradictory results. The proposed model focuses on metro topology characteristics, and also can transfer a multiobjective problem to a single-objective combinatorial problem with additional constraints that respect the other goals. This method can reduce the subjectivity caused by improper weighting factor setting. Furthermore, the proposed model also can present a flexible framework. The objectives and constraints can be set flexibly by decision-makers to meet multi-stage objectives.The majority of existing restoration optimization models based on resilience only considered the resilience index of the network performance, but ignored the recovery trajectories of restoration schemes. For example, in Figure1, the resilience index of curve 1 and curve 2 are equal, but with significant differences in trajectories. Thus, we add an extra objective that makes the network performance recover to the pre-given value at a specific time. This method can avoid the above question validly.Figure 1
Resilience loss measurement from the resilience triangle.Genetic algorithm [10, 18, 20], tabu search algorithm [13], and greedy algorithm [21] were widely applied to deal with discrete NDP problem. Compared with the greedy algorithm and tabu search algorithm, the Genetic Algorithm has better global search ability and convergence control. NSGA-II introduces the elitist strategy to expand the sampling space, prevent the loss of the best individual, and improve the operation speed and robustness of the algorithm [22]. Thus, NSGA-II is adopted to deal with optimization questions.Most metro stations and lines are underground. The restoration process is relatively complex and may continue for a long time. Multi-stage decision-making is necessary for large-scale metro network restoration. Focusing on network topology characteristics, this paper provides a valuable and flexible tool for optimizing the metro restoration sequences, while taking limited budget restraints and repair time uncertainty into account, giving a guideline for multi-objective decision-making. Unlike most bi-objective research, we transfer a multi-objective problem to a single-objective combinatorial problem with additional constraints that respect the other goals. The research can enhance the effective allocation of disaster relief resources and improve post-disaster recovery, which improves the metro’s resilience following a disruption.The remainder of the paper is organised as follows. Firstly, the framework and methodology of the resilience-based, multiobjective optimal restoration sequence model are introduced. Then, three empirical case studies using a real-world metro network are presented. Finally, the conclusion and recommendations are summarised.


## 2. Methodology

### 2.1. Problem Statement

As metro networks can be particularly vulnerable during extreme events, potentially causing damage to stations, actions should be adopted to ensure the network is able to recover as quickly and effectively as possible. In reality, postdisaster recovery is generally a long-term project. As decision-makers may have different objectives at different stages. Based on the need for practice and the key points of this research, some assumptions are made in order to simplify the complexity of the problem.(1)
As alternative paths often exist in a damaged network, passengers can be evacuated from affected zones to safer areas without the help of other means of transportation, proving that network accessibility is more important than global average efficiency in the short term. Networks with different restoration schemes may have the same network accessibility. However, the global average efficiency may vary. Hence, the proposed model aims to seek an optimal restoration sequence scheme to maximize the global average efficiency, under the condition that network accessibility meets predetermined resilience requirements (such as the recovery time, the resilience index, and recovery rate).(2)
Consideration of uncertainties associated with restoration projects is critical for effective decision-making. Uncertainties can include the network damage status, the residual network capacity [12], and the effects of aftershocks [23], among others. This paper assumes that postdisaster network damaged conditions are known, and ignores the effects of any potential aftershocks. Besides, the restoration duration for a damaged metro station obeys a certain probability distribution.(3)
Fund allocation is crucial for network recovery and any restoration scheme will be particularly sensitive to budget changes [24]. This paper assumes that the total budget is limited, and the utilisation of funds can be different throughout different stages, meaning that some stations can be repaired at the same time.


### 2.2. Network Topology Performance Metrics

Based on graph theory, a physical metro network can be abstracted as an undirected graphG (N, L) composed of N nodes and L links. In this graph, stations are abstracted as nodes, and links between two adjacent stations are abstracted as links. The most common network modelling methods include the Space L, Space P, and the Space R method [15]. Because the Space L method can directly reflect a metro network’s physical structure, using it to calculate network topology metrics can better reflect passengers’ travel behaviour. Thus, the Space L method is adopted to build a network topology model.


#### 2.2.1. Network Accessibility

A graphG can be completely represented by an adjacency matrix AN×N with element aij = 1 if nodes i and j connect directly, otherwise, aij = 0. By default, when i = j, the aij = 0.Accessibility matrixB (N × N) can describe the network accessibility. If node i to node j have a path (i ≠ j), bij = 1, otherwise, bij = 0. By default, when i = j, the bij = 1. In the operational state, the value of bij (i ≠ j) is equal to 1. When some nodes are damaged and there are no alternative paths from node i to node j, the bij = 0.To depict the node importance in the model, the node degree is considered. The degree of nodei is defined as the number of the nodes that directly connect with node i [25]. The degree matrix D is a 1 × N matrix. Because we constructed an undirected graph, so the D does not consider the incoming and outgoing links. The degree of node i equals to the sum of the value in matrix A’s ith row. Matrix C = D × B is used to consider the node importance and accessibility comprehensively. This method also can help to decrease the matrix dimension and built a mathematical model. Matrix C is a 1 × N matrix, the ith element of the matrix represents the product of the degree of node i and the total number of node j which connect with node i by at least one path. To generate a network accessibility resilience index, the dimension of the matrix C should be reduced further. Z (t) = Sum (Ci) (i ∈ N) is adopted to depict the network accessibility at time t.(1)Zt=∑i=1NCit=∑i=1ND×Bt,where Z (t) is the network accessibility at time t. Ci (t) is the value of ith element of matrix C at time t. D is the degree matrix N×N. Bt is the accessibility matrix 1×N at time t. N is the total number of nodes.


#### 2.2.2. Global Average Efficiency

The global average efficiencyE quantifies the network efficiency in the global scope, it can be calculated by equation (2) [26]. The shortest path between two nodes can be found by the Dijkstra algorithm [27].(2)E=1NN−1∑i≠jN1dij,where E is the global average efficiency. dij is the shortest path length between node i and node j.


### 2.3. Resilience Index

As shown in Figure1, F (t0) represents the system’s performance value in the original stable state. F (t) represents the system’s performance curve, whose value continues to change with time. te represents the time of disruption occurring. tf represents the time for the system to recover to its original state. The resilience of the system at time tr can be quantified as resilience index RF, shown as equation (3). It is equal to the ratio of the area covered by the performance curve F (t) and the area covered by the curve F (t0) during the period of te to tr. In some research, the shadow part is named the “resilience triangle” [6].(3)RFtr=∫tetrFtdtFt0tr−te.


### 2.4. Resilience-Based Multiobjective Optimization for Restoration Sequence

Taking budget limitations and repair time uncertainty into account, the optimal restoration sequence scheme aims to maximize global average efficiency, when the network accessibility satisfies pregiven resilience requirements (including the resilience index and recovery rate). A multiobjective problem can be transferred to a single-objective combinatorial problem with additional constraints that respect the other goals of the problem. Equations (14) and (15) represent the other goals of the problem. The optimal sequence scheme should make the network accessibility’s resilience index and recovery rate reach the threshold at least and maximize as much as possible under the budget limitation. Then, from the partial solutions, the solution with the maximum global average efficiency is selected as the optimal scheme.(4)Nd=s1,s2,s3,…,sm,(5)ti∼Ntl¯,δi.Objective:(6)MaxEtr=1NN−1∑i=1,i≠jN1dij,Decision variables:(7)βikt∈0,1,∀i∈Nd,(8)tis,(9)tie=tis+ti,(10)Nat=sa,sb,sc,…,sp.Constraints:(11)θTZ≤U,(12)K≤INTuθ,(13)∑i=1,i∈NatrNatrti≤TZ,(14)RZ=∫t0trZtdtZt0tr−t0≥f1,(15)QZ=ZtrZt0≥f2,(16)tis≥0,(17)maxtie≤tr.Equation (4) is the set of damaged stations after disaster. Equation (5) reveals the repair time of node i obeys normal distribution whose mean is ti¯ and variance is δi. It reflects the uncertainty of repair time. Equation (6) is the objective of the model, which maximizes the global average efficiency. Equations (7)–(10) is the decision variables. Equation (7) represents whether the station i is repaired at time t by team k. Equation (8) is the repair start time of node i. Equation (9) is the repair finished time of node i. It equals to the node i’s repair start time plus the i’s repair time. Equation (10) is the set of repaired stations at time t, and it can get by equation (7). Equation (11) demonstrates the total budget limitation. Equation (12) demonstrates the limitation of the number of maintenance teams in one day, which can reflect the abundance of resources. Equation (13) indicates the limitation of total repair time for repaired nodes. Equation (14) is the resilience requirement of the network accessibility, which requires the resilience index to reach f1 at least at time tr. Equation (15) is the other requirement of the resilience, which requires the network accessibility to get back into Z (t0) ∗ f2 at least at time tr. The range of f1 and f2 is 0,1. The former reflects the recovery degree of Z with continuous time. The latter reflects the recovery degree of Z at discrete time. In practice, decision-makers can preset the different f1 and f2 to reflect the different resilience requirements. Equation (16) indicates the repair start time of node i should be bigger than 0. Equation (17) indicates the maximized repair finished time of node i should not be bigger than the pre-given deadline. The notations are shown in Table 1.Table 1
Notations.
NdThe set of damaged nodes at timet0t0 (day)The time of the disruption occurringtr (day)The pregiven deadlineEGlobal average efficiencyNThe total nodes in the networkdijThe length of the shortest path from nodei to node jβiktBinary variable – if nodei is repaired by team k at time t, then βikt=1; otherwise, βikt=0NatThe set of repaired nodes at timettisRepair start time of nodeitieRepair finished time of nodeiZNetwork accessibilityBtThe accessibility matrix (N × N) at time tRzThe resilience index of network accessibility at timetrQzThe ratio of network accessibility at timetr and t0f1, f2Constants that represent the resilient requirementθ ($)A constant that represents the cost of one day’s work for a maintenance teamU ($)The total budgetTz (day)The total restoration time of one team under the total budget limitationu ($)The maximized budget which can be paid in one dayKThe number of the maintenance teams in one dayti (day)The repair time of damaged nodeiDThe degree matrix (1 ×N) of the networkti¯ (day)The average repair time of nodeiδi (day)The variance of repair time of nodei


### 2.5. Solution Process and Algorithm

The solution process of the proposed model for restoration sequence is shown as Figure2. The solution process is divided into two-stage. The first stage aims to make the network accessibility’s resilience index RZ and recovery rate QZ reach to the threshold and maximize as much as possible. The NSGA-II algorithm is adopted to deal with this problem. Under the budget limitation, the Pareto front solutions can be available. The second stage aims to find out the optimal restoration sequence scheme to maximize the network efficiency E from the Pareto front solutions.Figure 2
The solution process of resilience-based multi-objective optimization with NSGA-II.The solution process is as follows:(1)
Parameters input. All parameters can be found in scenario descriptions. Because the damaged station’s repair time obeys normal distribution, the repair time of each nodeti is randomly allocated according to the distribution function.(2)
According to equations (11) and (12) to calculate the value of TZ, Kmax. k = 1, 2,…, Kmax(3)
Stage One: using NAGA-II to deal with multi-objective optimization.Objective 1: maximize the network accessibility’s resilience indexRZObjective 2: maximize the network accessibility’s recovery rateQZThe NSGA-II has four important parameters: the number of individuals in the population (Population), the maximum number of generations (Maximum generations), cross-over rate, mutation rate, and the number of individuals in each tournament. The cross-over rate is used to decide the probability of two individuals need to crossover. The mutation rate is used to decide the probability that any individual needs mutation. The termination criterion is the number of iterations is equal to the maximum generations.(1)
Initialization—Define the basic parameters to control the NSGA-II: number of individuals in the population (np), the maximum number of generations (ngmax), cross-over rate (c), mutation rate (mr), number of individuals in each tournament (ntour), and generation counter (Gen).(2)
Generation of the initial population—The illustration of chromosome coding is shown in Figure3. x1 (i) represents the order priority value of generation 1, 0 < x (i) < 1. The smaller the value, the higher the priority. y1 (i) represents the resource allocation of generation 1, k = 1, 2, …, Kmax. Generate 3np individuals and among them select np with distinct characteristics. With one individual, calculate the tis, tie,RZ, QZ, and select the individual that meets the constraints (13)–(17). Otherwise, an individual is generated repeatedly until it meets all the constraints. Repair scheduling by chromosome decoding is shown in Figure 4.Because theRZ is integral form, it should be replaced by the sum of discrete forms. The repair finished time of node i can be got by decoding. Sort the repair finished time of node i in ascending order, the time axis can be divided into p segments. The calculation of RZ can be achieved by equation.(18)RZ=∫t0trZtdtZt0tr−t0=∑0p−1Ztp+1+Ztptp+1−tp2Zt0tr−t0.(3)
Classification according to the dominance criterion (nondominated sorting)—classify the individuals in fronts based on the value ofRz, Qz. The nondominated sorting criterion states that for two solutions, Xa and Xb, Xa dominates Xb if Xa is better than or equal to Xb in all objectives and Xa is better than Xb in at least one of the objectives. If there are no other decision variables that can dominate a decision variable, the decision variable is called a nondominated solution. All nondominated solutions in chromosome set X is defined as the first nondominated layer.(4)
Iterative process—while Gen <ngmax, repeat the following loop:(a)
Selection—the individuals selected for cross-over and mutation are chosen by tournaments which then select each individual in the following way: among the individuals of the population,ntour are randomly chosen and the best classified is selected according to the dominance criteria.(b)
Crossover—using operators for the crossover, resulting inc ∗ np descendants.(c)
Mutation—using operators for the mutation, resulting inm ∗ np individuals.(d)
Generation of the temporary population—with thenp individuals obtained through crossover and mutation, a new population is generated and added to the previous temporary population of 2np individuals.(e)
Classification of the temporary population—the 2np individuals of the temporary population are classified again according to the criteria of dominance and diversity.For the solutionXq∈X in the ist dominating layer, the crowding distance CXq can be calculated as equation.(19)CXq=QZXq+1−QZXq−1MaxQZX−MinQZX+RZXq+1−RZXq−1MaxRZX−MinRZX,whereMaxQzX and MinQzX are the maximum and minimum values of QzX in the ist dominant layer, respectively. MaxRzX and MinRzX are the maximum and minimum values of RzX in the ist dominant layer, respectively. QzXq+1 and QzXq−1 are the previous and next values of QzXq after the ascending order of QzX in the ist dominant layer. RzXq+1 and RzXq−1 are the previous and next values of RzXq in the ist dominant layer. The illustration can be shown in Figure 5. The farther each individual is located form the remaining solutions, the better its classification.(f)
Selection of a new population—A new population is obtained from the temporary population.(g)
Updating of the generation counter—Gen = Gen + 1.(h)
Output the Pareto front solutions.(4)
Stage two: output the optimal sequence scheme that maximizes the network efficiencyE (tr).Figure 3
Chromosome coding (Kmax = 3).Figure 4
Repair scheduling by chromosome decoding (Kmax = 3).Figure 5
Solution space of a problem with two objectives to be maximized.Calculate the network efficiencyE (tr) of each Pareto front solution and find out the one that makes the E (tr) maximized.The output of model isX=i,k,tis,tie,…,. i represents the node ID. k represents the node is repaired by team k. tis is the repair start time of node i. tie is the repair finished time of node i.


## 2.1. Problem Statement

As metro networks can be particularly vulnerable during extreme events, potentially causing damage to stations, actions should be adopted to ensure the network is able to recover as quickly and effectively as possible. In reality, postdisaster recovery is generally a long-term project. As decision-makers may have different objectives at different stages. Based on the need for practice and the key points of this research, some assumptions are made in order to simplify the complexity of the problem.(1)
As alternative paths often exist in a damaged network, passengers can be evacuated from affected zones to safer areas without the help of other means of transportation, proving that network accessibility is more important than global average efficiency in the short term. Networks with different restoration schemes may have the same network accessibility. However, the global average efficiency may vary. Hence, the proposed model aims to seek an optimal restoration sequence scheme to maximize the global average efficiency, under the condition that network accessibility meets predetermined resilience requirements (such as the recovery time, the resilience index, and recovery rate).(2)
Consideration of uncertainties associated with restoration projects is critical for effective decision-making. Uncertainties can include the network damage status, the residual network capacity [12], and the effects of aftershocks [23], among others. This paper assumes that postdisaster network damaged conditions are known, and ignores the effects of any potential aftershocks. Besides, the restoration duration for a damaged metro station obeys a certain probability distribution.(3)
Fund allocation is crucial for network recovery and any restoration scheme will be particularly sensitive to budget changes [24]. This paper assumes that the total budget is limited, and the utilisation of funds can be different throughout different stages, meaning that some stations can be repaired at the same time.


## 2.2. Network Topology Performance Metrics

Based on graph theory, a physical metro network can be abstracted as an undirected graphG (N, L) composed of N nodes and L links. In this graph, stations are abstracted as nodes, and links between two adjacent stations are abstracted as links. The most common network modelling methods include the Space L, Space P, and the Space R method [15]. Because the Space L method can directly reflect a metro network’s physical structure, using it to calculate network topology metrics can better reflect passengers’ travel behaviour. Thus, the Space L method is adopted to build a network topology model.


### 2.2.1. Network Accessibility

A graphG can be completely represented by an adjacency matrix AN×N with element aij = 1 if nodes i and j connect directly, otherwise, aij = 0. By default, when i = j, the aij = 0.Accessibility matrixB (N × N) can describe the network accessibility. If node i to node j have a path (i ≠ j), bij = 1, otherwise, bij = 0. By default, when i = j, the bij = 1. In the operational state, the value of bij (i ≠ j) is equal to 1. When some nodes are damaged and there are no alternative paths from node i to node j, the bij = 0.To depict the node importance in the model, the node degree is considered. The degree of nodei is defined as the number of the nodes that directly connect with node i [25]. The degree matrix D is a 1 × N matrix. Because we constructed an undirected graph, so the D does not consider the incoming and outgoing links. The degree of node i equals to the sum of the value in matrix A’s ith row. Matrix C = D × B is used to consider the node importance and accessibility comprehensively. This method also can help to decrease the matrix dimension and built a mathematical model. Matrix C is a 1 × N matrix, the ith element of the matrix represents the product of the degree of node i and the total number of node j which connect with node i by at least one path. To generate a network accessibility resilience index, the dimension of the matrix C should be reduced further. Z (t) = Sum (Ci) (i ∈ N) is adopted to depict the network accessibility at time t.(1)Zt=∑i=1NCit=∑i=1ND×Bt,where Z (t) is the network accessibility at time t. Ci (t) is the value of ith element of matrix C at time t. D is the degree matrix N×N. Bt is the accessibility matrix 1×N at time t. N is the total number of nodes.


### 2.2.2. Global Average Efficiency

The global average efficiencyE quantifies the network efficiency in the global scope, it can be calculated by equation (2) [26]. The shortest path between two nodes can be found by the Dijkstra algorithm [27].(2)E=1NN−1∑i≠jN1dij,where E is the global average efficiency. dij is the shortest path length between node i and node j.


## 2.2.1. Network Accessibility

A graphG can be completely represented by an adjacency matrix AN×N with element aij = 1 if nodes i and j connect directly, otherwise, aij = 0. By default, when i = j, the aij = 0.Accessibility matrixB (N × N) can describe the network accessibility. If node i to node j have a path (i ≠ j), bij = 1, otherwise, bij = 0. By default, when i = j, the bij = 1. In the operational state, the value of bij (i ≠ j) is equal to 1. When some nodes are damaged and there are no alternative paths from node i to node j, the bij = 0.To depict the node importance in the model, the node degree is considered. The degree of nodei is defined as the number of the nodes that directly connect with node i [25]. The degree matrix D is a 1 × N matrix. Because we constructed an undirected graph, so the D does not consider the incoming and outgoing links. The degree of node i equals to the sum of the value in matrix A’s ith row. Matrix C = D × B is used to consider the node importance and accessibility comprehensively. This method also can help to decrease the matrix dimension and built a mathematical model. Matrix C is a 1 × N matrix, the ith element of the matrix represents the product of the degree of node i and the total number of node j which connect with node i by at least one path. To generate a network accessibility resilience index, the dimension of the matrix C should be reduced further. Z (t) = Sum (Ci) (i ∈ N) is adopted to depict the network accessibility at time t.(1)Zt=∑i=1NCit=∑i=1ND×Bt,where Z (t) is the network accessibility at time t. Ci (t) is the value of ith element of matrix C at time t. D is the degree matrix N×N. Bt is the accessibility matrix 1×N at time t. N is the total number of nodes.


## 2.2.2. Global Average Efficiency

The global average efficiencyE quantifies the network efficiency in the global scope, it can be calculated by equation (2) [26]. The shortest path between two nodes can be found by the Dijkstra algorithm [27].(2)E=1NN−1∑i≠jN1dij,where E is the global average efficiency. dij is the shortest path length between node i and node j.


## 2.3. Resilience Index

As shown in Figure1, F (t0) represents the system’s performance value in the original stable state. F (t) represents the system’s performance curve, whose value continues to change with time. te represents the time of disruption occurring. tf represents the time for the system to recover to its original state. The resilience of the system at time tr can be quantified as resilience index RF, shown as equation (3). It is equal to the ratio of the area covered by the performance curve F (t) and the area covered by the curve F (t0) during the period of te to tr. In some research, the shadow part is named the “resilience triangle” [6].(3)RFtr=∫tetrFtdtFt0tr−te.


## 2.4. Resilience-Based Multiobjective Optimization for Restoration Sequence

Taking budget limitations and repair time uncertainty into account, the optimal restoration sequence scheme aims to maximize global average efficiency, when the network accessibility satisfies pregiven resilience requirements (including the resilience index and recovery rate). A multiobjective problem can be transferred to a single-objective combinatorial problem with additional constraints that respect the other goals of the problem. Equations (14) and (15) represent the other goals of the problem. The optimal sequence scheme should make the network accessibility’s resilience index and recovery rate reach the threshold at least and maximize as much as possible under the budget limitation. Then, from the partial solutions, the solution with the maximum global average efficiency is selected as the optimal scheme.(4)Nd=s1,s2,s3,…,sm,(5)ti∼Ntl¯,δi.Objective:(6)MaxEtr=1NN−1∑i=1,i≠jN1dij,Decision variables:(7)βikt∈0,1,∀i∈Nd,(8)tis,(9)tie=tis+ti,(10)Nat=sa,sb,sc,…,sp.Constraints:(11)θTZ≤U,(12)K≤INTuθ,(13)∑i=1,i∈NatrNatrti≤TZ,(14)RZ=∫t0trZtdtZt0tr−t0≥f1,(15)QZ=ZtrZt0≥f2,(16)tis≥0,(17)maxtie≤tr.Equation (4) is the set of damaged stations after disaster. Equation (5) reveals the repair time of node i obeys normal distribution whose mean is ti¯ and variance is δi. It reflects the uncertainty of repair time. Equation (6) is the objective of the model, which maximizes the global average efficiency. Equations (7)–(10) is the decision variables. Equation (7) represents whether the station i is repaired at time t by team k. Equation (8) is the repair start time of node i. Equation (9) is the repair finished time of node i. It equals to the node i’s repair start time plus the i’s repair time. Equation (10) is the set of repaired stations at time t, and it can get by equation (7). Equation (11) demonstrates the total budget limitation. Equation (12) demonstrates the limitation of the number of maintenance teams in one day, which can reflect the abundance of resources. Equation (13) indicates the limitation of total repair time for repaired nodes. Equation (14) is the resilience requirement of the network accessibility, which requires the resilience index to reach f1 at least at time tr. Equation (15) is the other requirement of the resilience, which requires the network accessibility to get back into Z (t0) ∗ f2 at least at time tr. The range of f1 and f2 is 0,1. The former reflects the recovery degree of Z with continuous time. The latter reflects the recovery degree of Z at discrete time. In practice, decision-makers can preset the different f1 and f2 to reflect the different resilience requirements. Equation (16) indicates the repair start time of node i should be bigger than 0. Equation (17) indicates the maximized repair finished time of node i should not be bigger than the pre-given deadline. The notations are shown in Table 1.Table 1
Notations.
NdThe set of damaged nodes at timet0t0 (day)The time of the disruption occurringtr (day)The pregiven deadlineEGlobal average efficiencyNThe total nodes in the networkdijThe length of the shortest path from nodei to node jβiktBinary variable – if nodei is repaired by team k at time t, then βikt=1; otherwise, βikt=0NatThe set of repaired nodes at timettisRepair start time of nodeitieRepair finished time of nodeiZNetwork accessibilityBtThe accessibility matrix (N × N) at time tRzThe resilience index of network accessibility at timetrQzThe ratio of network accessibility at timetr and t0f1, f2Constants that represent the resilient requirementθ ($)A constant that represents the cost of one day’s work for a maintenance teamU ($)The total budgetTz (day)The total restoration time of one team under the total budget limitationu ($)The maximized budget which can be paid in one dayKThe number of the maintenance teams in one dayti (day)The repair time of damaged nodeiDThe degree matrix (1 ×N) of the networkti¯ (day)The average repair time of nodeiδi (day)The variance of repair time of nodei


## 2.5. Solution Process and Algorithm

The solution process of the proposed model for restoration sequence is shown as Figure2. The solution process is divided into two-stage. The first stage aims to make the network accessibility’s resilience index RZ and recovery rate QZ reach to the threshold and maximize as much as possible. The NSGA-II algorithm is adopted to deal with this problem. Under the budget limitation, the Pareto front solutions can be available. The second stage aims to find out the optimal restoration sequence scheme to maximize the network efficiency E from the Pareto front solutions.Figure 2
The solution process of resilience-based multi-objective optimization with NSGA-II.The solution process is as follows:(1)
Parameters input. All parameters can be found in scenario descriptions. Because the damaged station’s repair time obeys normal distribution, the repair time of each nodeti is randomly allocated according to the distribution function.(2)
According to equations (11) and (12) to calculate the value of TZ, Kmax. k = 1, 2,…, Kmax(3)
Stage One: using NAGA-II to deal with multi-objective optimization.Objective 1: maximize the network accessibility’s resilience indexRZObjective 2: maximize the network accessibility’s recovery rateQZThe NSGA-II has four important parameters: the number of individuals in the population (Population), the maximum number of generations (Maximum generations), cross-over rate, mutation rate, and the number of individuals in each tournament. The cross-over rate is used to decide the probability of two individuals need to crossover. The mutation rate is used to decide the probability that any individual needs mutation. The termination criterion is the number of iterations is equal to the maximum generations.(1)
Initialization—Define the basic parameters to control the NSGA-II: number of individuals in the population (np), the maximum number of generations (ngmax), cross-over rate (c), mutation rate (mr), number of individuals in each tournament (ntour), and generation counter (Gen).(2)
Generation of the initial population—The illustration of chromosome coding is shown in Figure3. x1 (i) represents the order priority value of generation 1, 0 < x (i) < 1. The smaller the value, the higher the priority. y1 (i) represents the resource allocation of generation 1, k = 1, 2, …, Kmax. Generate 3np individuals and among them select np with distinct characteristics. With one individual, calculate the tis, tie,RZ, QZ, and select the individual that meets the constraints (13)–(17). Otherwise, an individual is generated repeatedly until it meets all the constraints. Repair scheduling by chromosome decoding is shown in Figure 4.Because theRZ is integral form, it should be replaced by the sum of discrete forms. The repair finished time of node i can be got by decoding. Sort the repair finished time of node i in ascending order, the time axis can be divided into p segments. The calculation of RZ can be achieved by equation.(18)RZ=∫t0trZtdtZt0tr−t0=∑0p−1Ztp+1+Ztptp+1−tp2Zt0tr−t0.(3)
Classification according to the dominance criterion (nondominated sorting)—classify the individuals in fronts based on the value ofRz, Qz. The nondominated sorting criterion states that for two solutions, Xa and Xb, Xa dominates Xb if Xa is better than or equal to Xb in all objectives and Xa is better than Xb in at least one of the objectives. If there are no other decision variables that can dominate a decision variable, the decision variable is called a nondominated solution. All nondominated solutions in chromosome set X is defined as the first nondominated layer.(4)
Iterative process—while Gen <ngmax, repeat the following loop:(a)
Selection—the individuals selected for cross-over and mutation are chosen by tournaments which then select each individual in the following way: among the individuals of the population,ntour are randomly chosen and the best classified is selected according to the dominance criteria.(b)
Crossover—using operators for the crossover, resulting inc ∗ np descendants.(c)
Mutation—using operators for the mutation, resulting inm ∗ np individuals.(d)
Generation of the temporary population—with thenp individuals obtained through crossover and mutation, a new population is generated and added to the previous temporary population of 2np individuals.(e)
Classification of the temporary population—the 2np individuals of the temporary population are classified again according to the criteria of dominance and diversity.For the solutionXq∈X in the ist dominating layer, the crowding distance CXq can be calculated as equation.(19)CXq=QZXq+1−QZXq−1MaxQZX−MinQZX+RZXq+1−RZXq−1MaxRZX−MinRZX,whereMaxQzX and MinQzX are the maximum and minimum values of QzX in the ist dominant layer, respectively. MaxRzX and MinRzX are the maximum and minimum values of RzX in the ist dominant layer, respectively. QzXq+1 and QzXq−1 are the previous and next values of QzXq after the ascending order of QzX in the ist dominant layer. RzXq+1 and RzXq−1 are the previous and next values of RzXq in the ist dominant layer. The illustration can be shown in Figure 5. The farther each individual is located form the remaining solutions, the better its classification.(f)
Selection of a new population—A new population is obtained from the temporary population.(g)
Updating of the generation counter—Gen = Gen + 1.(h)
Output the Pareto front solutions.(4)
Stage two: output the optimal sequence scheme that maximizes the network efficiencyE (tr).Figure 3
Chromosome coding (Kmax = 3).Figure 4
Repair scheduling by chromosome decoding (Kmax = 3).Figure 5
Solution space of a problem with two objectives to be maximized.Calculate the network efficiencyE (tr) of each Pareto front solution and find out the one that makes the E (tr) maximized.The output of model isX=i,k,tis,tie,…,. i represents the node ID. k represents the node is repaired by team k. tis is the repair start time of node i. tie is the repair finished time of node i.


## 3. Case Study

The performance indicators of restoration sequence scheme include “The percent of repaired nodes,” “The total budget,” “The total recovery time,” “The resilience index of theZ,” “The recovery ratio of Z,” and “The recovery ratio of E.” Indicators 2 to 5 also appeared in the scenario setup. However, scenario setup only provides those indicator’s upper or lower limits. The optimization results can provide the specific values of those indicators. Those values can be used to compare the different restoration sequence schemes.


### 3.1. Scenario I: The Location of the Damaged Stations Is Aggregated in Nanjing Metro

#### 3.1.1. Scenario Descriptions

Until May 2020, Nanjing’s metro operated ten lines, with a total length of 378 km, and 174 stations, including 13 transfer stations. The SpaceL method is used to construct network topology. Some stations of Nanjing metro in the CBD are closed because of a natural disaster, which can be shown in Figure 6. There are twenty stations and four lines affected. Table 2 shows that each damaged station’s repair time obeys normal distribution. It reflects the uncertainty of repair time. Because the transfer stations often serve multiple lines, we assume they have a longer repair time than the remaining stations.Figure 6
Affected zone of the Nanjing Metro in scenario I.
(a)(b)Table 2
The distribution of repair time for damaged stations in scenario I.
IDMean,ti¯Variance,δiIDMean,ti¯Variance,δi7, 10, 24, 97, 117, 118318, 13, 25, 99, 100, 1164112, 27, 28, 1015111, 98619, 2671The objective of the base scenarios is to maximize theE under the condition that the Z’s resilience index and recovery rate reach 0.5 and 90% at least, respectively. The parameters of the model are shown in Table 3.Table 3
The value of parameters of the model in scenario II and III.
The meaning of the parameterParameterValueThe pregiven deadline time (day)tr19The limitation of the total budget ($)U55000The lower limit ofZ’s resilience indexf10.50The lower limit ofZ’s recovery ratiof290%The cost of each day’s work for a maintenance team ($)θ1000The maximized budget for one day ($)u3200


#### 3.1.2. The Optimal Restoration Sequence Scheme in Scenario I

The NSGA-II and GA are used to search the optimal solutions for scenario I. The numerical application is performed on an ordinary desktop with Intel(R) Core i7-6700K CPU @ 8.00 GHz CPU and 16 GB memory. All algorithms are solved by Python.According to Section2.5, the solution process is divided into two-stage. The first stage aims to make the network accessibility’s resilience index RZ and recovery rate QZ reach to the threshold and maximize as much as possible. The NSGA-II algorithm is adopted to find the Pareto front solutions. The second stage aims to find out the optimal restoration sequence scheme to maximize the network efficiency E from the Pareto front solutions.Before using the GA algorithm, the model’s objective should be changed as equation (20). The sum of l1, l2, and l3 is one. In this case, l1 = 0.5, l2 = l3 = 0.25.(20)SAT=Maxl1E+l2RZ+l3QZ.NSGA-II and GA algorithm are both based on the damaged stations’ repair time equal to the mean value. The most appropriate parameter settings in NSGA-II and GA are shown in Table4.Table 4
The most appropriate parameter settings of NSGA-II and GA.
ParameterNSGA-IIGAPopulation (np)100100Maximum generations (ngmax)100100Cross-over rate (c)0.90.9Mutation rate (mr)0.70.6Number of individuals in each tournament (ntour)10—Figures7 and 8 illustrate the convergence of NSGA-II and GA over generations. The average computing time of NSGA-II is 6.9 min, and the GA is 3.3 min. Although the GA can achieve convergence about the 30th generation, NSGA-II also has a faster convergence speed, indicating fast convergence and good stability. However, GA for multi-objective optimization is limited by weight. Different weights lead to different results. NSGA-II can fill this gap and generate the Pareto frontier. NSGA-II can obtain some non-dominated solutions. The optimal sequence solution maximizes the network efficiency E from the Pareto frontier. The solutions can be shown in Figure 9.Figure 7
Convergence of optimization of NSGA-II.Figure 8
Convergence of optimization of GA.Figure 9
Solution set and Pareto frontier of restoration schedules.Table5 and Figure 10 illustrate the optimal restoration sequence in scenario I. Because every node i’s repair time follows a specific normal distribution, the optimal restoration sequence scheme is not the only one. When each station’s repair time is shorter, the best results of the optimal scheme can be achieved. When each station’s repair time is longer, the worst results of the optimal scheme are realised. Through comparison of the best and the worst, the total budget only increases by 7.84%, the number of repaired stations increases by 36.36%, the resilience index of the Z increases by 74.21%, the recovery ratio of the Z and the E improve by 13.26% and 8.38% respectively, but the total recovery time only extends one day. In this case, the recovery time is mainly limited by the total budget. If the total budget is adequate and can support all nodes repaired, the best scheme’s total recovery time must be smaller than the worst. After all, the former repaired 75% of the nodes in 18 days, but the latter only repaired 55% of the nodes in 19 days. It is worth mentioning that the worst scheme does not satisfy the resilience constraints of objective of Table 3. It aims to reveal the sensitivity of the repair time’s uncertainty.Table 5
The optimal restoration sequence in scenario I.
IndicatorsThe best of the optimal schemeThe worst of the optimal schemeAverage valueIgnore uncertaintyThe sequences of the repaired nodesA: 24, 117, 7, 117, 10, 116A: 7, 24, 8, 13—A: 24, 98, 9, 26B: 97, 12, 9, 11, 12,B: 97, 98, 99, 25B: 97, 25, 99, 11C: 118, 25, 99, 26, 27C: 118, 117, 9C: 118, 7, 117, 10The percent of repaired nodes75%55%65%60%The total budget ($)51000550005300052000The total recovery time (day)181918.618The resilience index of theZ0.6080.3490.4860.503The recovery ratio ofZ98.46%86.93%93.74%92.80%The recovery ratio ofE87.91%81.11%84.60%82.25%Figure 10
The optimal scheme based on the model in scenario I considering uncertainty.


#### 3.1.3. The Comparison of Proposed Optimal Scheme with Other Schemes

This paper also analyses the advantage of optimal schemes compared to random alternatives, which can be obtained by the way of free combination. In Figure11, the blue line is the optimal restoration scheme based on the model. The red dots are Z’s value of random schemes on different days. The green line is the average Z of random schemes, which can be called an average random scheme. From the 1st to the 11th day, Z’s recovery is very slow. However, after the 11th day, the advantage of the optimal scheme becomes more obvious, especially between days 12 and 13 where the Z is increases by approximately 113%. Although the average random scheme’s Z is higher than the optimal scheme on some days, its resilience index dropped by 42.8%.Figure 11
The optimal schemes with different strategies in scenario I (ignore uncertainty).This paper also compares the objective values (the blue line in Figure11) and KPIs with a solution that repairs the transfer stations first (the yellow line in Figure 11). The yellow line gradually increases and has a significant upward trend after the 13th day. The blue one gradually increases for the first 12 days, then goes up suddenly and always stays at a higher value. The resilience index of the yellow is smaller than the blue. The reasons are as follows: the repair time of transfer stations is longer than nontransfer stations. They need more time to be repaired, so the network’s recovery is slow in the early time. By analysing the transfer stations’ location, even they are repaired, they cannot connect with other no-damaged stations. Thus, giving them priority has little influence on the whole network recovery. For the optimal scheme, the number of repaired nodes are increasing as time goes on. Alternative paths will exist in the damaged network. Other nodes may replace the function of transfer station. Thus, even without giving priority to transfer stations, Z can continue to grow.


#### 3.1.4. Sensitivity Analysis

(1) The Influence of Changing the Restoration Objective in Scenario I. The optimization of this part is based on the results of scenario I without considering uncertainty. After the restoration of scenario I, there are 8 stations are left behind and need to be repaired in Nanjing metro (ID: 8, 12, 13, 27, 28, 100, 101, 116). In this stage, the new objective is to make the Z recover to 100% and maximize the E. Besides, the pregiven deadline time and the budget limitation change to 35 days and 90000$, respectively. Other parameters are same as Table 3. The meaning of part is to illustrate the flexibility of the model. Decision-makers can make different objectives according to the recovery situation and remaining resources. Figure 12 demonstrates the optimal restoration schemes with different maintenance teams. All the nodes are repaired in those conditions, however with 3 teams compared to with 2 teams. The Z sees little improvement after the 22nd day, the total recovery time shortens by 3 days, the resilience index improves by 3.51%, and the Z can recover to 100% three days earlier.Figure 12
The optimal restoration sequence schemes with different objectives in scenario I.(2) The Influence of the Maximized Budget for One Day in Scenario I. This part aims to analyze the influence of the maximized budget for one day (u) on the optimal restoration scheme. Assume there are three different u ($2200, $3200, $4000) in scenario I, and the optimal sequence schemes of them be shown in Figure 13. Because the total budget is the same, except for the total recovery time and resilience index of the Z, other indicators do not change. The maximized budget for one day directly affects the number of synchronous maintenance teams, and when the teams increase from 2 to 3, the total recovery time is reduced by eight days. However, the resilience index has little change, with an increase of 6.34%. When the number of synchronous teams increases to 4, the total recovery time only shortens by three days and the resilience index only increases by 1.19%. Therefore, we can imply that increasing the synchronous number of maintenance teams blindly does not achieve the desired effects and may lead to the wasting of resources.Figure 13
The sensitivity analysis of the maximized budget for one day in scenario I.(3) The Influence of the Total Budget in Scenario I. This part aims to analyze the influence of the total budget (U) on optimal restoration scheme. Assume there are three different total budget limitations ($40000, $55000, $70000) in scenario I, and the optimal sequence schemes can be shown in Table 6. All the indicators grow with total budget increase. When the number of repaired nodes equals 80% of the total number, the Z can recover to 100%. Examining budgets of $55,000 and $70,000, the E’s recovery ratio and Z’s resilience index increase by 8.57% and 21.07%, respectively, and the total recovery time is reduced by six days. It is worth mentioning that the scheme with $40,000 does not satisfy the resilience constraints, where the purpose is to reveal the sensitivity of the total budget. As the total budget affects the number of repaired nodes directly, when 50% of the total number nodes are repaired, the resilience index only is 0.362. However, when 60% of the total number nodes are repaired, the resilience index and recovery ratio of Z can meet the resilience constraints of objective, showing that the total budget is vital for recovery.Table 6
The sensitivity analysis of the limitation of the total budget in scenario I.
Total budget limitationU40000 ($)55000 ($)70000 ($)The sequences of the repaired nodesA: 24, 98, 9, 10A: 24, 98, 9, 26A: 24, 98, 9, 26, 27, 100B: 97, 25, 99B: 97, 25, 99, 11B: 97, 25, 99, 11, 13C: 118, 7, 117C: 118, 7, 117, 10C: 118, 7, 117, 10, 116The total recovery time (day)141824The percent of repaired nodes50%60%80%The total budget ($)390005200069000The resilience index of theZ0.3620.5030.609The recovery ratio ofZ86.9%92.8%100%The recovery ratio ofE76.91%82.25%89.3%


### 3.2. Scenario II: The Location of the Damaged Stations Is Aggregated in Zhengzhou Metro

#### 3.2.1. Scenario Descriptions

We also set up a similar scenario to compare the results with different network structure. Until March 2021, Zhengzhou metro has six lines and 114 stations, shown in Figure14. Zhengzhou Metro is a typical radioactive network with a ring line. Line 5 is a ring line. Twenty stations and four lines also are affected because of a natural disaster. There are eight stations damaged in ring line 5. The repair time distribution of damaged stations is similar to the Nanjing metro, shown in Table 7. It reflects the uncertainty of repair time.Figure 14
Affected zone of the Zhengzhou metro in scenario II.Table 7
The distribution of repair time for damaged stations in scenario II.
IDMeanti¯VarianceδiIDMeanti¯Varianceδi17, 80, 81, 105, 107, 1103120, 22, 41, 106, 108, 1094119, 23, 42, 835118, 436121, 8271The objective of the base scenarios is to maximize theE under the condition that the Z’s resilience index and recovery rate reach 0.5 and 90% at least, respectively. The parameters of the model are same as Table 3.


#### 3.2.2. The Optimal Restoration Sequence Scheme in Scenario II

The network size of Zhengzhou and Nanjing metro is similar. The Zhengzhou metro’sZ is smaller than Nanjing metro before a disaster. However, the E is larger than Nanjing. After a disaster, Zhengzhou’s Z only decreased by 36.13%, but the Nanjing metro’s Z decreased by 74.97%. It can prove that the ring line is critical to improve network efficiency. It also can effectively maintain network accessibility after a disaster.The optimal restoration sequence scheme is shown in the green line in Figures15 and 16. We also contrast the optimal sequence scheme with transfer station priority and no transfer station priority. By analysing performance indicators, other indicators are the same except the resilience index. Different from the results of the Nanjing, the resilience index of giving transfer station priority is bigger than no transfer station priority. However, the difference in resilience index between them is slight. The former is increased by 0.45% than the latter. By analysing the position of the damaged transfer station, node 18, node 21, and node 43 are close to unaffected stations. Even transfer stations need more repair time, giving them priority may be bad for early recovery. However, they are close to unaffected stations, the recovery in the latter days is better than the red line.Figure 15
The restoration sequence with different priority in scenario II.Figure 16
The resilience change of restoration sequences with different priority in scenario II.


#### 3.2.3. Sensitivity Analysis

(1) The Influence of Damaged Stations’ Repair Time in Scenario II. This part aims to check the sensitivity of damaged stations’ repair time distribution. Assume all damage stations’ repair time equals 4.5 days in scenario II, and the results show in Figure 17. The red line’s resilience index is increased by 2% than the one that gives transfer station priority. In this case, giving transfer station priority is also not the optimal strategy. It can further prove that repairing the transfer station firstly is unsuitable for all situations. Especially in the case of majority transfer stations being far away from unaffected stations.Figure 17
The sensitivity of damaged stations’ repair time distribution in scenario II.(2) The Influence of Different Network Structure Based on Zhengzhou Metro. This part aims to analyze the influence of the damaged stations’ structure. Comparing the damaged stations’ locations of scenario I and II, we find that scenario I’s transfer stations are closer to the unaffected stations. This scenario changes the damaged stations’ location based on the Zhengzhou metro, shown in Figure 18. It is more similar to scenario I than scenario II. Except for the network structure, other model setups are the same as scenario II.Figure 18
Affected zone of the metro in scenario II-I based on the Zhengzhou metro.We contrast the optimal restoration sequence with transfer station priority and no transfer station priority in scenario II-I. The results can be shown in Figures19 and 20. The red line’s resilience index is larger than the green line, increasing by 3.6%. This result is entirely different from scenario II but similar to the scenario I. In this scenario, giving transfer station priority is not the optimal strategy.Figure 19
The optimal restoration sequence with different priority in scenario II-I.Figure 20
The resilience change of restoration sequences with different priority in scenario II-I.


### 3.3. Scenario III: The Location of the Damaged Stations Is Scattered in Nanjing Metro

#### 3.3.1. Scenario Descriptions

Because of man-made attack, some important stations are attacked and cannot operate, the affected stations are shown in Table8 and Figure 21. The percent of the transfer station is 75%. The repair time of each station obeys normal distribution ti∼N5,1, and unit time is day. Because those stations are relatively important and lots of lines are affected, so decision-maker want to make the E and Z’s resilience index maximized under some budget restrictions. In other words, an optimal restoration scheme should make the network recover to a normal state and meet pregiven resilience requirement, the model parameters are shown as Table 9.Table 8
The affected stations in Nanjing metro in scenario III.
IDThe degree of the stationThe affected linesIDThe degree of the stationThe affected lines242, 10531, 101441, 323222642, 34451, 3, S19843, 410823Figure 21
Damaged stations of the Nanjing Metro in scenario III.Table 9
The value of parameters of the model in scenario III.
The meaning of the parameterParameterValueThe pregiven deadline time (day)tr12The limitation of the total budget ($)U42000The resilience index ofZf1MaximizeThe lower limit ofZ’s recovery ratiof2100%The cost of one day’s work for a maintenance team ($)θ1000The maximized budget for one day ($)u4000The set of damaged nodes (ID)Nd2, 5, 14, 23, 26, 44, 98, 108


#### 3.3.2. The Optimal Restoration Sequence Scheme in Scenario III

By the analysis of Table9, four maintenance teams can work at the same time. Because the repair time is uncertain, the optimal scheme is not only one. Firstly, if the uncertainty is not considered, the network performance curve of the optimal scheme is shown in Figure 22 (the red line of 4 teams). The restoration plan for the maintenance teams is shown in Figure 23. After 10 days, all the stations are repaired and the network recovers to a normal state. The resilience index of this scheme is maximized, which means the network accessibility recovery more quickly and effectively than all the alternatives.Figure 22
The optimal restoration sequence schemes with different maintenance teams in scenario III.Figure 23
The optimal restoration plan for 4 maintenance teams in scenario III.Because the optimization model also considered the recovery process (resilience index), so the repair sequence is closely related to each node’s repair time. After many simulations, we can get the result of how much the variability of restoration time affects the variability of network accessibility. Taking the repair time uncertainty into account, Figure24 shows the 150 optimal restoration sequence schemes’ network accessibility probability distribution when four teams work synchronously. It can be obtained by executing the program 150 times after randomly giving each node’s repair time according to the distribution function. The network accessibility’s resilience index range is (0.734–0.754). The mean value is 0.745, and the variance is 0.011. Under the budget limitation, the Z’s resilience index and node’s repair time are negatively correlated. The shorter the repair time of nodes, the more nodes are repaired, and the greater the resilience index of network accessibility. The resilience index’s mean value is approximately equal to the resilience index that does not consider repair uncertainty (0.744).Figure 24
Probability distribution of theZ’s resilience index in scenario III (4 teams).Figure25 illustrates the probability distribution of total recovery time. The shortest recovery time is 8 days, and the longest recovery time is 12 days. The average of recovery time is 10.2 days. Because each station’s repair time obeys normal distribution, the total recovery time obeys normal distribution too.Figure 25
Probability distribution of the total recovery time in scenario III (4 teams).


#### 3.3.3. Sensitivity Analysis

(1) The Influence of the Maximized Budget for One Day in Scenario III. If prolong the pre-given deadline time to 20 days, Figure 22 also illustrates the different network performance curves of schemes with different synchronous maintenance teams. This comparison is based on the damaged station repair time equal to their mean value, which means it does not consider repair time uncertainty. By contrasting the indicators of Table 10, it can be found that with the increase in the number of maintenance teams, the resilience index becomes bigger. By comparing the 4 teams and 2 teams, the total recovery time shortens by 50% and the resilience index improves by 36.51%. But the total recovery time of 3 teams and 4-2 teams is the same because the multiple teams repairing one station at the same time is not allowed. Interestingly, the stations’ repair sequence does not change. The station with a bigger node degree is repaired earlier. Firstly, the node 44 with degree 5 is repaired, then the set of nodes whose degree are 4 are repaired, the nodes with degree 3 and 2 are subsequently repaired, which means transfer stations with bigger node degree should be given priority in restoration to make network recover quickly and efficiently.Table 10
The sensitive analysis of synchronous maintenance teams in scenario III.
Indicators2 teams3 teams4-2 teams4 teamsThe sequences of the repaired nodesA: 44, 14, 2, 23A: 44, 98, 23A: 44, 2, 23A: 44, 2B: 26, 2, 108B: 26, 5, 108B: 26, 5B: 26, 98, 5, 108C: 14, 5C: 14C: 14, 23D: 98D: 98, 108The percent of repaired nodes100%100%100%100%The total budget ($)40000400004000040000The total recovery time (day)20151510The resilience index ofZ0.5450.6970.7180.744The recovery ratio ofZ100%100%100%100%The recovery ratio ofE100%100%100%100%(2) The Influence of Damaged Stations’ Repair Time in Scenario III. This part aims to check the sensitivity of damaged stations’ repair time distribution. Assume damage transfer stations’ repair time equal 6 days in scenario III, and other damaged stations’ repair time equal 3 days, the results shown in Figure 26. Those schemes’ resilience index is very similar, but the optimal sequence is not based on transfer station priority. The optimal restoration plan shown in Figure 27. In this case, giving transfer station priority is not the optimal strategy. It can prove that damaged stations’ repair time significantly influences the optimal sequence scheme. Repairing the transfer station firstly is unsuitable for all situations. The reason is that the transfer stations need more time to be repaired. If all transfer stations are repaired first, the early stage’s recovery will be prolonged and affect the whole stages’ recovery.Figure 26
The sensitivity of damaged stations’ repair time distribution in scenario III.Figure 27
The optimal restoration plan for 4 maintenance teams in scenario III.


## 3.1. Scenario I: The Location of the Damaged Stations Is Aggregated in Nanjing Metro

### 3.1.1. Scenario Descriptions

Until May 2020, Nanjing’s metro operated ten lines, with a total length of 378 km, and 174 stations, including 13 transfer stations. The SpaceL method is used to construct network topology. Some stations of Nanjing metro in the CBD are closed because of a natural disaster, which can be shown in Figure 6. There are twenty stations and four lines affected. Table 2 shows that each damaged station’s repair time obeys normal distribution. It reflects the uncertainty of repair time. Because the transfer stations often serve multiple lines, we assume they have a longer repair time than the remaining stations.Figure 6
Affected zone of the Nanjing Metro in scenario I.
(a)(b)Table 2
The distribution of repair time for damaged stations in scenario I.
IDMean,ti¯Variance,δiIDMean,ti¯Variance,δi7, 10, 24, 97, 117, 118318, 13, 25, 99, 100, 1164112, 27, 28, 1015111, 98619, 2671The objective of the base scenarios is to maximize theE under the condition that the Z’s resilience index and recovery rate reach 0.5 and 90% at least, respectively. The parameters of the model are shown in Table 3.Table 3
The value of parameters of the model in scenario II and III.
The meaning of the parameterParameterValueThe pregiven deadline time (day)tr19The limitation of the total budget ($)U55000The lower limit ofZ’s resilience indexf10.50The lower limit ofZ’s recovery ratiof290%The cost of each day’s work for a maintenance team ($)θ1000The maximized budget for one day ($)u3200


### 3.1.2. The Optimal Restoration Sequence Scheme in Scenario I

The NSGA-II and GA are used to search the optimal solutions for scenario I. The numerical application is performed on an ordinary desktop with Intel(R) Core i7-6700K CPU @ 8.00 GHz CPU and 16 GB memory. All algorithms are solved by Python.According to Section2.5, the solution process is divided into two-stage. The first stage aims to make the network accessibility’s resilience index RZ and recovery rate QZ reach to the threshold and maximize as much as possible. The NSGA-II algorithm is adopted to find the Pareto front solutions. The second stage aims to find out the optimal restoration sequence scheme to maximize the network efficiency E from the Pareto front solutions.Before using the GA algorithm, the model’s objective should be changed as equation (20). The sum of l1, l2, and l3 is one. In this case, l1 = 0.5, l2 = l3 = 0.25.(20)SAT=Maxl1E+l2RZ+l3QZ.NSGA-II and GA algorithm are both based on the damaged stations’ repair time equal to the mean value. The most appropriate parameter settings in NSGA-II and GA are shown in Table4.Table 4
The most appropriate parameter settings of NSGA-II and GA.
ParameterNSGA-IIGAPopulation (np)100100Maximum generations (ngmax)100100Cross-over rate (c)0.90.9Mutation rate (mr)0.70.6Number of individuals in each tournament (ntour)10—Figures7 and 8 illustrate the convergence of NSGA-II and GA over generations. The average computing time of NSGA-II is 6.9 min, and the GA is 3.3 min. Although the GA can achieve convergence about the 30th generation, NSGA-II also has a faster convergence speed, indicating fast convergence and good stability. However, GA for multi-objective optimization is limited by weight. Different weights lead to different results. NSGA-II can fill this gap and generate the Pareto frontier. NSGA-II can obtain some non-dominated solutions. The optimal sequence solution maximizes the network efficiency E from the Pareto frontier. The solutions can be shown in Figure 9.Figure 7
Convergence of optimization of NSGA-II.Figure 8
Convergence of optimization of GA.Figure 9
Solution set and Pareto frontier of restoration schedules.Table5 and Figure 10 illustrate the optimal restoration sequence in scenario I. Because every node i’s repair time follows a specific normal distribution, the optimal restoration sequence scheme is not the only one. When each station’s repair time is shorter, the best results of the optimal scheme can be achieved. When each station’s repair time is longer, the worst results of the optimal scheme are realised. Through comparison of the best and the worst, the total budget only increases by 7.84%, the number of repaired stations increases by 36.36%, the resilience index of the Z increases by 74.21%, the recovery ratio of the Z and the E improve by 13.26% and 8.38% respectively, but the total recovery time only extends one day. In this case, the recovery time is mainly limited by the total budget. If the total budget is adequate and can support all nodes repaired, the best scheme’s total recovery time must be smaller than the worst. After all, the former repaired 75% of the nodes in 18 days, but the latter only repaired 55% of the nodes in 19 days. It is worth mentioning that the worst scheme does not satisfy the resilience constraints of objective of Table 3. It aims to reveal the sensitivity of the repair time’s uncertainty.Table 5
The optimal restoration sequence in scenario I.
IndicatorsThe best of the optimal schemeThe worst of the optimal schemeAverage valueIgnore uncertaintyThe sequences of the repaired nodesA: 24, 117, 7, 117, 10, 116A: 7, 24, 8, 13—A: 24, 98, 9, 26B: 97, 12, 9, 11, 12,B: 97, 98, 99, 25B: 97, 25, 99, 11C: 118, 25, 99, 26, 27C: 118, 117, 9C: 118, 7, 117, 10The percent of repaired nodes75%55%65%60%The total budget ($)51000550005300052000The total recovery time (day)181918.618The resilience index of theZ0.6080.3490.4860.503The recovery ratio ofZ98.46%86.93%93.74%92.80%The recovery ratio ofE87.91%81.11%84.60%82.25%Figure 10
The optimal scheme based on the model in scenario I considering uncertainty.


### 3.1.3. The Comparison of Proposed Optimal Scheme with Other Schemes

This paper also analyses the advantage of optimal schemes compared to random alternatives, which can be obtained by the way of free combination. In Figure11, the blue line is the optimal restoration scheme based on the model. The red dots are Z’s value of random schemes on different days. The green line is the average Z of random schemes, which can be called an average random scheme. From the 1st to the 11th day, Z’s recovery is very slow. However, after the 11th day, the advantage of the optimal scheme becomes more obvious, especially between days 12 and 13 where the Z is increases by approximately 113%. Although the average random scheme’s Z is higher than the optimal scheme on some days, its resilience index dropped by 42.8%.Figure 11
The optimal schemes with different strategies in scenario I (ignore uncertainty).This paper also compares the objective values (the blue line in Figure11) and KPIs with a solution that repairs the transfer stations first (the yellow line in Figure 11). The yellow line gradually increases and has a significant upward trend after the 13th day. The blue one gradually increases for the first 12 days, then goes up suddenly and always stays at a higher value. The resilience index of the yellow is smaller than the blue. The reasons are as follows: the repair time of transfer stations is longer than nontransfer stations. They need more time to be repaired, so the network’s recovery is slow in the early time. By analysing the transfer stations’ location, even they are repaired, they cannot connect with other no-damaged stations. Thus, giving them priority has little influence on the whole network recovery. For the optimal scheme, the number of repaired nodes are increasing as time goes on. Alternative paths will exist in the damaged network. Other nodes may replace the function of transfer station. Thus, even without giving priority to transfer stations, Z can continue to grow.


### 3.1.4. Sensitivity Analysis

(1) The Influence of Changing the Restoration Objective in Scenario I. The optimization of this part is based on the results of scenario I without considering uncertainty. After the restoration of scenario I, there are 8 stations are left behind and need to be repaired in Nanjing metro (ID: 8, 12, 13, 27, 28, 100, 101, 116). In this stage, the new objective is to make the Z recover to 100% and maximize the E. Besides, the pregiven deadline time and the budget limitation change to 35 days and 90000$, respectively. Other parameters are same as Table 3. The meaning of part is to illustrate the flexibility of the model. Decision-makers can make different objectives according to the recovery situation and remaining resources. Figure 12 demonstrates the optimal restoration schemes with different maintenance teams. All the nodes are repaired in those conditions, however with 3 teams compared to with 2 teams. The Z sees little improvement after the 22nd day, the total recovery time shortens by 3 days, the resilience index improves by 3.51%, and the Z can recover to 100% three days earlier.Figure 12
The optimal restoration sequence schemes with different objectives in scenario I.(2) The Influence of the Maximized Budget for One Day in Scenario I. This part aims to analyze the influence of the maximized budget for one day (u) on the optimal restoration scheme. Assume there are three different u ($2200, $3200, $4000) in scenario I, and the optimal sequence schemes of them be shown in Figure 13. Because the total budget is the same, except for the total recovery time and resilience index of the Z, other indicators do not change. The maximized budget for one day directly affects the number of synchronous maintenance teams, and when the teams increase from 2 to 3, the total recovery time is reduced by eight days. However, the resilience index has little change, with an increase of 6.34%. When the number of synchronous teams increases to 4, the total recovery time only shortens by three days and the resilience index only increases by 1.19%. Therefore, we can imply that increasing the synchronous number of maintenance teams blindly does not achieve the desired effects and may lead to the wasting of resources.Figure 13
The sensitivity analysis of the maximized budget for one day in scenario I.(3) The Influence of the Total Budget in Scenario I. This part aims to analyze the influence of the total budget (U) on optimal restoration scheme. Assume there are three different total budget limitations ($40000, $55000, $70000) in scenario I, and the optimal sequence schemes can be shown in Table 6. All the indicators grow with total budget increase. When the number of repaired nodes equals 80% of the total number, the Z can recover to 100%. Examining budgets of $55,000 and $70,000, the E’s recovery ratio and Z’s resilience index increase by 8.57% and 21.07%, respectively, and the total recovery time is reduced by six days. It is worth mentioning that the scheme with $40,000 does not satisfy the resilience constraints, where the purpose is to reveal the sensitivity of the total budget. As the total budget affects the number of repaired nodes directly, when 50% of the total number nodes are repaired, the resilience index only is 0.362. However, when 60% of the total number nodes are repaired, the resilience index and recovery ratio of Z can meet the resilience constraints of objective, showing that the total budget is vital for recovery.Table 6
The sensitivity analysis of the limitation of the total budget in scenario I.
Total budget limitationU40000 ($)55000 ($)70000 ($)The sequences of the repaired nodesA: 24, 98, 9, 10A: 24, 98, 9, 26A: 24, 98, 9, 26, 27, 100B: 97, 25, 99B: 97, 25, 99, 11B: 97, 25, 99, 11, 13C: 118, 7, 117C: 118, 7, 117, 10C: 118, 7, 117, 10, 116The total recovery time (day)141824The percent of repaired nodes50%60%80%The total budget ($)390005200069000The resilience index of theZ0.3620.5030.609The recovery ratio ofZ86.9%92.8%100%The recovery ratio ofE76.91%82.25%89.3%


## 3.1.1. Scenario Descriptions

Until May 2020, Nanjing’s metro operated ten lines, with a total length of 378 km, and 174 stations, including 13 transfer stations. The SpaceL method is used to construct network topology. Some stations of Nanjing metro in the CBD are closed because of a natural disaster, which can be shown in Figure 6. There are twenty stations and four lines affected. Table 2 shows that each damaged station’s repair time obeys normal distribution. It reflects the uncertainty of repair time. Because the transfer stations often serve multiple lines, we assume they have a longer repair time than the remaining stations.Figure 6
Affected zone of the Nanjing Metro in scenario I.
(a)(b)Table 2
The distribution of repair time for damaged stations in scenario I.
IDMean,ti¯Variance,δiIDMean,ti¯Variance,δi7, 10, 24, 97, 117, 118318, 13, 25, 99, 100, 1164112, 27, 28, 1015111, 98619, 2671The objective of the base scenarios is to maximize theE under the condition that the Z’s resilience index and recovery rate reach 0.5 and 90% at least, respectively. The parameters of the model are shown in Table 3.Table 3
The value of parameters of the model in scenario II and III.
The meaning of the parameterParameterValueThe pregiven deadline time (day)tr19The limitation of the total budget ($)U55000The lower limit ofZ’s resilience indexf10.50The lower limit ofZ’s recovery ratiof290%The cost of each day’s work for a maintenance team ($)θ1000The maximized budget for one day ($)u3200


## 3.1.2. The Optimal Restoration Sequence Scheme in Scenario I

The NSGA-II and GA are used to search the optimal solutions for scenario I. The numerical application is performed on an ordinary desktop with Intel(R) Core i7-6700K CPU @ 8.00 GHz CPU and 16 GB memory. All algorithms are solved by Python.According to Section2.5, the solution process is divided into two-stage. The first stage aims to make the network accessibility’s resilience index RZ and recovery rate QZ reach to the threshold and maximize as much as possible. The NSGA-II algorithm is adopted to find the Pareto front solutions. The second stage aims to find out the optimal restoration sequence scheme to maximize the network efficiency E from the Pareto front solutions.Before using the GA algorithm, the model’s objective should be changed as equation (20). The sum of l1, l2, and l3 is one. In this case, l1 = 0.5, l2 = l3 = 0.25.(20)SAT=Maxl1E+l2RZ+l3QZ.NSGA-II and GA algorithm are both based on the damaged stations’ repair time equal to the mean value. The most appropriate parameter settings in NSGA-II and GA are shown in Table4.Table 4
The most appropriate parameter settings of NSGA-II and GA.
ParameterNSGA-IIGAPopulation (np)100100Maximum generations (ngmax)100100Cross-over rate (c)0.90.9Mutation rate (mr)0.70.6Number of individuals in each tournament (ntour)10—Figures7 and 8 illustrate the convergence of NSGA-II and GA over generations. The average computing time of NSGA-II is 6.9 min, and the GA is 3.3 min. Although the GA can achieve convergence about the 30th generation, NSGA-II also has a faster convergence speed, indicating fast convergence and good stability. However, GA for multi-objective optimization is limited by weight. Different weights lead to different results. NSGA-II can fill this gap and generate the Pareto frontier. NSGA-II can obtain some non-dominated solutions. The optimal sequence solution maximizes the network efficiency E from the Pareto frontier. The solutions can be shown in Figure 9.Figure 7
Convergence of optimization of NSGA-II.Figure 8
Convergence of optimization of GA.Figure 9
Solution set and Pareto frontier of restoration schedules.Table5 and Figure 10 illustrate the optimal restoration sequence in scenario I. Because every node i’s repair time follows a specific normal distribution, the optimal restoration sequence scheme is not the only one. When each station’s repair time is shorter, the best results of the optimal scheme can be achieved. When each station’s repair time is longer, the worst results of the optimal scheme are realised. Through comparison of the best and the worst, the total budget only increases by 7.84%, the number of repaired stations increases by 36.36%, the resilience index of the Z increases by 74.21%, the recovery ratio of the Z and the E improve by 13.26% and 8.38% respectively, but the total recovery time only extends one day. In this case, the recovery time is mainly limited by the total budget. If the total budget is adequate and can support all nodes repaired, the best scheme’s total recovery time must be smaller than the worst. After all, the former repaired 75% of the nodes in 18 days, but the latter only repaired 55% of the nodes in 19 days. It is worth mentioning that the worst scheme does not satisfy the resilience constraints of objective of Table 3. It aims to reveal the sensitivity of the repair time’s uncertainty.Table 5
The optimal restoration sequence in scenario I.
IndicatorsThe best of the optimal schemeThe worst of the optimal schemeAverage valueIgnore uncertaintyThe sequences of the repaired nodesA: 24, 117, 7, 117, 10, 116A: 7, 24, 8, 13—A: 24, 98, 9, 26B: 97, 12, 9, 11, 12,B: 97, 98, 99, 25B: 97, 25, 99, 11C: 118, 25, 99, 26, 27C: 118, 117, 9C: 118, 7, 117, 10The percent of repaired nodes75%55%65%60%The total budget ($)51000550005300052000The total recovery time (day)181918.618The resilience index of theZ0.6080.3490.4860.503The recovery ratio ofZ98.46%86.93%93.74%92.80%The recovery ratio ofE87.91%81.11%84.60%82.25%Figure 10
The optimal scheme based on the model in scenario I considering uncertainty.


## 3.1.3. The Comparison of Proposed Optimal Scheme with Other Schemes

This paper also analyses the advantage of optimal schemes compared to random alternatives, which can be obtained by the way of free combination. In Figure11, the blue line is the optimal restoration scheme based on the model. The red dots are Z’s value of random schemes on different days. The green line is the average Z of random schemes, which can be called an average random scheme. From the 1st to the 11th day, Z’s recovery is very slow. However, after the 11th day, the advantage of the optimal scheme becomes more obvious, especially between days 12 and 13 where the Z is increases by approximately 113%. Although the average random scheme’s Z is higher than the optimal scheme on some days, its resilience index dropped by 42.8%.Figure 11
The optimal schemes with different strategies in scenario I (ignore uncertainty).This paper also compares the objective values (the blue line in Figure11) and KPIs with a solution that repairs the transfer stations first (the yellow line in Figure 11). The yellow line gradually increases and has a significant upward trend after the 13th day. The blue one gradually increases for the first 12 days, then goes up suddenly and always stays at a higher value. The resilience index of the yellow is smaller than the blue. The reasons are as follows: the repair time of transfer stations is longer than nontransfer stations. They need more time to be repaired, so the network’s recovery is slow in the early time. By analysing the transfer stations’ location, even they are repaired, they cannot connect with other no-damaged stations. Thus, giving them priority has little influence on the whole network recovery. For the optimal scheme, the number of repaired nodes are increasing as time goes on. Alternative paths will exist in the damaged network. Other nodes may replace the function of transfer station. Thus, even without giving priority to transfer stations, Z can continue to grow.


## 3.1.4. Sensitivity Analysis

(1) The Influence of Changing the Restoration Objective in Scenario I. The optimization of this part is based on the results of scenario I without considering uncertainty. After the restoration of scenario I, there are 8 stations are left behind and need to be repaired in Nanjing metro (ID: 8, 12, 13, 27, 28, 100, 101, 116). In this stage, the new objective is to make the Z recover to 100% and maximize the E. Besides, the pregiven deadline time and the budget limitation change to 35 days and 90000$, respectively. Other parameters are same as Table 3. The meaning of part is to illustrate the flexibility of the model. Decision-makers can make different objectives according to the recovery situation and remaining resources. Figure 12 demonstrates the optimal restoration schemes with different maintenance teams. All the nodes are repaired in those conditions, however with 3 teams compared to with 2 teams. The Z sees little improvement after the 22nd day, the total recovery time shortens by 3 days, the resilience index improves by 3.51%, and the Z can recover to 100% three days earlier.Figure 12
The optimal restoration sequence schemes with different objectives in scenario I.(2) The Influence of the Maximized Budget for One Day in Scenario I. This part aims to analyze the influence of the maximized budget for one day (u) on the optimal restoration scheme. Assume there are three different u ($2200, $3200, $4000) in scenario I, and the optimal sequence schemes of them be shown in Figure 13. Because the total budget is the same, except for the total recovery time and resilience index of the Z, other indicators do not change. The maximized budget for one day directly affects the number of synchronous maintenance teams, and when the teams increase from 2 to 3, the total recovery time is reduced by eight days. However, the resilience index has little change, with an increase of 6.34%. When the number of synchronous teams increases to 4, the total recovery time only shortens by three days and the resilience index only increases by 1.19%. Therefore, we can imply that increasing the synchronous number of maintenance teams blindly does not achieve the desired effects and may lead to the wasting of resources.Figure 13
The sensitivity analysis of the maximized budget for one day in scenario I.(3) The Influence of the Total Budget in Scenario I. This part aims to analyze the influence of the total budget (U) on optimal restoration scheme. Assume there are three different total budget limitations ($40000, $55000, $70000) in scenario I, and the optimal sequence schemes can be shown in Table 6. All the indicators grow with total budget increase. When the number of repaired nodes equals 80% of the total number, the Z can recover to 100%. Examining budgets of $55,000 and $70,000, the E’s recovery ratio and Z’s resilience index increase by 8.57% and 21.07%, respectively, and the total recovery time is reduced by six days. It is worth mentioning that the scheme with $40,000 does not satisfy the resilience constraints, where the purpose is to reveal the sensitivity of the total budget. As the total budget affects the number of repaired nodes directly, when 50% of the total number nodes are repaired, the resilience index only is 0.362. However, when 60% of the total number nodes are repaired, the resilience index and recovery ratio of Z can meet the resilience constraints of objective, showing that the total budget is vital for recovery.Table 6
The sensitivity analysis of the limitation of the total budget in scenario I.
Total budget limitationU40000 ($)55000 ($)70000 ($)The sequences of the repaired nodesA: 24, 98, 9, 10A: 24, 98, 9, 26A: 24, 98, 9, 26, 27, 100B: 97, 25, 99B: 97, 25, 99, 11B: 97, 25, 99, 11, 13C: 118, 7, 117C: 118, 7, 117, 10C: 118, 7, 117, 10, 116The total recovery time (day)141824The percent of repaired nodes50%60%80%The total budget ($)390005200069000The resilience index of theZ0.3620.5030.609The recovery ratio ofZ86.9%92.8%100%The recovery ratio ofE76.91%82.25%89.3%


## 3.2. Scenario II: The Location of the Damaged Stations Is Aggregated in Zhengzhou Metro

### 3.2.1. Scenario Descriptions

We also set up a similar scenario to compare the results with different network structure. Until March 2021, Zhengzhou metro has six lines and 114 stations, shown in Figure14. Zhengzhou Metro is a typical radioactive network with a ring line. Line 5 is a ring line. Twenty stations and four lines also are affected because of a natural disaster. There are eight stations damaged in ring line 5. The repair time distribution of damaged stations is similar to the Nanjing metro, shown in Table 7. It reflects the uncertainty of repair time.Figure 14
Affected zone of the Zhengzhou metro in scenario II.Table 7
The distribution of repair time for damaged stations in scenario II.
IDMeanti¯VarianceδiIDMeanti¯Varianceδi17, 80, 81, 105, 107, 1103120, 22, 41, 106, 108, 1094119, 23, 42, 835118, 436121, 8271The objective of the base scenarios is to maximize theE under the condition that the Z’s resilience index and recovery rate reach 0.5 and 90% at least, respectively. The parameters of the model are same as Table 3.


### 3.2.2. The Optimal Restoration Sequence Scheme in Scenario II

The network size of Zhengzhou and Nanjing metro is similar. The Zhengzhou metro’sZ is smaller than Nanjing metro before a disaster. However, the E is larger than Nanjing. After a disaster, Zhengzhou’s Z only decreased by 36.13%, but the Nanjing metro’s Z decreased by 74.97%. It can prove that the ring line is critical to improve network efficiency. It also can effectively maintain network accessibility after a disaster.The optimal restoration sequence scheme is shown in the green line in Figures15 and 16. We also contrast the optimal sequence scheme with transfer station priority and no transfer station priority. By analysing performance indicators, other indicators are the same except the resilience index. Different from the results of the Nanjing, the resilience index of giving transfer station priority is bigger than no transfer station priority. However, the difference in resilience index between them is slight. The former is increased by 0.45% than the latter. By analysing the position of the damaged transfer station, node 18, node 21, and node 43 are close to unaffected stations. Even transfer stations need more repair time, giving them priority may be bad for early recovery. However, they are close to unaffected stations, the recovery in the latter days is better than the red line.Figure 15
The restoration sequence with different priority in scenario II.Figure 16
The resilience change of restoration sequences with different priority in scenario II.


### 3.2.3. Sensitivity Analysis

(1) The Influence of Damaged Stations’ Repair Time in Scenario II. This part aims to check the sensitivity of damaged stations’ repair time distribution. Assume all damage stations’ repair time equals 4.5 days in scenario II, and the results show in Figure 17. The red line’s resilience index is increased by 2% than the one that gives transfer station priority. In this case, giving transfer station priority is also not the optimal strategy. It can further prove that repairing the transfer station firstly is unsuitable for all situations. Especially in the case of majority transfer stations being far away from unaffected stations.Figure 17
The sensitivity of damaged stations’ repair time distribution in scenario II.(2) The Influence of Different Network Structure Based on Zhengzhou Metro. This part aims to analyze the influence of the damaged stations’ structure. Comparing the damaged stations’ locations of scenario I and II, we find that scenario I’s transfer stations are closer to the unaffected stations. This scenario changes the damaged stations’ location based on the Zhengzhou metro, shown in Figure 18. It is more similar to scenario I than scenario II. Except for the network structure, other model setups are the same as scenario II.Figure 18
Affected zone of the metro in scenario II-I based on the Zhengzhou metro.We contrast the optimal restoration sequence with transfer station priority and no transfer station priority in scenario II-I. The results can be shown in Figures19 and 20. The red line’s resilience index is larger than the green line, increasing by 3.6%. This result is entirely different from scenario II but similar to the scenario I. In this scenario, giving transfer station priority is not the optimal strategy.Figure 19
The optimal restoration sequence with different priority in scenario II-I.Figure 20
The resilience change of restoration sequences with different priority in scenario II-I.


## 3.2.1. Scenario Descriptions

We also set up a similar scenario to compare the results with different network structure. Until March 2021, Zhengzhou metro has six lines and 114 stations, shown in Figure14. Zhengzhou Metro is a typical radioactive network with a ring line. Line 5 is a ring line. Twenty stations and four lines also are affected because of a natural disaster. There are eight stations damaged in ring line 5. The repair time distribution of damaged stations is similar to the Nanjing metro, shown in Table 7. It reflects the uncertainty of repair time.Figure 14
Affected zone of the Zhengzhou metro in scenario II.Table 7
The distribution of repair time for damaged stations in scenario II.
IDMeanti¯VarianceδiIDMeanti¯Varianceδi17, 80, 81, 105, 107, 1103120, 22, 41, 106, 108, 1094119, 23, 42, 835118, 436121, 8271The objective of the base scenarios is to maximize theE under the condition that the Z’s resilience index and recovery rate reach 0.5 and 90% at least, respectively. The parameters of the model are same as Table 3.


## 3.2.2. The Optimal Restoration Sequence Scheme in Scenario II

The network size of Zhengzhou and Nanjing metro is similar. The Zhengzhou metro’sZ is smaller than Nanjing metro before a disaster. However, the E is larger than Nanjing. After a disaster, Zhengzhou’s Z only decreased by 36.13%, but the Nanjing metro’s Z decreased by 74.97%. It can prove that the ring line is critical to improve network efficiency. It also can effectively maintain network accessibility after a disaster.The optimal restoration sequence scheme is shown in the green line in Figures15 and 16. We also contrast the optimal sequence scheme with transfer station priority and no transfer station priority. By analysing performance indicators, other indicators are the same except the resilience index. Different from the results of the Nanjing, the resilience index of giving transfer station priority is bigger than no transfer station priority. However, the difference in resilience index between them is slight. The former is increased by 0.45% than the latter. By analysing the position of the damaged transfer station, node 18, node 21, and node 43 are close to unaffected stations. Even transfer stations need more repair time, giving them priority may be bad for early recovery. However, they are close to unaffected stations, the recovery in the latter days is better than the red line.Figure 15
The restoration sequence with different priority in scenario II.Figure 16
The resilience change of restoration sequences with different priority in scenario II.


## 3.2.3. Sensitivity Analysis

(1) The Influence of Damaged Stations’ Repair Time in Scenario II. This part aims to check the sensitivity of damaged stations’ repair time distribution. Assume all damage stations’ repair time equals 4.5 days in scenario II, and the results show in Figure 17. The red line’s resilience index is increased by 2% than the one that gives transfer station priority. In this case, giving transfer station priority is also not the optimal strategy. It can further prove that repairing the transfer station firstly is unsuitable for all situations. Especially in the case of majority transfer stations being far away from unaffected stations.Figure 17
The sensitivity of damaged stations’ repair time distribution in scenario II.(2) The Influence of Different Network Structure Based on Zhengzhou Metro. This part aims to analyze the influence of the damaged stations’ structure. Comparing the damaged stations’ locations of scenario I and II, we find that scenario I’s transfer stations are closer to the unaffected stations. This scenario changes the damaged stations’ location based on the Zhengzhou metro, shown in Figure 18. It is more similar to scenario I than scenario II. Except for the network structure, other model setups are the same as scenario II.Figure 18
Affected zone of the metro in scenario II-I based on the Zhengzhou metro.We contrast the optimal restoration sequence with transfer station priority and no transfer station priority in scenario II-I. The results can be shown in Figures19 and 20. The red line’s resilience index is larger than the green line, increasing by 3.6%. This result is entirely different from scenario II but similar to the scenario I. In this scenario, giving transfer station priority is not the optimal strategy.Figure 19
The optimal restoration sequence with different priority in scenario II-I.Figure 20
The resilience change of restoration sequences with different priority in scenario II-I.


## 3.3. Scenario III: The Location of the Damaged Stations Is Scattered in Nanjing Metro

### 3.3.1. Scenario Descriptions

Because of man-made attack, some important stations are attacked and cannot operate, the affected stations are shown in Table8 and Figure 21. The percent of the transfer station is 75%. The repair time of each station obeys normal distribution ti∼N5,1, and unit time is day. Because those stations are relatively important and lots of lines are affected, so decision-maker want to make the E and Z’s resilience index maximized under some budget restrictions. In other words, an optimal restoration scheme should make the network recover to a normal state and meet pregiven resilience requirement, the model parameters are shown as Table 9.Table 8
The affected stations in Nanjing metro in scenario III.
IDThe degree of the stationThe affected linesIDThe degree of the stationThe affected lines242, 10531, 101441, 323222642, 34451, 3, S19843, 410823Figure 21
Damaged stations of the Nanjing Metro in scenario III.Table 9
The value of parameters of the model in scenario III.
The meaning of the parameterParameterValueThe pregiven deadline time (day)tr12The limitation of the total budget ($)U42000The resilience index ofZf1MaximizeThe lower limit ofZ’s recovery ratiof2100%The cost of one day’s work for a maintenance team ($)θ1000The maximized budget for one day ($)u4000The set of damaged nodes (ID)Nd2, 5, 14, 23, 26, 44, 98, 108


### 3.3.2. The Optimal Restoration Sequence Scheme in Scenario III

By the analysis of Table9, four maintenance teams can work at the same time. Because the repair time is uncertain, the optimal scheme is not only one. Firstly, if the uncertainty is not considered, the network performance curve of the optimal scheme is shown in Figure 22 (the red line of 4 teams). The restoration plan for the maintenance teams is shown in Figure 23. After 10 days, all the stations are repaired and the network recovers to a normal state. The resilience index of this scheme is maximized, which means the network accessibility recovery more quickly and effectively than all the alternatives.Figure 22
The optimal restoration sequence schemes with different maintenance teams in scenario III.Figure 23
The optimal restoration plan for 4 maintenance teams in scenario III.Because the optimization model also considered the recovery process (resilience index), so the repair sequence is closely related to each node’s repair time. After many simulations, we can get the result of how much the variability of restoration time affects the variability of network accessibility. Taking the repair time uncertainty into account, Figure24 shows the 150 optimal restoration sequence schemes’ network accessibility probability distribution when four teams work synchronously. It can be obtained by executing the program 150 times after randomly giving each node’s repair time according to the distribution function. The network accessibility’s resilience index range is (0.734–0.754). The mean value is 0.745, and the variance is 0.011. Under the budget limitation, the Z’s resilience index and node’s repair time are negatively correlated. The shorter the repair time of nodes, the more nodes are repaired, and the greater the resilience index of network accessibility. The resilience index’s mean value is approximately equal to the resilience index that does not consider repair uncertainty (0.744).Figure 24
Probability distribution of theZ’s resilience index in scenario III (4 teams).Figure25 illustrates the probability distribution of total recovery time. The shortest recovery time is 8 days, and the longest recovery time is 12 days. The average of recovery time is 10.2 days. Because each station’s repair time obeys normal distribution, the total recovery time obeys normal distribution too.Figure 25
Probability distribution of the total recovery time in scenario III (4 teams).


### 3.3.3. Sensitivity Analysis

(1) The Influence of the Maximized Budget for One Day in Scenario III. If prolong the pre-given deadline time to 20 days, Figure 22 also illustrates the different network performance curves of schemes with different synchronous maintenance teams. This comparison is based on the damaged station repair time equal to their mean value, which means it does not consider repair time uncertainty. By contrasting the indicators of Table 10, it can be found that with the increase in the number of maintenance teams, the resilience index becomes bigger. By comparing the 4 teams and 2 teams, the total recovery time shortens by 50% and the resilience index improves by 36.51%. But the total recovery time of 3 teams and 4-2 teams is the same because the multiple teams repairing one station at the same time is not allowed. Interestingly, the stations’ repair sequence does not change. The station with a bigger node degree is repaired earlier. Firstly, the node 44 with degree 5 is repaired, then the set of nodes whose degree are 4 are repaired, the nodes with degree 3 and 2 are subsequently repaired, which means transfer stations with bigger node degree should be given priority in restoration to make network recover quickly and efficiently.Table 10
The sensitive analysis of synchronous maintenance teams in scenario III.
Indicators2 teams3 teams4-2 teams4 teamsThe sequences of the repaired nodesA: 44, 14, 2, 23A: 44, 98, 23A: 44, 2, 23A: 44, 2B: 26, 2, 108B: 26, 5, 108B: 26, 5B: 26, 98, 5, 108C: 14, 5C: 14C: 14, 23D: 98D: 98, 108The percent of repaired nodes100%100%100%100%The total budget ($)40000400004000040000The total recovery time (day)20151510The resilience index ofZ0.5450.6970.7180.744The recovery ratio ofZ100%100%100%100%The recovery ratio ofE100%100%100%100%(2) The Influence of Damaged Stations’ Repair Time in Scenario III. This part aims to check the sensitivity of damaged stations’ repair time distribution. Assume damage transfer stations’ repair time equal 6 days in scenario III, and other damaged stations’ repair time equal 3 days, the results shown in Figure 26. Those schemes’ resilience index is very similar, but the optimal sequence is not based on transfer station priority. The optimal restoration plan shown in Figure 27. In this case, giving transfer station priority is not the optimal strategy. It can prove that damaged stations’ repair time significantly influences the optimal sequence scheme. Repairing the transfer station firstly is unsuitable for all situations. The reason is that the transfer stations need more time to be repaired. If all transfer stations are repaired first, the early stage’s recovery will be prolonged and affect the whole stages’ recovery.Figure 26
The sensitivity of damaged stations’ repair time distribution in scenario III.Figure 27
The optimal restoration plan for 4 maintenance teams in scenario III.


## 3.3.1. Scenario Descriptions

Because of man-made attack, some important stations are attacked and cannot operate, the affected stations are shown in Table8 and Figure 21. The percent of the transfer station is 75%. The repair time of each station obeys normal distribution ti∼N5,1, and unit time is day. Because those stations are relatively important and lots of lines are affected, so decision-maker want to make the E and Z’s resilience index maximized under some budget restrictions. In other words, an optimal restoration scheme should make the network recover to a normal state and meet pregiven resilience requirement, the model parameters are shown as Table 9.Table 8
The affected stations in Nanjing metro in scenario III.
IDThe degree of the stationThe affected linesIDThe degree of the stationThe affected lines242, 10531, 101441, 323222642, 34451, 3, S19843, 410823Figure 21
Damaged stations of the Nanjing Metro in scenario III.Table 9
The value of parameters of the model in scenario III.
The meaning of the parameterParameterValueThe pregiven deadline time (day)tr12The limitation of the total budget ($)U42000The resilience index ofZf1MaximizeThe lower limit ofZ’s recovery ratiof2100%The cost of one day’s work for a maintenance team ($)θ1000The maximized budget for one day ($)u4000The set of damaged nodes (ID)Nd2, 5, 14, 23, 26, 44, 98, 108


## 3.3.2. The Optimal Restoration Sequence Scheme in Scenario III

By the analysis of Table9, four maintenance teams can work at the same time. Because the repair time is uncertain, the optimal scheme is not only one. Firstly, if the uncertainty is not considered, the network performance curve of the optimal scheme is shown in Figure 22 (the red line of 4 teams). The restoration plan for the maintenance teams is shown in Figure 23. After 10 days, all the stations are repaired and the network recovers to a normal state. The resilience index of this scheme is maximized, which means the network accessibility recovery more quickly and effectively than all the alternatives.Figure 22
The optimal restoration sequence schemes with different maintenance teams in scenario III.Figure 23
The optimal restoration plan for 4 maintenance teams in scenario III.Because the optimization model also considered the recovery process (resilience index), so the repair sequence is closely related to each node’s repair time. After many simulations, we can get the result of how much the variability of restoration time affects the variability of network accessibility. Taking the repair time uncertainty into account, Figure24 shows the 150 optimal restoration sequence schemes’ network accessibility probability distribution when four teams work synchronously. It can be obtained by executing the program 150 times after randomly giving each node’s repair time according to the distribution function. The network accessibility’s resilience index range is (0.734–0.754). The mean value is 0.745, and the variance is 0.011. Under the budget limitation, the Z’s resilience index and node’s repair time are negatively correlated. The shorter the repair time of nodes, the more nodes are repaired, and the greater the resilience index of network accessibility. The resilience index’s mean value is approximately equal to the resilience index that does not consider repair uncertainty (0.744).Figure 24
Probability distribution of theZ’s resilience index in scenario III (4 teams).Figure25 illustrates the probability distribution of total recovery time. The shortest recovery time is 8 days, and the longest recovery time is 12 days. The average of recovery time is 10.2 days. Because each station’s repair time obeys normal distribution, the total recovery time obeys normal distribution too.Figure 25
Probability distribution of the total recovery time in scenario III (4 teams).


## 3.3.3. Sensitivity Analysis

(1) The Influence of the Maximized Budget for One Day in Scenario III. If prolong the pre-given deadline time to 20 days, Figure 22 also illustrates the different network performance curves of schemes with different synchronous maintenance teams. This comparison is based on the damaged station repair time equal to their mean value, which means it does not consider repair time uncertainty. By contrasting the indicators of Table 10, it can be found that with the increase in the number of maintenance teams, the resilience index becomes bigger. By comparing the 4 teams and 2 teams, the total recovery time shortens by 50% and the resilience index improves by 36.51%. But the total recovery time of 3 teams and 4-2 teams is the same because the multiple teams repairing one station at the same time is not allowed. Interestingly, the stations’ repair sequence does not change. The station with a bigger node degree is repaired earlier. Firstly, the node 44 with degree 5 is repaired, then the set of nodes whose degree are 4 are repaired, the nodes with degree 3 and 2 are subsequently repaired, which means transfer stations with bigger node degree should be given priority in restoration to make network recover quickly and efficiently.Table 10
The sensitive analysis of synchronous maintenance teams in scenario III.
Indicators2 teams3 teams4-2 teams4 teamsThe sequences of the repaired nodesA: 44, 14, 2, 23A: 44, 98, 23A: 44, 2, 23A: 44, 2B: 26, 2, 108B: 26, 5, 108B: 26, 5B: 26, 98, 5, 108C: 14, 5C: 14C: 14, 23D: 98D: 98, 108The percent of repaired nodes100%100%100%100%The total budget ($)40000400004000040000The total recovery time (day)20151510The resilience index ofZ0.5450.6970.7180.744The recovery ratio ofZ100%100%100%100%The recovery ratio ofE100%100%100%100%(2) The Influence of Damaged Stations’ Repair Time in Scenario III. This part aims to check the sensitivity of damaged stations’ repair time distribution. Assume damage transfer stations’ repair time equal 6 days in scenario III, and other damaged stations’ repair time equal 3 days, the results shown in Figure 26. Those schemes’ resilience index is very similar, but the optimal sequence is not based on transfer station priority. The optimal restoration plan shown in Figure 27. In this case, giving transfer station priority is not the optimal strategy. It can prove that damaged stations’ repair time significantly influences the optimal sequence scheme. Repairing the transfer station firstly is unsuitable for all situations. The reason is that the transfer stations need more time to be repaired. If all transfer stations are repaired first, the early stage’s recovery will be prolonged and affect the whole stages’ recovery.Figure 26
The sensitivity of damaged stations’ repair time distribution in scenario III.Figure 27
The optimal restoration plan for 4 maintenance teams in scenario III.


## 4. Conclusions and Recommendations

Given the ever-increasing concerns for metro network safety, based on resilience evaluation, a multi-objective restoration sequence optimization method is proposed. Taking budget limitations and repair time uncertainty into account, combined with the network topology characteristics, the optimal restoration sequence scheme aims to maximizeE, when the Z satisfies pregiven resilience requirements. The resilience requirements include the recovery ratio and the resilience index that can reflect the network performance change in process. The proposed method is applied to the Nanjing and Zhengzhou Metro network. The benefits of the proposed model are as follows:(1)
The proposed method focuses on network topology characteristics and has a good handle on the node degree, network accessibility, and global average efficiency. The model presents a flexible framework. It can integrate multiple goals. The objectives can be set flexibly to the decision-makers preference. In the early emergency stage, decision-makers often want the network performance to recover to an acceptable level as early as possible, and they can change objectives based on the current recovery results after this objective is achieved.(2)
Unlike other traditional restoration sequence optimization models, the proposed method combines the resilience evaluation and optimization problem, ensuring that network performance is optimal in both process and result. Assuming the damaged stations’ repair time obeys different normal distributions and comparing the optimal sequence under different repair times, we can find that damaged stations’ repair time will impact the optimal restoration sequence. In some cases, the result is entirely different from the result based on importance ranking. More detailed conclusions are as follows:(1)
By comparing the Zhengzhou metro and Nanjing metro, the performance of a ring network is more excellent than a radial network under the same network attack. After a similar disaster, Zhengzhou’sZ decreased by 36.13%, but the Nanjing metro’s Z decreased by 74.97%. It proves that a ring network is more robust than a radial network.(2)
Many studies prove that transfer stations should be given priority in the restoration process. This conclusion may be invalid in the following scenario.When damaged stations’ location is relatively centralized, giving transfer station priority is not always the optimal strategy, especially when most transfer stations are far away from unaffected stations and they need more time to be repaired. It can be proved by Sections3.1.2 and 3.2.3(2). Because even if they are repaired, they cannot play the role of network connection. The network accessibility recovery is prolonged in the early stage. It will affect the network accessibility resilience index because the metro resilience focuses on final results and the recovery process.In scenario I and II-I, the repair time of transfer stations is longer than non-transfer stations. They need more time to be repaired, so the network’s recovery is slow in the early time. By analysing the transfer stations’ location, even they are repaired, they cannot connect with other no-damaged stations. Thus, giving them priority has little influence on the whole network recovery. As time goes on, alternative paths will exist in the damaged network. Other nodes may replace the function of transfer station. Thus, even without giving priority to transfer stations,Z can continue to grow with accepted level. It can further prove that giving transfer station priority is not always the optimal strategy.In the case of the location of the damaged stations is scattered, for example in the scenario III, if the damaged stations’ repair time are the same, station with a bigger node degree should be given priority to be repaired. Because those damaged transfer stations are very close to unaffected stations, so if they are repaired, they can immediately play the role of connecting other nodes. However, if the damaged transfer stations repair time are far longer than other damaged stations, the advantage of giving the transfer stations priority becomes smaller. It can be proved by Section3.3.3(2).Thus, the transfer station’s location and repair time together affect the optimal sequence scheme. In practice, we should shorten the repair time of the transfer station as much as possible. It can make the network recovery faster. But if the transfer stations’ repair time cannot change, the stations connected to the unaffected station need to be repaired firstly, even those stations have smaller node degree, then the stations with bigger node degree and connect with unaffected or repaired stations should be given priority, which can make the recovery more effectively.(3)
According to the sensitivity analysis, the total budget is more sensitive than the input of the one-day budget in the entire restoration phase. However, in the emergency phase, increasing the number of synchronous maintenance teams can effectively shorten recovery time. For example, in Section3.3.2, when the number of maintenance teams increases from 2 to 4, the recovery time was cut by 42.31%. After the Z recovered to an improved level, increasing the number of synchronous maintenance teams does not result in significant change. For example, in Section 3.3.1, when the number of maintenance teams rises from 2 to 3, the resilience index only improves by 3.51%, and the total recovery time shorten by 8.57%. In summary, according to the available resources, a reasonable resource input plan should be set up to avoid delays or the wasting of resources.The scheduling restoration is a complex process that may involve many factors, the paper only focuses on network topology characteristics, and the global average efficiency ignores the difference of the edge’s length. Except for the topology characteristics, there are other critical operational metrics, such as passengers demand, network flow, travel cost, etc. Those metrics can be integrated into the model in future work. For example, passengers demand and flow can be used to reflect the network performance. Due to the variability of passenger flow with time, the optimal restoration scheme may change with time and different form this paper proposed. Although the proposed model can provide a near-optimal scheme in the case study, not an exact solver, the restoration strategy can be used in similar scenarios. Finally, the applicability of restoration strategy needs to be further analyzed. For example, the damaged station’s distribution is relative scatter. Using the proposed method in different scenarios to generate corresponding restoration strategies and extend them to other similar scenarios, which is very meaningful to enhance the network resilience facing disruptions.



---

*Source: 8595356-2022-03-14.xml*