Resilience Assessment and Optimization for Urban Rail Transit Networks: A Case Study of Beijing Subway Network

With the rapid development of urban rail transit, huge subway systems have been built, which is the best choice for people due to the efficiency, safety, and punctuality. Therefore, the ability of subway systems to resist failures especially interruptions has attracted the attention of operators. In the paper, based on the graph theory, a resilience assessment method is proposed to quantitatively measure the performance and recovery rapidity within unifying metrics and models. We represent the subway network with an undirected graph where the subway stations are described using the nodes whereas tracks are demonstrated with the edges. The performance evaluation of a subway network is implemented based on the assessment of passenger flow and topological structure of the network, where weighted degrees and the weighted sum of the reasonable passageway to the other nodes are considered. The resilience of a subway network can be associated to the network performance loss triangle over the relevant timeline from the occurrence of a random or intentional disruption to full recovery. The Beijing Subway is taken as the example to perform the proposed approach which is verified through the numerical results in the paper. Following the resilience evaluation, a structure optimization model with a computational algorithm is proposed. Based on the genetic algorithm, we achieved the solution results of the simplified network of the Beijing Subway. Several interesting conclusions are drawn from the results.

SECTION I. Introduction

As a safer, more eco-friendly, faster and cheaper way, urban rail transit is becoming a popular mode of public transportation, which has promoted the rapid development of subway systems; here, subway refers to urban rail transit with exclusive right-of-way, whether it is underground, at grade or elevated. The operation management of subway systems has entered an era of network-based operation. For example, Beijing Subway network has 22 lines, 391 stations and 636.8 km of route length, and the annual ridership was 3.85 billion delivered in 2018. Therefore, once an accident happens due to hardware/software failures, operator errors, malicious attacks, and natural disasters, the capacity and operation efficiency of one single line, even the whole subway network could be badly affected. On September 27, 2011, a rear-end collision caused by signal failure occurred in Shanghai Subway Line 10, and 9 stations from Hongqiao Road Station to Tiantong Road Station were shut down over six hours with 271 passengers hurt and over five hundred people’s travel affected. On July 6, 2014, a fire between Xizhimen Station and Dazhongsi Station led to the shutdown of the whole Beijing Subway Line 13, passengers were detained on the train and the transportation ability of the whole subway network was severely affected. Therefore, quantitative assessment on the performance loss of a subway network under different accidents is critical to describe the ability to resist emergency events.

Building a system index of subway systems under different scenarios is the key to implement the quantitative assessment, robustness, vulnerability, reliability and resilience are respectively taken as the metric of a subway system in the past decades [1]–​[4]. Generally speaking, a subway network can be mapped into topological graph to simplify the subway tunnels as edges and the subway stations as nodes. Von Ferber et al. [5] summarized four types of topological maps, L-space type, B-space type, P-space type and C-space type to analyze different urban transit networks in fourteen cities around the world. In general, the subway networks can be described by two topological methods: Space L and Space P. In the model of Space L, the nodes represent stations and the edges between the two nodes only exit if they are consecutive stations. However, much different from what is in Space L, the edges exist between any two stations in the same route, so that all the nodes of a specific route are connected directly in Space P model. For the intuitive and simple definitions in relation to transportation networks, L-space model is chosen to analyze the subway networks among all these models. Topological analysis consists of not only node and edge, but also degree, path length, diameter of network, etc., which can provide analysis in the aspect of network’s topological structure [4], [6]–​[8]. Scale-free networks have a high robustness index under random attacks but a low robustness index under intentional attacks [3], [9], [10]. Albert et al. [9] quantitatively analyzed the robustness of subway networks in the event of an accident, where robustness is expressed in terms of the residual network connectivity after the disruption of nodes in the network. Derrible and Kennedy [10] analyzed the complexity and robustness of subway networks using two particular concepts: scale-free patterns and small-worlds, and the Tokyo Metro network was studied as a real-world example for large networks analysis. Crucitti et al. [3] also studied the robustness of two types of large-scale networks, i.e., a random network and scale-free network, for the performance of network connectivity. Meanwhile, a similar analysis of the robustness of subway networks was also reported by Zhang et al. [4] and Yang et al. [11], both research are analyzed based on the topological structure of subway networks. The above works reveal the topological characteristics of subway networks, in the meantime, applications to the robustness of subway networks and recommendations for increasing the robustness of subway networks are provided.

Vulnerability is a concept to evaluate performance loss in case of failures. Reducing the vulnerability of subway networks has been studied as a direct method to minimize the impact of disruptions. Holmgren [12] defined vulnerability as a collection of properties of an infrastructure system that may weaken or limit its ability to maintain its intended function when exposed to threats and hazards. Berdica [13] proposed the concept of vulnerability of road transportation systems which is from a safety point of view and taken as a problem of an insufficient level of service. In transportation networks, vulnerability is commonly measured based on the complement of reliability [13], [14]. Deng et al. [6] used the Space L model to analyze the topological vulnerability of the Nanjing Subway network in China which is based on topological characteristics and functional properties of subway networks.

Additionally, performance recovery has attracted many researchers, which demonstrates how and how long the system performance can get back to an acceptable level. The rapid recovery of a network’s connectivity from a disrupted state to the normal state is a key concern among engineers [15].

“Resilience” can provide an appropriate solution to illustrate the recovery period when performing the safety evaluation on a network system [16], [17]. The concept of resilience engineering was proposed by Hollnagel et al. [18], where resilience is defined as the ability of a system to return to a stable state following a strong perturbation caused by failure, disaster or attack, which is applied in different systems, such as the resilience evaluation of ecosystems [19], social-ecological systems [20], [21], psychosocial resilience [22], resilient topology structures of computer networks [23], [24]. There are some studies on resilience of transportation networks [25]–​[27]. Jin et al. [25] focused on multiple networks, which enhanced the resilience of subway networks by the integration with bus services. Bruyelle et al. [27] identifies critical systems and proposes improvements to the design of subway coaches, in order to improve the management of the emergency situation and assist the evacuation and rescue to passengers. In the context of subway systems, the resilience could be measured by the performance loss triangle for disruption responses. When limited nodes or edges are disrupted, a resilient network has largest component size and global connectivity with accepted routes loss. One measure of network connectivity is given by the standard graph-theoretic k-connectivity definition: a graph is k-connected if any set of k1 node removals does not disconnect the graph. However, subway operation managers need to be able to provide alternate route to reroute passengers [28]. The resilience of a system is quantified by relating it to a resilience loss triangle represented by the difference between a normal performance evolution curve and a disrupted performance curve along with the time duration of disruption [29].

Quantitative assessment for network resilience can also be applied to optimize the subway network by promoting the resilience as a preventive approach. Two preventive methods have been approached. The first method is the edge addition method [30], where edges are added to the network to enhance network resilience. The second method is the edge rewiring method [31], where new edges are introduced by swapping a subset of existing edges. For some networks like power grids and the Internet sensor networks, the edge rewiring method might be preferable due to lower maintenance and cost. However, it is nearly impossible to apply the edge rewiring method to subway networks which can increase the construction cost and limit the ridership. So the edge addition method is chosen to improve the resilience of the subway network. There can be many researchers studying the passenger flow in urban rail transit networks and passenger flow is a very important factor for the urban rail construction [32]–​[35]. To the best of our knowledge, resilience analysis for subway systems considering passenger flow, has been hardly studied in the previous works. In the paper, a resilience-based assessment approach is proposed based on the graph theory in order to evaluate the performance of subway networks under emergency accidents.

This paper provides a general resilience assessment method for the resilience analysis of subway networks that identifies the critical stations affecting the network most when disrupted. Meanwhile, based on the resilience assessment method the edge addition method is chosen to improve the resilience of the subway network and some good strategies are concluded. Several concepts and models of the subway network are introduced and the framework is as followed:

1. Mapping the subway network into topological graph;

2. Introducing and defining performance of the subway network;

3. Developing a resilience assessment method;

4. Optimizing the subway network based on the resilience assessment method.

The rest of this paper is organized as followed. In Section II, we describe the problem and provide some definitions. Then, the solution algorithm for assessing the resilience of subway networks is provided. In Section III, some topological characteristics of Beijing Subway network are calculated and the resilience assessment method is applied to the Beijing Subway network. In Section IV, we propose the structure optimization model of subway networks and strategies are obtained based on Bejing Subway network. Finally, conclusions are addressed in Section V.

SECTION II. Methodology

Subway networks in many metropolitan cities around the word are generally in large scale. For example, the Beijing Subway network and Tokyo Subway network currently have 391 stations and 285 stations (a multi-line exchange station is regarded as a single station) respectively. The subway network as a main mode of transportation is responsible for people’s daily travelling. However, disruptions in the network caused by failure can lead to partial or even complete loss of function, which affect not only people’s daily activity but also the social economy. In this section, some parameters are analyzed including topological characteristics and passenger flow, then the procedure for calculating the performance of the subway network is presented and the resilience assessment method is modeled.

A. Topological Mapping of Subway Networks

The subway network is a kind of complex networks which are typically studied in representation of topological graphs where subway stations are represented by nodes whereas edges correspond to tunnels that exist between stations. For modeling transportation networks, there can be several types of topological maps based on the application of nodes and edges among nodes. Referring to Von Ferber et al. [5], L-space type of topological map is chosen for analyzing the subway network.

A topological graph for a subway network can be expressed by a vector $G$ :

$$\begin{equation*} G=[V,E]. \tag{1}\end{equation*}$$ where $V$ is the set of nodes representing the stations in the subway network and $E$ is the set of edges representing the tracks between adjacent stations. The topological graph can be represented by a matrix, namely adjacent matrix $A(n,n)$ . If there is an edge between node i and node j (node i and node j are connected directly), $A(i,j)=1$ ; otherwise, $A(i,j)$ equals to infinity. Under normal circumstances, if there is a subway train traveling from station $i$ to station $j$ , there is also another train traveling from station $j$ to station $i$ along the same route [36]. As subway systems generally have two-way traffic, the urban rail transit network is viewed as an undirected graph. Also the distance between different stations and departure frequency are not concerned as represented frequently in researches for analyzing transportation system.

Thus, to simplify the calculation we can get the lower triangular matrix:

$$\begin{equation*}A_{tril}=tril(A). \tag{2}\end{equation*}$$

Due to the subway network considered as undirected, the connecting sequence of nodes in the subway network can be expressed by the lower triangular matrix $A_{tril}$ . Under the help of the conversion, the work of calculation can decrease to a half level compared to $A(n,n)$ .

For the topology of a subway network, the degree of a node $D(i)$ stands for the number of nodes that connected directly to this node. The average node degree $D^{*}$ is defined as the average degree of all the nodes in the network:

$$\begin{equation*}D^{*}=\frac {\sum D(i)}{N}. \tag{3}\end{equation*}$$

The minimum number of edges that need to be passed through from one node to another is defined as the shortest path length between these two nodes. There are three classical algorithms to calculate the path length $d_{i,j}$ , Dijkstra’s algorithm, Bellman-Ford algorithm, Floyd algorithm [37], [38]. The average path length $L$ is defined as the average shortest path length for all nodes in the network:

$$\begin{equation*}L=\frac {\sum _{i\neq j} d_{ij}}{N(N-1)}. \tag{4}\end{equation*}$$

The diameter of the network $L^{*}$ is defined as the maximum path length $d_{ij}$ among all pair of nodes. By using the above notation, the basic connection status can be characterized. The foundation function of the subway systems is to carry passengers from one station to another station. For travelling by subway in the city, people care not only about the number of tracks from their origins to destinations but also routes diversity that how many routes they can choose.

Meanwhile, for the large-scale subway network, the connectivity from one station to another should be a key criterion for subway operation. Once a station is disrupted due to some unexpected events, the connectivity of the network will and must decrease to some degree. At the same time the optimal routes for passengers should be adjusted. Then the efficient way for passengers to reach their destinations is to take another passageway connecting the departure station and destination station. Maybe the quick repair of the disrupted station can also satisfy the passengers, but it depends on many factors such as limited human, material and financial resources which are difficult to be normalized even some disruptions can last for a very long time. Therefore, the performance of the network depends largely on the node connectivity. Hence, before evaluating the network performance, the number of reasonable passageways between each two stations should be characterized first.

Definition 1:

If a path set includes paths without any common edges with other paths between any two nodes and each path in this set is the shortest in that case, the set is defined as a reasonable passageway set between the two nodes and such paths are called reasonable passageways.

A network with 7 nodes and 11 edges is shown in Fig. 1, where the numbers in the circle are the labels of the nodes, and numbers over the edges are the labels of edges. We have seeked a reasonable passageway set between node 2 and node 5 including passageway {3}, {4-7} and {2-6-9}, where the numbers in the brackets are labels of the edges. We note that path {4-8-9} is not a passageway in this reasonable passageway set, because a common edge {4} consists in the passageway {4-7} and a common edge {9} in passageway {2-6-9}. However, path {4-8-9} may belong to another reasonable passageway with other path together.

FIGURE 1.

Example of a simple network.

Considering a subway network of a large city with much larger dimension, an effective solution to obtain reasonable passageways is necessary, which is demonstrated as follows.

With the given network $G=[V,E]$ , $s_{k}(i,j)$ is defined as the $k$ th passageway between node $i$ and $j$ . The stations are numbered from 1 to $n$ and $A(i,j)$ is initialized to be $zeros(n,n)$ .

The procedure for calculating the number of reasonable passageways can be described as follows:

The number of reasonable passageways between each pair of nodes is listed in the following matrix. We consider the network is undirected, so the matrix should be symmetrical. We only give the lower block here.

$$\begin{equation*} \left [{ \begin{array}{ccccccc} 0&\quad 0&\quad 0&\quad 0&\quad 0&\quad 0&\quad 0 \\ 1&\quad 0&\quad 0&\quad 0&\quad 0&\quad 0&\quad 0\\ 1&\quad 3&\quad 0&\quad 0&\quad 0&\quad 0&\quad 0\\ 1&\quad 3&\quad 3&\quad 0&\quad 0&\quad 0&\quad 0\\ 1&\quad 3&\quad 3&\quad 3&\quad 0&\quad 0&\quad 0\\ 1&\quad 3&\quad 3&\quad 3&\quad 3&\quad 0&\quad 0\\ 1&\quad 2&\quad 2&\quad 2&\quad 2&\quad 2&\quad 0\\ \end{array} }\right]\end{equation*}$$

B. Calculating Passenger Flow of Each Station

As an important factor for transportation systems, passenger flow attracts a lot of attention. The short-term passenger flow forecasting technology becomes more and more significant in the field of subway systems. With the volume of passenger flow increasing, effective predicting method for passenger flow data can not only ensure the safe operation of urban rail transit system but also make the evacuation more efficient in case of disruptions. In our analysis, to evaluate the resilience of subway systems, the method to predict passenger flow of each station on daily ridership is proposed based on population distribution.

We can easily get the daily ridership of the subway system on the official website, but it’s almost impossible to obtain the passenger flow data of each station like Shanghai Metro and Beijing Subway. In the paper, we can estimate passenger flow of each station using population distribution. We assume the passenger flow of each station is assessed based on the logic of the special interaction, which means the passenger flow of each station is related to the population around the stations. The key point to this issue is how to delineate the served area of the subway system. In some previous research, the served area is defined based on walking distance [39]–​[41]. The served area is considered covering places within 2km (about twenty minutes walking for adult).

To estimate the passenger flow of each station, the population within the served area is considered as the weight. First, calculate the population in the served area based on the density and the area; then the population $M_{i}$ is in the served area is calculated:

$$\begin{equation*} M_{i}=\beta *\pi *2^{2}. \tag{5}\end{equation*}$$ where $\beta$ is the density of the served area. Second, the total volume of the population in Line L is calculated by summing $M_{i}$ in Line L: $$\begin{equation*} M_{L}=\sum _{i\in L}M_{i}. \tag{6}\end{equation*}$$ where $M_{i}$ is the population around station $i$ , $M_{L}$ is the population around Subway Line L in the served area.

Then, the passenger flow of station $i$ can be expressed as:

$$\begin{equation*} N_{i}=\frac {M_{i}}{M_{L}}*\sum _{i\in L}f_{i}. \tag{7}\end{equation*}$$ where $\sum _{i\in L}f_{i}$ stands for the passenger flow of Subway Line L; $N_{i}$ stands for the passenger flow of station $i$ .

After the passenger flow of each station is obtained, we focus on the performance of the subway network. Common interruptions in subway systems include rear-end collisions, leaks, fires, signal problems and terrorist attacks. During the recovery procedure, the subway station is closed to the public. So the shutting down of subway stations can not only affects people’s travel, but also leads to financial loss of the city. Based on the topological characteristics and passenger flow, the performance evaluation model will be presented next.

C. Performance of Subway Networks

The performance of the subway networks can be classified into three parts. The first part is to obtain the reasonable passageways as introduced above. The second part is to calculate the degree of each node, which we can get from the topological graph of the subway network. In complex network theory, if one node has a higher degree, it indicates that the node is more important. The last part is to get the passenger flow of each station. In view of the fact that passenger flow is important for the performance of subway systems, we take passenger flow of each node as a weight of performance. We consider the passenger flow of the whole network divided by that of station $i$ is the weight of node $i$ . This is:

$$\begin{align*} f=&\sum _{i=1}^{i-n}f_{i}. \tag{8}\\ u_{i}=&\frac {f_{i}}{f},\quad i\in n. \tag{9}\end{align*}$$ where $f_{i}$ is the passenger flow for node $i$ , $f$ is the passenger flow of the whole network and $u_{i}$ is the weight of node $i$ .

When we calculate the performance of a node, its connected nodes do not include itself. Thus, the self-exhausted weight of a node, $v_{i}$ is:

$$\begin{equation*} v_{i}=\frac {f_{i}}{f-f_{i}},\quad i\in n. \tag{10}\end{equation*}$$

The performance of a node can be evaluated by the weighted number of reasonable passageways to all the other nodes in the networks. Therefore, we also need to consider the weight of degree, which is determined by the number of direct links connecting with the node $i$ .

Definition 2:

The performance of a node in a subway network is defined as the weighted degree and the weighted sum of the numbers of reasonable passageways to all the other nodes in the network.

The calculation formula is:

$$\begin{align*} p_{i}=D(i)*\sum v_{i}*\sum \left({{\frac {s_{k}(i,j)}{d_{ij}^{k}}*rel_{k}(i,j)}}\right),\quad j\in n,~j\neq i. \\ \tag{11}\end{align*}$$ where $s_{k}^{i,j}$ is the $kth$ reasonable passageway between node $i$ and node $j$ ; $d_{ij}^{k}$ is length of the $kth$ reasonable passageway; $rel_{k}(i,j)$ is the reliability of the $kth$ reasonable passageway between node $i$ and node $j$ ; let $s_{k}(i,j)$ be 1 if the kth reasonable passageway exists; and 0 otherwise. $D(i)$ is the degree of node $i$ ; $p_{i}$ is the performance of node $i$ . The inverse of path length $d_{ij}^{k}$ essentially means the connectivity efficiency between nodes $i$ and $j$ in a network.

Definition 3:

The performance of a subway network is defined as the weighted sum of the performance of all nodes:

$$\begin{equation*} P=\sum _{i=1}^{i=n}u_{i}*p_{i}. \tag{12}\end{equation*}$$ where $P$ is the performance of the whole network.

Generally speaking, the performance of a complex subway network can be affected not only by the failure of stations (nodes) but also by the failure of tracks (edges). In the paper we consider the failure of stations preferentially but not the tracks. There are two reasons: one is that the stations is exposed to passengers and thus passengers care more about stations; another is that the research on the failure of nodes is often considered in L-space type model for transportation networks [4], [11].

There can be two types failure of a subway station. One type is random failure which is caused by nature disasters (rainstorm, lightning, etc.), malfunction of devices or incorrect operations. The probability of this kind of failure can be considered as the same for all the stations in the subway network. The second type is intentional failure, which is always caused by terrorist’s behavior on purpose. For this type of failure, the relatively important stations (multi-line exchange stations and stations with large passenger flow) are always targeted. For the performance analysis, the assessment of the network in the scenario of one node disrupted can be modeled by deleting the node from the topological graph. To analyze both the random failure type and the intentional failure type, the nodes are deleted from the topological graph one by one in spite of huge amount of calculations.

The performance of the disrupted network can be recalculated by the changed topological structure and passenger flow. After one station disrupted, the passenger flow of the disrupted station is assumed to be distributed equally to the directly connected station(s). Hence, the formula can be described as:

$$\begin{equation*} P^{i}=\sum u_{i}^{i}*p_{i}^{i},\quad i\in n. \tag{13}\end{equation*}$$ where $u_{i}^{i}$ is the recalculated weight of node $i$ after station $i$ is deleted from the topological graph; $p_{i}^{i}$ is the recalculated performance of station $i$ after node $i$ is deleted from the topological graph; $p^{i}$ is the performance of the disrupted network after station $i$ is deleted. For the node removal strategy, only one node is deleted at one time.

D. Resilience of Subway Networks

The system resilience is the ability of the system to withstand the impact of disastrous events on the system performance and also the ability of the system to recovery to an accepted performance level. This resilience concept is adapted for assessing the resilience of subway networks. Different from some natural systems, the recovery procedure of subway systems depends mainly on behaviors of social units such as the government and organizations. Three parts are considered in the resilience concept of subway system as shown in Fig. 2: before the disruption, during the disruption, after the disruption (recovery).

FIGURE 2.

Resilience triangle model.

Before the disruption, attention should be payed to decrease probability of disruption occurrence. The subway system should be designed in a way that they are maximally reliable to resist random failures. For the intentional failures, the government and the subway organizations should release comprehensive policies and behavior to improve the security of subway systems.

During the disruption, the ability of the subway system to withstand the impacts of disruptions on performance should be increased in the aspect of the topological structure, which can improve the robustness and reduce the impacts of the disruption on the system performance.

After the disruption, the performance of the system will fall to some extent, which will impact the efficiency of the subway network. Recovery strategies by the organizations should be implemented as fast as possible, people have to reroute to their destinations. Usually the very procedure induces much costs on both time and money.

Our research aims to assess the resilience of the subway system itself to withstand the impacts of disruptions, but not formulating policies. After the performance of the subway network has been obtained, the resilience of the network can be evaluated. The resilience of the subway network as discussed in the paper is defined as the remained performance level after node disruptions and the ability of the network to recover to an acceptable level with appropriate reconstruction process. This definition refers to the concept of the “resilience triangle ”proposed by Bruneau et al. [17]. The resilience triangle model is displayed in Fig. 2, the loss of resilience is printed in red. The vertical axis stands for the performance of the network, whereas the horizontal axis stands for the time $t$ . A disruption event happens at time $t_{0}$ , with the specific measures applicated, the performance of the network can be recovered to normal mode by time $t_{1}$ . Then, the resilience triangle lose is illustrated by the area that the difference between normal mode performance and the degraded performance from the disruption time $t_{0}$ to the recovery time $t_{1}$ . Thus, the area below the performance line after disruption from time $t_{0}$ to time $t_{1}$ represents the remained resilience. Hence, based on the resilience triangle theory, a general metric of resilience assessment for the subway network is proposed. For the resilience of subway networks, we can also applicate this model that the resilience is the ratio of the remained performance (the area covered by the disrupted performance curve) with the normal performance (the area covered by the undisrupted curve). Hence, the resilience index can be expressed as:

$$\begin{equation*} R_{i}=\frac {\int _{t_{0}}^{t+t_{i}}P^{i}dt}{\int _{t_{0}}^{t+t_{i}}Pdt},\quad i \in n. \tag{14}\end{equation*}$$ where $P^{i}$ stands for the performance of the remaining network after node $i$ removed; $P$ stands for the performance of the remaining network before the interruption; $R_{i}$ stands for the resilience of the network in the scenario that node $i$ is disrupted.

The performance during the recovery period may fluctuate in some systems such as ecosystems, for it’s a gradual process. However, for the subway network, once a disruption happens, the disrupted station will be shut down until it is fully repaired. Thus the performance of the subway systems always remain the same during the recovering process.

We assume that during the recovery procedure the performance remain the same level as the interruption happens and after the recovery procedure the performance recovers to the normal level immediately. This assumption can be changed and different recovery curve can be applied without affecting the resilience assessment model we proposed.

SECTION III. Application: Beijing Subway Network

The Beijing Subway system opened in 1969 and is the oldest subway system in mainland China, which has experienced rapid expansion since 2002, as only two lines were in service before then. The existing network still cannot adequately meet the city’s mass transit needs. Beijing Subway’s extensive expansion plans call for 999 km (621 mi) of lines serving a projected 18.5 million trips every day by 2021. The most recent expansion, which included a one stop extension of Fangshan Line and the opening of Xijiao Line, S1 Line and Yanfang Line came into effect on December 30, 2017. There are currently over 300 km of subway under construction in Beijing, including six new fully automated lines totaling up to 300 km (190 mi) in length using domestically developed communications-based train control systems, which could potentially create the longest fully automated subway network in the world. The necessity of a detailed resilience analysis for such an important and complex network is quite obvious from this perspective of view.

A. Topological Characteristics of the Beijing Subway

A typical L-space topological map representing Beijing Subway network is shown in Fig. 3. The nodes represent stations and the edges linking the nodes are subway lines. The topological map consists of 292 nodes and 335 edges. Based on the topological structure of the Beijing Subway network, the characteristics of the network like average node degree $D^{*}$ , average path length $L$ and diameter of the network $L^{*}$ is calculated by the popular path searching algorithm proposed by Dijkstra’s algorithm [37]. These typical characteristics are displayed in Table 1.

TABLE 1 Topological Characteristics of Beijing Subway Network

FIGURE 3.

Topological map of Beijing Subway network.

The value of degree ranges from 1 to 5 that is very small. The average node degree is equal to 2.284, which indicates that every station is connected to 2.284 stations directly on average. Fig. 4 displays the typical degree and the degree distribution of the Beijing Subway network. There are 15 stations with the degree of 1, which indicates that they are the ends of a subway line. The degree equal to 2 always characterizes an intermediate normal station where only one subway line passes through. However, in some spacial cases, it can be connecting stations of two lines and also it is both the ends of these two lines, such as Guogongzhuang Station from both Beijing Subway Line 9 and Fangshan Line, Yancuneast Station from both Fangshan Line and Yanfang Line. The value of degree larger than two indicates there exist at least two subway lines passing through the station. In total, nearly 76% stations are normal stations with the degree of two and more than 18% stations are multi-line exchange stations with the degree over 2. Among all the stations in Beijing Subway network, Xizhimen Station is unique with a degree of 5 alone, due to three lines passing through.

FIGURE 4.

Degree of nodes in Beijing Subway network.

The average path length $L$ is 15.4879 as shown in Table 1, which means when people travelling by Beijing Subway, 15.4879 stations should be passed though from their origins to destinations on average. The diameter of the Beijing Subway network $L^{*}$ is equal to 46, which means the longest of all the calculated shortest paths in the network. It is the shortest distance between the two most distant nodes in the network, which are Yancun East Station in Fangshan Line and Fengbo Station in Line 15. From the topological characteristics analyzed above, the Beijing Subway networks is proved to be a complex network and have an intensive connectivity indeed.

B. Passenger Flow of Each Station in Beijing Subway Network

The Beijing Subway network is shown in Fig. 3, which consists of 292 stations (multi-line exchange stations are counted only once) and 335 tracks between stations by January 14nd, 2018. S1 Line and Xijiao Line are not included. Because S1 Line is not connected to any other line in the network and for Xijiao Line we cannot get the passenger flow data for the whole line officially. From the official website we can obtained the passenger flow data for each line but not for each station.

Considering the daily ridership and demand fluctuation, the estimated passenger flow should be distinguished based on the days of the week. We obtained the real daily ridership of each subway line for two weeks (1/1/2018-1/14/2018). In this paper we calculate the average ridership for weekdays and weekends, which are shown as two bars in Fig. 5. The blue bar stands for the passenger flow of each subway line per weekend on average, whereas the red bar stands for the passenger flow of each subway line per weekday averagely.

FIGURE 5.

Daily ridership of Beijing Subway Lines.

Both the blue bar and the red bar fluctuate hugely from different subway lines, however the same trend occurred according to different lines. Subway Line 10 has the maximum passenger flow through the week and the passenger flow on weekday nearly twice as much as that on weekend obtained by the curve in Fig. 5, which indicates Subway Line 10 is the most important line in the Beijing Subway network for people’s commuting. For comparison, the passenger flow for the Airport Line remains nearly the same no matter on weekday or weekend, which keeps a relative low amount of passenger flow. Note that the Airport Line operates from Dongzhimen Station to Sanyuanqiao Station, then the airport, also the fees are hugely high compared to other subway lines. Therefore, people usually choose the Airport Line under the circumstances that their destinations are the airport or they want to go downtown from the airport. Hence, the operation purpose and the function of the subway lines can be reflected by the difference of passenger flow. From the analysis of the passenger flow, passenger flow is proved to be an indispensable factor for the performance of subway networks and it is necessary to assess the performance for subway networks on weekday and weekend respectively.

Once the passenger flow data of each line is obtained, how to get the population density around each station is the key of the problem. Considering the land use and station distribution in Beijing, places within 2 km (twenty-minutes walk) to the stations are assumed as the subway stations’ served areas. As illustrated in Fig. 6, we generate a two-kilometer buffer zone and Thiessen polygons are applied to divide the served area into separate zones by stations. Then we calculate the population around each station within its serving area using the Sixth National Population Census.

FIGURE 6.

Density of population in Beijing.

Subway stations are often classified into two types based on their roles in the network: multi-line exchange stations and normal stations. Note that unlike a normal station, a multi-line exchange station connects different lines to collect traffic flows, resulting in more frequent use and a heavy concentration of passenger flow. Thus, for the multi-line exchange station, the passenger flow is the sum of the estimated passenger flow in all the lines passing through it. The passenger flow of stations in the initial Beijing Subway network without any disruption is calculated by using (7). After the disrupted node is deleted from the topological graph, the passenger flow of the disrupted station is assumed to be distributed equally to the directly connected station(s).

C. Performance and Resilience Evaluation for Beijing Subway Network

The reasonable passageways are calculated based on the Dijkstra’s algorithm [37] and the performance of the Beijing Subway network is calculated for both passenger flow of the weekday and weekend respectively, corresponding to the difference resulting from passenger flow. The initial network performance $P$ without any disruption is calculated by (12), where the number of nodes $N$ is equal to 292 and the number of edges is equal to 335. The calculated $P$ is equal to 2.9537 and 2.9437 respectively on the weekday and weekend, which shows that the performance of the Beijing Subway network remains the same level due to the topological structure is not changed through the week and the passenger flow as the weight of performance fluctuates with the same trend. The similar procedure of calculation can be repeated to a disrupted network with all the nodes in the network deleted one by one to deal with the two types of disruption caused by random failure and intentional failure.

The network performance is calculated after each node is deleted in the topological map, then the resilience of the network in different scenarios can be achieved by using (14).

Some disruptions are listed in Table 2. The recovery time depend on many factors such as the human labor and financial resources that can be invested, the severity of the disruptions, etc. A repairing duration analysis in terms of recovery cost is studied in many published model, such as Francis and Bekera [15]. Detailed research on recovery time after the disruption is not displayed in the paper. We set the recovery time as 1 to simplify the question. During the recovery period the performance of the subway network could not increase to the normal level gradually but sharply at the time $t_{1}$ as a result that the disrupted station will be open to the public after fully repaired. Thus, based on the characteristics of subway networks, the “resistance loss triangle” printed in red is displayed in Fig. 7.

TABLE 2 Accidents in Subway (Metro, Undergroud)

FIGURE 7.

Unique resilience triangle model for subway networks.

The calculated results of resilience for top twenty most influenced stations in Beijing Subway network are shown in Table 3 and Table 4 responsible for weekdays and weekends respectively. Meanwhile, the average resilience of the network in different scenarios is shown below:

$$\begin{align*} R_{wday}^{ave}=&0.9804. \tag{15}\\ R_{wend}^{ave}=&0.9803. \tag{16}\end{align*}$$ where $R_{wday}^{ave}$ stands for the average resilience of the Beijing Subway network on weekday; $R_{wend}^{ave}$ stands for the average resilience of the Beijing Subway network on weekend.

TABLE 3 Resilience of Top Twenty Most Influenced Stations for Weekdays

TABLE 4 Resilience of Top Twenty Most Influenced Stations for Weekends

The value of the average resilience for the weekday and weekend shows small difference, which is 0.9804 and 0.9803 respectively. The relative high average resilience indicates that after one station is disrupted, the average performance remained over 98% compared to the original network. It clearly shows that the resilience of the Beijing Subway network is excellent in case of random attacks. However, the resilience of the subway network is the lowest in the scenario that Xizhimen Station is disrupted compared to other stations disrupted in the network both on weekday and weekend with the value of 0.8419 and 0.8417. Obviously, when Xizhimen Station is disrupted and the other stations keep in normal operation, the performance of the disrupted network decreased hugely and only 84 percentage of performance remained compared to the initial network. In addition to Xizhimen Station, Zhichunlu Station, Dongzhimen Station, Haidianhuangzhuang Station and Songjiazhuang Station rank top five most influenced stations from weekday to weekend, which will lead to relative low resilience of the network when disrupted. Therefore, the Beijing Subway network behaviors better under the condition of random failures than intentional failures.

From resilience calculating results and the location of the disrupted stations, it is obvious that stations affect the subway network most are always located in the central part with more lines passing through (higher degree) and there are always more passenger flows over these stations which are typically considered as important hubs. For example, Xizhimen Station has a degree of 5 and the passenger flow over this station is 195620 per day through two weeks. For Dongzhimen Station and Zhichunlu Station, the both degree is 4 and the passenger flow is 163459 and 120979 respectively. As shown in the top twenty most influenced stations in Beijing Subway network, all the important stations lie in the center with high degree and they are all multi-line exchange stations. Haidianhuangzhuang Station and Songjiazhuang Station rank 4 and 5 respectively, the degree of which is 4. Also these two stations are all multi-line exchange stations. However, the results based on different passenger flows produced a different ranking. For example, Caishikou Station and Dongdan Station are not ranked in top twenty on weekdays, but they are ranked in top twenty on the weekends, which suggests that the passenger flow can impact the resilience of subway networks.

Furthermore, the suburb subway lines still have a significant number of stations beyond the critical stations. Once a multi-line exchange station in the suburb subway line is disrupted, the entire connection between downtown and the respective suburb would be completely disrupted. For example, Guogonghzuang Station lies in the southwest of Bejing as the connecting station for Beijing Subway Line 9 and Beijing Subway Fangshan Line. Therefore, every station is a inseparable part of the subway network. As a conclusion Xizhimen Station, Dongzhimen station, etc., influence the whole network most, which also provide to the Beijing Subway managers which stations are more important and managers should protect these stations in top priority.

SECTION IV. Resilience-Based Network Structure Optimization

Once we have made the resilience assessment of Beijing Subway network, which can be used to evaluate the performance of the network and analyze the structural reasonability of networks. The edge addition method aims to add the edges in the graph in order to enhance the resilience of the network to failures. In particular, the edge addition method will change the total number of edges in the network. As introduced from graph theory, a connectivity matrix is used to present the topological connectivity of a network system $G$ . If $G_{1}=[V,E_{1}]$ is a sub-graph with the same node set $V$ of graph $G_{2}=[V,E_{2}]$ , $G_{1}$ has a lower resilience than $G_{2}$ , i.e., If $E_{1}\subset E_{2}$ , then $R(G_{1})\leq R(G_{2})$ . That is, the more connected graph (on the same vertex set) has the higher resilience.

A. Optimization Model to Enhance Resilience

Edge adding is perhaps the most intuitive method for enhancing resilience of network connectivity since it adds edges that are not already presented in $G$ . The resilience-based optimization problem of subway networks can be described as follows. In this optimization, we consider the situation of one edge adding. The problem is how to select which edge between two stations can maximize the network resilience. Selection optimization problems and models have been discussed in many early studies. For this kind of model, we can define the decision variables as:

$$\begin{equation*}E_{(e,f)}=\begin{cases} 1&\text {if} ~e_{ef}~\text {is selected, and}~ e\ne f,\\ 0&\text {otherwise}. \end{cases} \end{equation*}$$

Due to the possible edge adding will change the structure of the target network, all path-dependent variables should be recalculated.

So we solve the following problem. Given the basic graph $G$ , and a set of candidate edges added to $G$ that leads to the greatest increase in the network resilience. Let $G_{(e,f)}$ be the resulting graph after adding an edge $e_{ef}\notin E$ to $G$ .

The mathematical programming formulation for the optimization can be constructed as follows:

Maximize

$$\begin{align*}&\hspace{-1.2pc}R_{(e,f)} \\=&\frac {P_{(e,f)}}{P} \\=&\frac {\sum {u_{(e,f)i}D_{(e,f)}(i)}\sum {v_{(e,f)j}}\sum \left({{\frac {s_{(e,f)k}(i,j)}{d_{(e,f)ij}^{k}}*rel_{(e,f)k}(i,j)}}\right)}{P} \\\tag{17}\end{align*}$$

Subject to

$$\begin{align*}&i\in n,\quad j\in n,~ i\neq j \tag{18}\\&f< e \tag{19}\\&f\in m,\quad e\in m \tag{20}\\&\alpha \le d_{i,j}\le \beta\tag{21}\end{align*}$$ where $R_{(e,f)}$ is the resilience of the network after adding edge $e_{ef}$ , $\alpha$ , $\beta$ are constants. In the objective function, the parameters with the subscript $(e,f)$ have the same meaning of the defined parameters without subscript $(e,f)$ and the difference is they are in different networks. Constraints (18)–(20) are the searching constraints at different networks. Constraint (21) is the restriction of two stations between which the edge is added.

For the optimization of this kind of problem, a genetic algorithm (GA) is chosen for the solution. John Holland introduced genetic algorithms in 1960 based on the concept of Darwin’s theory of evolution, afterwards, his student Goldberg extended GA in 1989 [42], [43]. In computer science and operations research, the GA is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms. Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on bio-inspired operators such as mutation, crossover and selection.

A typical genetic algorithm requires: a genetic representation of the solution domain and a fitness function to evaluate the solution domain. In the paper, the solution domain is the added edge linking two nodes within the topological graph of the subway network, whereas the fitness function is shown in (17). To represent the number of the two stations selected respectively, we encode two chromosomes X and Y as 8-bit binary number, which can not only cover the station from 1 to 292, but also choosing the binary number as chromosome can guarantee when every mutation and crossover happen to the chromosome, the symbol of the chromosome just changes from one station to another.

B. Numerical Results

In order to relieve the computational burden, the first step to analyze the subway network is to simplify the network. The method was presented elsewhere and can be referred to for further explanations [44]. Different from other networks, the connected subway networks consist of some subway lines and each line is divided by several multi-line exchange stations which are the connections of the network. Some normal stations have the same structural characteristic, so we consider them as a single zone respectively [45]. Fig. 8 includes an actual Beijing Subway network with circles as zones Fig. 8(a) and the simplified topological graph of Beijing Subway network Fig. 8(b). In the actual network, 292 nodes and 335 edges. However, the simplified graph only consists of 187 nodes and 173 edges. The computation time can be reduced to a large extent. We set the passenger flow to be 1 for each station in the simplified network.

FIGURE 8.

Display map of simplified Beijing Subway network. (a) Actual Beijing Subway network with circles as zones. (b) Simplified topological graph of Beijing Subway network with best adding edges marked when $\alpha = 2$ , $\beta = 5$ .

In what follows, we apply the optimization algorithm to the simplified Beijing Subway network to tackle the problem. To understand the optimal network structure, we compare which single edges are most efficient at improving the resilience of the network. After many times of attempt, setting the population size as 10, mutation probability as 0.1, crossover probability as 0.2 can be more accurate and efficient. As displayed in Fig. 9(a) and Fig. 9(b), the blue line shows the best individual and the red line shows the average result of each iteration. When $\alpha \,\,=2$ and $\beta \,\,=5$ , after 170 iterations calculating, we achieve the convergence of the algorithm; whereas, when $\alpha \,\,=6$ and $\beta \,\,=9$ , the convergence of the algorithm can be achieved after 176 iterations. From Fig. 9, we can come to a conclusion that the larger $\alpha$ and $\beta$ are, the better solutions will be achieved. However, the relatively long distance of the adding edges will always be spent not only more money but also longer construction period.

FIGURE 9.

Convergence procedure of GA in (a) and (b), and best solution under different $\alpha$ and $\beta$ . (a) Convergence procedure when $\alpha = 2$ , $\beta = 5$ . (b) Convergence procedure when $\alpha = 6$ , $\beta = 9$ . (c) Ten best solution under different $\alpha$ and $\beta$ .

Assume that due to limitation of the financial resources and construction period, only the stations with a shortest path no more than five, i.e.,$\alpha \,\,=2$ and $\beta \,\,=5$ , can be selected, between which a new edge can be added. This assumption can be changed and different construction limitation can be applied without affecting the resilience enhancing model we proposed. The specific locations of the ten most critical adding edges under the circumstance of $\alpha \,\,=2$ and $\beta \,\,=5$ are marked in the simplified topological graph of Beijing Subway network as shown in Fig. 8(b), and the numbers above the adding edges are the ranking of the most efficient solutions. Analyzing the location of these adding edges, it is obvious that most of the adding edges are located in the position linking between center stations. The top 10 of the network resilience after one edge is added are demonstrated in Table 5. We see that adding the edge from Wangjing West Station to Dawanglu Station can obtain the highest resilience, that is 1.1653, which can improve the resilience of the network over sixteen percentage. Also the edges which can maximum the network resilience are always connected from one multi-line exchange station to another multi-line exchange station. There are exceptions from Table 5, for example, the edge from Zhichunlu Station to Fuchengmen Station. Zhichunlu Station is a multi-line exchange station, but Fuchengmen is not a multi-line exchange station, however, which is linked directly to the critical multi-line exchange station Chegongzhuang Station and Fuxingmen Station. So in the aspect of network structure, the adding edges between multi-line exchange stations are always more efficient in improving the resilience of the subway network.

TABLE 5 Top Ten Adding Edges to Improve Resilience

It is evident that the connection of two relative centra multi-line exchange stations can improve resilience much more than the marginal stations in the aspect topological structure. As a conclusion, a new subway line should be implemented into the network linking Wangjing West Station and Dawanglu Station. The result can provide some advices for the Beijing Subway managers in planning and constructing new subway lines.

SECTION V. Conclusion

The main contribution of this paper is developing the resilience assessment model to find out which stations in the subway network are more important and the resilience-based network structure optimization model to find out which edges added to the network can improve the network resilience more efficiently.

First, the unique characteristics of subway networks in topological structure is analyzed. Second, considering recovery time, resilience of the subway network is defined as the fraction of performance that can be satisfied by the degraded subway network after disruptions, which shows the ability of the subway network to resist events once any one station is disrupted. Thirdly, we apply the solution algorithm to analyze the resilience of the real subway network, Beijing Subway network. Finally, the simplified network based on the real Beijing Subway network is optimized.

The evaluation results of the top twenty stations which will lead to the lowest resilience of the subway network when disrupted are showed to the subway managers for protection reference. Whereas, the result of the top ten adding edges which can result in higher resilience are presented to the subway managers for construction reference.

It should be specifically noted that the resilience evaluation model of the subway network discussed in this paper is under the assumption of an undirected and unweighted network. Although this assumption is widely accepted for basic understandings of a large-scale networks, some of the practical factors are not considered such as the physical length of tunnels between stations, the travelling time on the route and also time for transferring from different subway lines. Those factors on the importance of network resilience could be explored in future studies. For the optimization part, the future work aims at providing a multiple edges adding solution to optimizing the network considering the cost, human resource and construction duration.