# Route Redundancy-Based Network Topology Measure of Metro Networks

Authors: Weiwei Jing; Xiangdong Xu; Yichao Pu
Journal: Journal of Advanced Transportation
 (2019)

---

## Abstract

The metro system plays a very important role in the urban multimodal transportation system, yet it is susceptible to accidents. A well-designed metro system needs to provide alternative routes to travellers both in the disruptive events and the normal operating conditions for providing rerouting opportunities and balancing crowded lines. This paper provides a new dimension of assessing metro network performance—travellers’ route redundancy (or route diversity), which is defined as the number of behaviourally effective routes between each origin-destination (O-D) pair in the network. The route redundancy of metro network is evaluated by statistical indicators of the distribution of the O-D-level number of effective routes. Compared with the existing connectivity and accessibility measures of topology network performance, route redundancy is also based on the topology network, but it takes the travellers’ route choice into consideration. Specifically, the effective routes between each O-D pair would provide disaggregated information from the travellers’ perspective. Case studies in four metropolises in the world, i.e., Shanghai, Beijing, London, and Tokyo, are conducted to examine the predisaster preparedness of the four metro networks explicitly from the perspective of route redundancy. The results indicate that the London metro network has the best route redundancy performance in terms of the statistical indicators of the distribution of the O-D level number of effective routes. Furthermore, the results of route redundancy are compared with typical measures of topology network performance in terms of measuring connectivity and accessibility of metro networks. Their differences are attributed to the fact that the route redundancy measure considers the travellers’ O-D-level route choice beyond the pure network topology and the shortest path considerations of the existing measures. The route redundancy proposed in this paper could assist in evaluating the predisaster preparedness of current or planning metro networks from O-D level to network level.


---

## Body

## 1. Introduction

The metro system is becoming a priority choice to mitigate the traffic pressure in many cities, due to its promising advantages such as large capacity, high efficiency, low energy consumption, low pollution, and land resource saving [1]. As of July 2018, as summarized in Wikipedia [2–4], about 180 cities in 54 countries have opened their metro systems, and 40 cities are planning to open a metro system in the future. With the development of economy and technology, metro systems are developing towards high density, high efficiency, and networking [5]. In China, metro systems have received a rapid development in past decades, and 35 cities have opened their metro systems with a total distance of 4,898 kilometres by July 2018. For example, in Shanghai, there are 16 metro lines and 395 stations in operation with the total mileage of 673 kilometres. On the other hand, the metro ridership also continues to increase significantly. For example, in the Beijing metro system, the average daily ridership has a breakneck growth since 2008, and the maximum daily ridership has exceeded 13 million by July 2018.Accidents (e.g., collapse, leak, terrorist attack, fire, and suicide) frequently occur in metro networks [6]. When an accident causes the failure of a station, it would affect not only the individual metro line but also multiple lines or even the whole network [7]. Since the metro network is susceptible to disruptions, measuring its performance under uncertainties has attracted a lot of attention from both researchers and practitioners. Recently,network resilience is being increasingly considered to be an important aspect of network performance or network behaviour following disruptions [8–10]. Resilience is often used in association with several threatening events, which may show critical and catastrophic phases such as terrorist attacks and natural disasters [11]. The White House [12] defined resilience as the ability to prepare for and adapt to changing conditions and withstand and recover rapidly from disruptions. Resilience engineering offers a much broader sociotechnical framework to cope with infrastructure threats and disruptions by focusing on three aspects: readiness and preparedness, response and adaptation, and recovery and adjustment [13].According to Bruneauet al. [14], resilience can be characterized by the four “R’s” concept: redundancy, robustness, resourcefulness, and rapidity.Redundancy is one of the key dimensions of resilience [15], which is defined as “the extent to which elements, systems, or other units of analysis exist that are substitutable”.A resilient network should be redundant as redundancy reflects the predisaster preparedness of a network. In other words, a redundant network would provide alternative choices to reduce the impact of disruptions [16, 17]. Note thatthe redundancy evaluation of the metro network is different from the vulnerability analysis, which focuses on the consequences caused by disruptions or incidents. Interested readers are directed to the book by Taylor [10] which charts the development and a comprehensive overview of transportation network vulnerability analysis. However,very limited attention has been paid to the redundancy of public transportation networks, as shown by the more detailed reviews to be presented in Section 2.This paper provides a new dimension of metro network performance assessment—travellers’ route redundancy, which is measured by the distribution characteristics of the number of effective routes (or paths) between each O-D pair in a metro network. The route redundancy describes the O-D effective connections explicitly from the users’ perspective. We should point out that route redundancy is still based on the topology network, but it could offer more behavioural information than the typical topology network-based measures such as the measures aggregated from the node level (e.g., degree, clustering coefficient) and the measures based on the shortest paths (e.g., diameter, network efficiency). Specifically, it can not only provide disaggregated information from O-D level, but also quantify the number of behaviourally effective alternatives considering that the travellers may not always choose the shortest paths in reality. By looking at four metro networks, i.e., Shanghai, Beijing, London, and Tokyo, we examine the performance of metro networks based on the concept of route redundancy. Furthermore, the differences and relationships between the route redundancy-based measure and the typical topology network measures will be discussed based on the four metro networks.Redundancy reflects the predisaster preparedness of a network for combatting vulnerability. Therefore, with the networking development of metro systems, a well-designed metro network needs to provide alternative routes for travellers as much as possible under the occurrence of accidents. Also, alternative routes are needed to split the passenger flow of congested segments/lines under normal operating conditions. Hence, it is necessary to have a deep understanding of the route redundancy (or route diversity) of metro networks. Following Xuet al. [18], we customize the definition of route redundancy to metro networks asthe number of behaviourally effective routes (or paths) available for passengers between any two stations in the metro network. The assessment of route redundancy could help to evaluate the predisaster preparedness of the current metro network or the planned scheme, and also offer the information of alternative routes to assist metro managers in rerouting passengers in a highly congested or disruptive event. Note that this paper only focuses on the route redundancy from the travellers’ perspective, i.e., the first dimension of transportation network redundancy proposed by Xuet al. [18]. The second dimension (i.e., network spare capacity from the planners’ perspective) of metro network redundancy will be related to the station capacity and line capacity, which itself is more complex than the first dimension. When the operation and scheduling data are available, the second dimension could also be further measured.The reminder of this paper is organized as follows. The studies on redundancy and network topology are introduced in Section2. In Section 3, we provide the definition and computational method of route redundancy. In Section 4, we examine the route redundancy of four metropolitan metro networks and discuss the differences and relationships between the route redundancy and the typical topology network measures. Conclusions are summarized in Section 5.


## 2. Literature Review

The studies on redundancy and network topology of transportation networks are reviewed in this section.


### 2.1. Redundancy

In a broad picture, redundancy is an important topic in systems engineering. In reality, many infrastructure and safety-critical systems require redundancy design such as the water distribution networks [19] and the aircraft door management systems [20]. The concept of redundancy has also been applied in the transportation systems as one of the measures of resilience. Berdica [21] defined redundancy in transportation systems as the existence of numerous optional routes/means of transport between origins and destinations that can result in less serious consequences in case of a disturbance in some part of the system. Immerset al. [22] described the redundancy of road network as sufficient spare capacity which could avoid the degradation in the quality of service. Freckletonet al. [23] defined redundancy as the ability of a traveller to adjust routes as necessary to detour around the affected sections of the network under disruptions. Actually,the concept of redundancy has been widely studied but there is no consensus definition for transportation networks, which comes down to two aspects: the number of alternatives and the network spare capacity (e.g., [10, 18, 24, 25]). For quantifying the redundancy of transportation networks, El-Rashidy and Grant-Muller [25] proposed a redundancy index of various nodes in road networks covering the static aspect of redundancy (i.e., alternative paths) and the dynamic feature of redundancy (i.e., the availability of spare capacity under different network loading and service levels). In their redundancy model, the entropy concept was adopted to measure the configuration of a system and to model the uncertainties inherent in road networks. However, the entropy concept may not be intuitive to travellers, who do care about the existence of optional routes/means. Xuet al. [18] developed two network-based measures for systematically characterizing the redundancy of transportation networks: one is travel alternative diversity from travellers’ perspective to address the question of “how many effective redundant alternatives are there for travellers?” and the other one is network spare capacity from planners’ perspective to address the question of “how much redundant capacity does the network have?”The above redundancy studies are mainly conducted for road networks. For public transportation networks, Jenelius and Cats [26] developed a methodology for evaluating the value for robustness and redundancy of extending the public transportation network. The value of redundancy of the network extension was defined as the value of robustness (i.e., the change in passenger welfare under network disruptions in the extended network compared to the baseline network) minus the difference in welfare under normal conditions in the extended network compared to the baseline network. However,in case of disruptions, the travellers’ inconvenience significantly depends on the availability of alternative travel options, i.e., the amount of redundancy in the network. Yanget al. [7] applied the route diversity index (i.e., the simple average number of reasonable routes between all O-D pairs) of Xuet al. [18] to analyse the route diversity of the Beijing metro network and to identify the vulnerable stations. Yanget al. [7] simply considered the reasonable/efficient routes in defining the route diversity. For improving the realism of route redundancy in metro networks, in this paper, we consider not only efficient routes but also not-too-long routes (termed as effective routes). To a certain degree, this modelling captures both network topology and travellers’ route choice behaviours (via the route cost constraint). In addition, the transfer costs at transfer stations are explicitly modelled in metro networks, which is a significant difference between road networks and metro networks.


### 2.2. Measures of Topology Network Performance

In the past decades, many scholars (e.g., [27–30]) have examined the metro network performances from the viewpoint of graph theory and complex network by focusing on the topological properties of metro networks. The small-world property and scale-free pattern are considered as significant network topological properties, which are also well-studied in metro networks. Small-world effect is referred to as a high clustering and small average shortest path length ([31, 32]), and a scale-free network is defined as the network with a nodal degree distribution following the power law distribution ([32]). For example, Latora and Marchiori [33] analysed the small-world property of Boston subway network; Derrible and Kennedy [34] demonstrated that most metros are small-worlds and scale-free by looking at 33 metro systems.Besides, many metrics have been proposed to measure the performances of topology networks. According to Grubesicet al. [35] and Zhanget al. [36], these metrics could be divided toconnectivity and accessibility measures of the network topology. Typical network performance measures based on topology network are summarized in Table 1. On the one hand, the connectivity measures (e.g., Alpha, Beta, and Gamma indices, average degree, cyclomatic number, and clustering coefficient) are used to assess the connectedness. For these measures, Alpha, Beta, and Gamma indices represent the connectivity and complexity of a network. Specifically, Alpha index is expressed by the ratio of the number of cycles to the maximum number of cycles; Beta index represents the relationship between the number of links and the number of nodes; and Gamma index quantifies the relationship between the number of links and the maximum possible number of links [36]. The node degree measures the number of links converging to each node [37]. The cyclomatic number calculates the number of cycles (or loops), which has been proposed as a topology metric to evaluate the total number of alternatives from the aggregated perspective of the whole network ([34, 36]). The clustering coefficient, known as transitivity, represents an alternative possibility as it measures the overall probability for the network to have interconnected adjacent nodes ([25, 37]). On the other hand, the accessibility measures of network topology, such as diameter and average shortest path length, are directly related to the shortest paths. Network efficiency measures the travel efficiency of passengers between two nodes ([38]). Node betweenness characterizes the centrality of nodes, which could reflect the role of nodes in the network ([39]). These measures have been widely extended to consider passenger flows, route choice, etc. and applied to the robustness and vulnerability analysis of metro networks ([34, 40–46]).Table 1
Typical network performance measures based on topology network ([35–37]).
Metrics Specifications Notes Connectivity Alpha index α = e - v + 1 2 v - 5 e: the number of undirected edges; v: the number of nodes;  di: the number of nodes directly connected to node i;  ei: the number of undirected edges among the nodes directly connected to node i;  lij: the shortest path length from node i to node j;  mjk: the number of shortest paths between node j and node k;  mjk(i): the number of shortest paths between node j and node k through node i. Beta index β = e v Gamma index γ = e 3 v - 6 Average Degree d ¯ = ∑ i d i v Cyclomatic number μ = e - v + 1 Clustering coefficient C = 1 v  ∑ i 2 e i d i ( d i - 1 )  Accessibility Diameter D = m a x ( l i j ) Average shortest path length L = ∑ i , j , i ≠ j l i j v ( v - 1 ) / 2 Network efficiency E = 2 ∑ i , j , i ≠ j 1 / l i j v ( v - 1 ) Average node betweenness B ¯ = ∑ i ∑ j , k , j ≠ k m j k ( i ) / m j k vCompared with these typical measures, the number of redundant effective routes in this paper is still based on the topology network. However, it is evaluated for each O-D pair, which can provide disaggregate information (e.g., the number of behaviourally effective routes) explicitly from the travellers’ perspective. On the one hand, taking the travel choice behaviour into account, the number of effective routes measures the network redundancy from the disaggregate O-D level, while the connectivity measures listed in Table1 are based on the number of nodes and edges or aggregated from the node level to the network level. On the other hand, route redundancy represents a set of alternative choices provided to travellers. As travellers might not choose the shortest paths in reality ([30, 47, 48]), the number of effective routes would provide more information than the above accessibility measures based on the shortest paths.


## 2.1. Redundancy

In a broad picture, redundancy is an important topic in systems engineering. In reality, many infrastructure and safety-critical systems require redundancy design such as the water distribution networks [19] and the aircraft door management systems [20]. The concept of redundancy has also been applied in the transportation systems as one of the measures of resilience. Berdica [21] defined redundancy in transportation systems as the existence of numerous optional routes/means of transport between origins and destinations that can result in less serious consequences in case of a disturbance in some part of the system. Immerset al. [22] described the redundancy of road network as sufficient spare capacity which could avoid the degradation in the quality of service. Freckletonet al. [23] defined redundancy as the ability of a traveller to adjust routes as necessary to detour around the affected sections of the network under disruptions. Actually,the concept of redundancy has been widely studied but there is no consensus definition for transportation networks, which comes down to two aspects: the number of alternatives and the network spare capacity (e.g., [10, 18, 24, 25]). For quantifying the redundancy of transportation networks, El-Rashidy and Grant-Muller [25] proposed a redundancy index of various nodes in road networks covering the static aspect of redundancy (i.e., alternative paths) and the dynamic feature of redundancy (i.e., the availability of spare capacity under different network loading and service levels). In their redundancy model, the entropy concept was adopted to measure the configuration of a system and to model the uncertainties inherent in road networks. However, the entropy concept may not be intuitive to travellers, who do care about the existence of optional routes/means. Xuet al. [18] developed two network-based measures for systematically characterizing the redundancy of transportation networks: one is travel alternative diversity from travellers’ perspective to address the question of “how many effective redundant alternatives are there for travellers?” and the other one is network spare capacity from planners’ perspective to address the question of “how much redundant capacity does the network have?”The above redundancy studies are mainly conducted for road networks. For public transportation networks, Jenelius and Cats [26] developed a methodology for evaluating the value for robustness and redundancy of extending the public transportation network. The value of redundancy of the network extension was defined as the value of robustness (i.e., the change in passenger welfare under network disruptions in the extended network compared to the baseline network) minus the difference in welfare under normal conditions in the extended network compared to the baseline network. However,in case of disruptions, the travellers’ inconvenience significantly depends on the availability of alternative travel options, i.e., the amount of redundancy in the network. Yanget al. [7] applied the route diversity index (i.e., the simple average number of reasonable routes between all O-D pairs) of Xuet al. [18] to analyse the route diversity of the Beijing metro network and to identify the vulnerable stations. Yanget al. [7] simply considered the reasonable/efficient routes in defining the route diversity. For improving the realism of route redundancy in metro networks, in this paper, we consider not only efficient routes but also not-too-long routes (termed as effective routes). To a certain degree, this modelling captures both network topology and travellers’ route choice behaviours (via the route cost constraint). In addition, the transfer costs at transfer stations are explicitly modelled in metro networks, which is a significant difference between road networks and metro networks.


## 2.2. Measures of Topology Network Performance

In the past decades, many scholars (e.g., [27–30]) have examined the metro network performances from the viewpoint of graph theory and complex network by focusing on the topological properties of metro networks. The small-world property and scale-free pattern are considered as significant network topological properties, which are also well-studied in metro networks. Small-world effect is referred to as a high clustering and small average shortest path length ([31, 32]), and a scale-free network is defined as the network with a nodal degree distribution following the power law distribution ([32]). For example, Latora and Marchiori [33] analysed the small-world property of Boston subway network; Derrible and Kennedy [34] demonstrated that most metros are small-worlds and scale-free by looking at 33 metro systems.Besides, many metrics have been proposed to measure the performances of topology networks. According to Grubesicet al. [35] and Zhanget al. [36], these metrics could be divided toconnectivity and accessibility measures of the network topology. Typical network performance measures based on topology network are summarized in Table 1. On the one hand, the connectivity measures (e.g., Alpha, Beta, and Gamma indices, average degree, cyclomatic number, and clustering coefficient) are used to assess the connectedness. For these measures, Alpha, Beta, and Gamma indices represent the connectivity and complexity of a network. Specifically, Alpha index is expressed by the ratio of the number of cycles to the maximum number of cycles; Beta index represents the relationship between the number of links and the number of nodes; and Gamma index quantifies the relationship between the number of links and the maximum possible number of links [36]. The node degree measures the number of links converging to each node [37]. The cyclomatic number calculates the number of cycles (or loops), which has been proposed as a topology metric to evaluate the total number of alternatives from the aggregated perspective of the whole network ([34, 36]). The clustering coefficient, known as transitivity, represents an alternative possibility as it measures the overall probability for the network to have interconnected adjacent nodes ([25, 37]). On the other hand, the accessibility measures of network topology, such as diameter and average shortest path length, are directly related to the shortest paths. Network efficiency measures the travel efficiency of passengers between two nodes ([38]). Node betweenness characterizes the centrality of nodes, which could reflect the role of nodes in the network ([39]). These measures have been widely extended to consider passenger flows, route choice, etc. and applied to the robustness and vulnerability analysis of metro networks ([34, 40–46]).Table 1
Typical network performance measures based on topology network ([35–37]).
Metrics Specifications Notes Connectivity Alpha index α = e - v + 1 2 v - 5 e: the number of undirected edges; v: the number of nodes;  di: the number of nodes directly connected to node i;  ei: the number of undirected edges among the nodes directly connected to node i;  lij: the shortest path length from node i to node j;  mjk: the number of shortest paths between node j and node k;  mjk(i): the number of shortest paths between node j and node k through node i. Beta index β = e v Gamma index γ = e 3 v - 6 Average Degree d ¯ = ∑ i d i v Cyclomatic number μ = e - v + 1 Clustering coefficient C = 1 v  ∑ i 2 e i d i ( d i - 1 )  Accessibility Diameter D = m a x ( l i j ) Average shortest path length L = ∑ i , j , i ≠ j l i j v ( v - 1 ) / 2 Network efficiency E = 2 ∑ i , j , i ≠ j 1 / l i j v ( v - 1 ) Average node betweenness B ¯ = ∑ i ∑ j , k , j ≠ k m j k ( i ) / m j k vCompared with these typical measures, the number of redundant effective routes in this paper is still based on the topology network. However, it is evaluated for each O-D pair, which can provide disaggregate information (e.g., the number of behaviourally effective routes) explicitly from the travellers’ perspective. On the one hand, taking the travel choice behaviour into account, the number of effective routes measures the network redundancy from the disaggregate O-D level, while the connectivity measures listed in Table1 are based on the number of nodes and edges or aggregated from the node level to the network level. On the other hand, route redundancy represents a set of alternative choices provided to travellers. As travellers might not choose the shortest paths in reality ([30, 47, 48]), the number of effective routes would provide more information than the above accessibility measures based on the shortest paths.


## 3. Methodology

In this section, we provide the definition, measure, and computational method of route redundancy in metro networks.


### 3.1. Definition and Measure of Route Redundancy

As summarized in Section2.1, although there is no consensus definition on the network redundancy, the availability of alternative paths in a network is widely accepted to be a measure of redundancy (e.g., [10, 18, 24, 25]). Xuet al. [18] proposed two network-based measures (i.e., travel alternative diversity and network spare capacity) to model transportation network redundancy. They defined travel alternative diversity as the existence of multiple modes and effective routes available for travellers or the number of effective connections between a specific O-D pair. For quantifying the number of alternatives in the metro network, we customize this concept to the route redundancy of metro networks with station transfer costs, i.e.,the number of behaviourally effective routes available for passengers between any two stations in the metro network. Travellers may not treat all simple paths as their usable paths. Following Xuet al. [18], we consider two requirements of effective route: efficient path and not-too-long path.(  1) Efficient Path.Dial [49] defined the efficient path as follows: if a path only consists of links that take network users further away from the origin, it is an efficient path. Consider a directed graphG = (N,A), whereN andA are the set of nodes and directed links, andR andS are the set of origins and destinations, respectively. All links on an efficient path should satisfy(1)crah>crat,∀a∈Awhere crah and crat are the shortest cost from originr to ah (the head node of linka) and at (the tail node of linka), respectively.(  2) Not-Too-Long Path. Typically, passengers prefer not-too-long paths with an acceptable travel cost as their reasonable alternative paths when the primary or secondary path is not available under disruptions. Hence, the following length constraint [50] is introduced to guarantee that all links are reasonable enough relative to the shortest path. (2)ca≤1+τracrah-crat,∀a∈Akwhere ca is the cost (or travel time) of linka; Ak is the set of links on pathk; τra is an allowable or acceptable elongation ratio of considering linka with respect to originr. By constraining the length of each link, we can guarantee that the total cost of a path has the following upper bound:(3)ck=∑a∈Akca≤∑a∈Ak1+τracrah-crat≤∑a∈Ak1+τrmaxcrah-crat=1+τrmaxcrs-crr=1+τrmaxcrswhere ck is the cost of pathk; crr and crs are the shortest cost from originr tor and to destinations, respectively; and τrmax is the maximum of τra. According to Leurent [50], τra can be set as 1.6 for interurban studies or between 1.3 and 1.5 for urban studies. In this paper, we set τra as 1.5 for each link to constrain the length of paths in metropolitan metro networks. Thus, in the measure of route redundancy, we only consider the paths whose lengths do not exceed 2.5 times the shortest path cost between each O-D pair. Without this requirement, the route redundancy will be significantly overestimated, leading to an optimistic assessment.When considering the path costs, the transfer time at transfer stations from one line to another line cannot be ignored. Passengers usually prefer paths with fewer interchanges and shorter travel time, so the transfer time would affect passengers’ path acceptance or choice. In this study, Space L representation is applied to describe the network topology of metro networks, which treats stations as nodes and links between consecutive stations as edges [51]. Furthermore, we add virtual stations and links to represent the transfer time. For example, consider the metro network shown in Figure 1(a), which consists of 2 lines, 9 stations, and 8 two-way links. Passengers can transfer between line 1 and line 2 at station D. We can introduce virtual stations D1 and D2, as shown in Figure 1(b), where the link length between D1 and D2 represents the transfer time or disutility at station D. Therefore, the original networkG(9, 16) can be represented by a directed graphG(10, 18).Figure 1
Metro network representation.
(a)
Original network (b)
Representation with virtual stations and linksWe should point out that passengers still treat the transfer station as a single station. Therefore, we need to map the route redundancy calculated in the represented network back to the route redundancy of the original network by merging the virtual stations. The merging principle is that the number of effective paths between a nontransfer station and a transfer station is equal to the number of effective paths between the nontransfer station and thenearestvirtual station of the transfer station. For example, the route redundancy of O-D pair (A, D) in Figure 1(a) is represented by the number of effective paths between A and D1 in Figure 1(b), and the route redundancy of O-D pair (F, D) is represented by the number of effective paths between F and D2.


### 3.2. Computational Method of Route Redundancy

In this section, the computational method of calculating the number of effective paths between each O-D pair is presented. Menget al. [52] developed a polynomial-time combinational algorithm to compute the number of efficient paths between any two nodes without path enumeration and storage. Xuet al. [18] further extended it to consider the not-too-long path constraint. This algorithm consists of two parts: (1) constructing the subnetworkGr = (Nr,Ar) for each originr, whereNr andAr are the set of nodes and links in the subnetwork; (2) computing the number of effective paths from originr to all nodes in the subnetwork. The detailed procedure is presented as follows:(  1) Construct the Subnetwork G r for Each Origin r. Perform the Dijkstra’s shortest path algorithm to obtain the shortest costcr(n) from originr to all the other nodesn(n≠r). Then, remove the links that satisfy cr(ah)≤cr(at) or ca>(1+τra)(cr(ah)-cr(at)) from the link setA. This step is to guarantee the satisfaction of efficient paths and not-too-long paths in defining the route redundancy.(  2) Calculate the Number of Effective Paths from Origin r to All Nodes in the Subnetwork. Firstly, we initialize the node adjacent matrix Urm,n(m,n∈Nr) by setting Urm,n= 0 for each origin r∈R. For the links in the setAr (i.e., a∈Ar), we set Ur(at,ah)=1. Then, we perform the following operation to calculate the number of effective paths between any node pair inNr.forj∈Nr
form∈Nr∖j
forn∈Nr∖j∖m
Urm,n=Urm,n+Urm,j×Urj,nendendendFinally, the number of effective paths between O-D pair (r,s) nrs can be calculated as follows:for all O-D pair (r, s)
nrs=Ur(r,s)endRemark. The above procedure of calculating the number of effective paths in the subnetworkGr has a polynomial-time complexity, which involves three nested layers. The principle of this algorithm can be explained as follows:(4)nrs=U1r,s+U2r,s+⋯+Upr,swhere Up is thep-power matrix of the adjacent matrixU, and Up(r,s) is equal to the number of paths between O-D pair (r,s) consisting ofp-1 intermediate nodes on these paths. Therefore,p-1 equals the total number of nodes in the network minus 2. The number of paths between O-D pair (r,s) is equal to the total number of directed paths without intermediate node (i.e.,U1), paths with one intermediate node (i.e.,U2), and paths with two intermediate nodes (i.e.,U3), till paths withp-1 intermediate nodes (i.e.,Up). This guarantees the correctness of the above algorithm for counting all the effective paths between each O-D pair.Note that the number of effective paths between each O-D pair is the O-D level measure, while the network-level route redundancy should aggregate the distribution of the O-D-level number of effective paths. In this paper, the statistical indicators of the above distribution will be considered to evaluate the network-level route redundancy, e.g., maximum value, minimum value, the average number of effective paths, median and standard variance of the distribution, and the proportion of O-D pairs with only 1 effective path. In addition, instead of the shortest path length, the length of effective alternative paths could also be considered as the accessibility measures.


## 3.1. Definition and Measure of Route Redundancy

As summarized in Section2.1, although there is no consensus definition on the network redundancy, the availability of alternative paths in a network is widely accepted to be a measure of redundancy (e.g., [10, 18, 24, 25]). Xuet al. [18] proposed two network-based measures (i.e., travel alternative diversity and network spare capacity) to model transportation network redundancy. They defined travel alternative diversity as the existence of multiple modes and effective routes available for travellers or the number of effective connections between a specific O-D pair. For quantifying the number of alternatives in the metro network, we customize this concept to the route redundancy of metro networks with station transfer costs, i.e.,the number of behaviourally effective routes available for passengers between any two stations in the metro network. Travellers may not treat all simple paths as their usable paths. Following Xuet al. [18], we consider two requirements of effective route: efficient path and not-too-long path.(  1) Efficient Path.Dial [49] defined the efficient path as follows: if a path only consists of links that take network users further away from the origin, it is an efficient path. Consider a directed graphG = (N,A), whereN andA are the set of nodes and directed links, andR andS are the set of origins and destinations, respectively. All links on an efficient path should satisfy(1)crah>crat,∀a∈Awhere crah and crat are the shortest cost from originr to ah (the head node of linka) and at (the tail node of linka), respectively.(  2) Not-Too-Long Path. Typically, passengers prefer not-too-long paths with an acceptable travel cost as their reasonable alternative paths when the primary or secondary path is not available under disruptions. Hence, the following length constraint [50] is introduced to guarantee that all links are reasonable enough relative to the shortest path. (2)ca≤1+τracrah-crat,∀a∈Akwhere ca is the cost (or travel time) of linka; Ak is the set of links on pathk; τra is an allowable or acceptable elongation ratio of considering linka with respect to originr. By constraining the length of each link, we can guarantee that the total cost of a path has the following upper bound:(3)ck=∑a∈Akca≤∑a∈Ak1+τracrah-crat≤∑a∈Ak1+τrmaxcrah-crat=1+τrmaxcrs-crr=1+τrmaxcrswhere ck is the cost of pathk; crr and crs are the shortest cost from originr tor and to destinations, respectively; and τrmax is the maximum of τra. According to Leurent [50], τra can be set as 1.6 for interurban studies or between 1.3 and 1.5 for urban studies. In this paper, we set τra as 1.5 for each link to constrain the length of paths in metropolitan metro networks. Thus, in the measure of route redundancy, we only consider the paths whose lengths do not exceed 2.5 times the shortest path cost between each O-D pair. Without this requirement, the route redundancy will be significantly overestimated, leading to an optimistic assessment.When considering the path costs, the transfer time at transfer stations from one line to another line cannot be ignored. Passengers usually prefer paths with fewer interchanges and shorter travel time, so the transfer time would affect passengers’ path acceptance or choice. In this study, Space L representation is applied to describe the network topology of metro networks, which treats stations as nodes and links between consecutive stations as edges [51]. Furthermore, we add virtual stations and links to represent the transfer time. For example, consider the metro network shown in Figure 1(a), which consists of 2 lines, 9 stations, and 8 two-way links. Passengers can transfer between line 1 and line 2 at station D. We can introduce virtual stations D1 and D2, as shown in Figure 1(b), where the link length between D1 and D2 represents the transfer time or disutility at station D. Therefore, the original networkG(9, 16) can be represented by a directed graphG(10, 18).Figure 1
Metro network representation.
(a)
Original network (b)
Representation with virtual stations and linksWe should point out that passengers still treat the transfer station as a single station. Therefore, we need to map the route redundancy calculated in the represented network back to the route redundancy of the original network by merging the virtual stations. The merging principle is that the number of effective paths between a nontransfer station and a transfer station is equal to the number of effective paths between the nontransfer station and thenearestvirtual station of the transfer station. For example, the route redundancy of O-D pair (A, D) in Figure 1(a) is represented by the number of effective paths between A and D1 in Figure 1(b), and the route redundancy of O-D pair (F, D) is represented by the number of effective paths between F and D2.


## 3.2. Computational Method of Route Redundancy

In this section, the computational method of calculating the number of effective paths between each O-D pair is presented. Menget al. [52] developed a polynomial-time combinational algorithm to compute the number of efficient paths between any two nodes without path enumeration and storage. Xuet al. [18] further extended it to consider the not-too-long path constraint. This algorithm consists of two parts: (1) constructing the subnetworkGr = (Nr,Ar) for each originr, whereNr andAr are the set of nodes and links in the subnetwork; (2) computing the number of effective paths from originr to all nodes in the subnetwork. The detailed procedure is presented as follows:(  1) Construct the Subnetwork G r for Each Origin r. Perform the Dijkstra’s shortest path algorithm to obtain the shortest costcr(n) from originr to all the other nodesn(n≠r). Then, remove the links that satisfy cr(ah)≤cr(at) or ca>(1+τra)(cr(ah)-cr(at)) from the link setA. This step is to guarantee the satisfaction of efficient paths and not-too-long paths in defining the route redundancy.(  2) Calculate the Number of Effective Paths from Origin r to All Nodes in the Subnetwork. Firstly, we initialize the node adjacent matrix Urm,n(m,n∈Nr) by setting Urm,n= 0 for each origin r∈R. For the links in the setAr (i.e., a∈Ar), we set Ur(at,ah)=1. Then, we perform the following operation to calculate the number of effective paths between any node pair inNr.forj∈Nr
form∈Nr∖j
forn∈Nr∖j∖m
Urm,n=Urm,n+Urm,j×Urj,nendendendFinally, the number of effective paths between O-D pair (r,s) nrs can be calculated as follows:for all O-D pair (r, s)
nrs=Ur(r,s)endRemark. The above procedure of calculating the number of effective paths in the subnetworkGr has a polynomial-time complexity, which involves three nested layers. The principle of this algorithm can be explained as follows:(4)nrs=U1r,s+U2r,s+⋯+Upr,swhere Up is thep-power matrix of the adjacent matrixU, and Up(r,s) is equal to the number of paths between O-D pair (r,s) consisting ofp-1 intermediate nodes on these paths. Therefore,p-1 equals the total number of nodes in the network minus 2. The number of paths between O-D pair (r,s) is equal to the total number of directed paths without intermediate node (i.e.,U1), paths with one intermediate node (i.e.,U2), and paths with two intermediate nodes (i.e.,U3), till paths withp-1 intermediate nodes (i.e.,Up). This guarantees the correctness of the above algorithm for counting all the effective paths between each O-D pair.Note that the number of effective paths between each O-D pair is the O-D level measure, while the network-level route redundancy should aggregate the distribution of the O-D-level number of effective paths. In this paper, the statistical indicators of the above distribution will be considered to evaluate the network-level route redundancy, e.g., maximum value, minimum value, the average number of effective paths, median and standard variance of the distribution, and the proportion of O-D pairs with only 1 effective path. In addition, instead of the shortest path length, the length of effective alternative paths could also be considered as the accessibility measures.


## 4. Case Study

In this section, we examine and compare the route redundancy of four metro networks, i.e., Shanghai, Beijing, London, and Tokyo. Furthermore, the results of topology network measures will be presented, and the differences and relationships between the route redundancy and the typical topology network measures (i.e., the connectivity measures and accessibility measures summarized in Table1) will be discussed.


### 4.1. Four Metropolitan Metro Networks

Four well-networked metro systems are analysed in this paper: Shanghai (excluding Maglev line), Beijing (excluding airport line), London (including underground, overground, and Transportation for London (TfL) rail), and Tokyo (including subway and some main private rail lines). These four metro networks are shown in Figure2. Table 2 further presents the basic information of each metro network. Note that the operation time between any two stations is obtained from their official websites. The transfer time of Shanghai and Beijing metro networks are also obtained from their official websites, and the transfer time of London and Tokyo metro networks is set to 5 min due to the data unavailability, which is the average transfer time of the Shanghai metro network.Table 2
Basic information of the four metro networks.
City Metro system information # of different types of stations # of lines # of stations Length (km) Non-transfer Two lines Three lines Four lines Five lines Shanghai 14 304 602 250 (82.24%) 46 7 1 0 Beijing 17 291 546 239 (82.13%) 50 2 0 0 London 13 381 569 309 (81.10%) 58 7 6 1 Tokyo 16 257 361 188 (73.15%) 46 14 6 3 Note: the station shared by two or more lines is treated as a single station in the third column; the number in the parenthesis represents the proportion of non-transfer stations.Figure 2
Topologies of the four metropolitan metro networks.
(a)
Shanghai (July, 2017) (b)
Beijing (July, 2017) (c)
London (July, 2017) (d)
Tokyo (July, 2017)According to Table2, among the four metropolitan cities, the London metro network has the largest number of stations (i.e., 381 stations), while the Shanghai metro network has the largest total line length. The Tokyo metro network has the smallest number of stations as well as the total line length. In terms of transfer stations, the Tokyo network has the most transfer stations among the four networks. The number of nontransfer stations accounts for 73.15% in Tokyo, which is the smallest among the four networks. Meanwhile, there are 6 four-line and 3 five-line transfer stations in the Tokyo network, which are larger than those in the London network, while the Shanghai and Beijing networks do not have five-line transfer stations.


### 4.2. Route Redundancy Results

Using the computational method in Section3.2, we can obtain the number of effective paths between each O-D pair. Since the four metro systems have different network scales, the proportion of O-D pairs with each number of effective paths is calculated for a fair comparison. Figure 3 shows the distributions of the number of effective paths among all O-D pairs in each network. Their statistical indicators are also presented in Table 3.Table 3
Statistical indicators of route redundancy distribution.
City Max Min Median Average Standard deviation Proportion of O-D pairs with only 1 effective path Shanghai 13 1 1 1.47 1.0258 73.55% Beijing 14 1 1 1.50 1.0207 72.64% London 50 1 1 2.31 2.8962 56.60% Tokyo 58 1 1 1.93 2.0779 66.23%Figure 3
Distributions of the number of effective paths (the histogram in the middle of each figure shows the detailed distribution of the number of effective paths).
(a)
Shanghai (b)
Beijing (c)
London (d)
TokyoOne can see that all O-D pairs in the four metro networks have at least one effective path. The Tokyo metro network has at most 58 effective paths between two stations, while the Beijing metro network only has at most 14 effective paths between two stations and Shanghai has at most 13 effective paths. The Beijing and Shanghai metro networks have more than 70% of the O-D pairs with only 1 effective path, while Tokyo has 66.23% and London has 56.60% of the O-D pairs with only 1 effective path. This means that passengers of more than 70% of the O-D pairs have no other effective alternatives for their metro trips in Shanghai and Beijing, while more than 40% of the O-D pairs in the London network and more than 30% of the O-D pairs in the Tokyo network have other effective alternatives. Also, the average numbers of effective paths in the Shanghai and Beijing networks are much smaller than 2 (i.e., 1.47 and 1.50), while there are 2.31 and 1.93 in London and Tokyo, respectively. The Shanghai and Beijing metro networks have a more concentrated distribution of the number of effective paths as indicated by their smaller average value and standard deviation, while the London and Tokyo metro networks have more diversely distributed route redundancy with a larger average value and standard deviation. As we mentioned before, the existence of more effective paths between an O-D pair means that there are more rerouting opportunities under both normal operations and disruptive events. The travellers’ inconvenience generated by disruptions and congestions can be reduced by the availability of alternative effective paths, i.e., route redundancy in the network. Overall, the London metro network has more route redundancy (i.e., predisaster preparedness) than the Tokyo metro network; the Shanghai and Beijing metro networks have similar performance of route redundancy, which have less route redundancy than the London and Tokyo metro networks.The number of effective paths between any two stations characterizes the route redundancy of metro networks at the O-D level. It is also meaningful to know how many effective paths originating from a station and going to a station. Therefore, the effective connection of each station can be measured. This information is related to the accessibility of metro stations and can be used in business and residential location decisions. We further define thestation-level route redundancy index (SRI) as the average number of effective paths originating from and going to a station. As there is at least one effective path from a station and one effective path to a station, SRI is not less than 2. The formulation of SRI is as follows:(5)SRIi=∑j=1,j≠iNnij+∑j=1,j≠iNnjiN-1where nij is the number of effective paths from stationi to stationj; N is the total number of stations in the metro network. The distributions of SRI of the four networks are shown in Figure 4. We can observe that the station-level route redundancy of the Shanghai and Beijing metro networks are highly concentrated in the interval of [2,4] with an average SRI of 2.95 and 2.99, respectively. The London and Tokyo metro networks have a larger range of SRI (i.e., from 2 to 11 and from 2 to 8). Both of London and Tokyo are mostly concentrated in the interval of [3,4], but the London network has more stations with SRI being greater than 5. Therefore, the average SRI of London (i.e., 4.62) is the highest among the four cities. Overall, the distribution of SRI is consistent with the distribution of the O-D-level number of effective paths shown in Figure 3 and Table 3. This further verifies the promising route redundancy performance of the London and Tokyo metro networks.Figure 4
Distributions of station-level route redundancy index.


### 4.3. Comparison of Route Redundancy and Other Measures

The results in Section4.2 show that the London metro network has the best performance in the O-D-level and station-level route redundancy compared with the Tokyo, Shanghai, and Beijing metro networks. As summarized in Table 1, the typical network performance measures based on the topology network can be divided into two categories: connectivity measures and accessibility measures. The route redundancy is also based on the topology metro network. Below we discuss the difference and relationship between the route redundancy and these typical measures using the above four metro networks.(  1) Route Redundancy versus Connectivity Measures.Table 4 presents the results of connectivity measures of the four metro networks. In terms of the Alpha index, Beta index, and Gamma index, the decreasing sequence is Tokyo, Shanghai, London, and Beijing, which means that the Tokyo metro network has the best connectivity among the four networks. Among the three indices, Alpha index is equal to the ratio of the number of cycles to the maximum possible number of cycles in a network. The result of the cyclomatic number shows that the Tokyo network has the largest number of cycles (i.e., 66 cycles) among the four metro networks, and London has more cycles than Shanghai and Beijing. The result difference between the Alpha index and the cyclomatic number is due to the larger number of stations in the London metro network than Shanghai and Beijing. The average degree and clustering coefficient are both node-level metrics. For a single line, the degree of most of stations is 2 except for the beginning and ending nodes. The degree of transfer stations in a network is usually greater than 2. The average degrees of the four metro networks are all between 2 and 3, and the largest one is also in the Tokyo network as the transfer stations account for the largest proportion. The clustering coefficient describes the degree to which nodes in the network tend to cluster together. The results show that the clustering coefficient of the four networks are all close to 0. The Tokyo network is the highest, and the nodes of the London network are more clustered than Shanghai and Beijing. Overall, the Tokyo metro network has the best connectivity, which is the most complex one among the four metro networks. The values of connectivity measures of the Beijing metro network are the lowest. The London metro network has more cycles and its nodes are more clustered than Shanghai, but the other four measures indicate that Shanghai has slightly better connectivity than London.Table 4
Connectivity measures of the four metro networks.
City Alpha index Beta index Gamma index Average Degree Cyclomatic number Clustering coefficient Shanghai 0.0796 1.1546 0.3874 2.3092 48 0.0081 Beijing 0.0711 1.1375 0.3818 2.2749 41 0.0023 London 0.0753 1.1470 0.3843 2.2940 57 0.0103 Tokyo 0.1297 1.2529 0.4209 2.5058 66 0.0214Among the typical measures of network connectivity, Alpha index, Beta index, Gamma index, and the cyclomatic number are calculated based on the number of nodes and the number of edges; the average degree and the clustering coefficient are aggregated from the node-level metrics to the network level. These measures are mainly related to the network structure. In contrast, the route redundancy measure proposed in this paper is able to consider passengers’ route choice besides the network topology and is aggregated from the O-D level, which could explicitly reflect alternative routes information (besides the shortest path only) for each O-D pair. Therefore, although the London metro network does not have the best topological connectivity as shown in Table4, it could provide more alternative routes for travellers than the other three metro networks as shown in Section 4.2.(  2) Route Redundancy versus Accessibility Measures.The results of accessibility measures are provided in Table 5. As introduced in Section 2.2, diameter and average shortest path length are directly related to the shortest paths. The Shanghai metro network has the largest diameter (i.e., 152), which is about two times the Tokyo metro network. Both Beijing and London also have diameters greater than 100. The average shortest path length of Tokyo is the lowest (i.e., 14.9963) and the other three networks have the average shortest path length, greater than 23. This means that travellers of each O-D pair should take at least an average of 23 minutes in Shanghai, Beijing, and London metro networks. Therefore, the network efficiency of the Tokyo network is much higher than the other three networks, as network efficiency is calculated by the harmonic mean of the length of all the shortest paths in the network. Compared to the above three measures, the average node betweenness is a node-level measure quantifying the importance of each node, which is also related to the shortest paths. For the London metro network, each node would be passed by the shortest paths of around 6,641 O-D pairs on average, while this number is less than 5,000 for the other three networks. It indicates that the nodes in the London metro network tend to be more important as they would be passed by more shortest paths. In summary, similar to the connectivity results, the Tokyo metro network also has the best accessibility performance among the four networks, as shown by the smaller diameter, shorter path length, and higher network efficiency. As to the average node betweenness, the nodes in the Tokyo metro network are also less important than the other three networks. The Shanghai, Beijing, and London networks have a similar accessibility performance but the nodes of the London metro network tend to be more important.Table 5
Accessibility measures of the four metro networks.
City Diameter (min) Average shortest path length (min) Network efficiency (min−1) Average node betweenness Shanghai 152 23.7878 0.0159 4,719 Beijing 142 23.4021 0.0164 4,496 London 127 23.0497 0.0155 6,641 Tokyo 77 14.9963 0.0955 4,138The accessibility measures, i.e., diameter, average shortest path length, network efficiency, and node betweenness, are calculated based on the shortest path of each O-D pair (Table5). Empirical studies (e.g., [30, 47, 48]) have shown that travellers may not always select the shortest path due to many reasons such as perception error and multicriterion consideration (e.g., [53]). Considering this behaviour realism, this paper explicitly captures the number of effective alternative paths with travel costs constraints. Although the number of effective paths cannot directly reflect the distance or efficiency of a network, the concept of effective path could be further applied to measure the network accessibility by replacing the shortest paths. Therefore, although the Tokyo metro network has the best accessibility, it has fewer effective alternatives for travellers than the London metro network.Overall, the results of connectivity and accessibility measures are quite different from the results of route redundancy. Among the four metro networks, the Tokyo metro network has better connectivity and accessibility, while the London metro network has more route redundancy. The main reason is that the route redundancy measure considers the O-D-level travellers’ route choice (i.e., efficient route and not-too-long route) beyond the pure network topology (as in the connectivity measures) and the shortest path (as in the accessibility measures) considerations.


## 4.1. Four Metropolitan Metro Networks

Four well-networked metro systems are analysed in this paper: Shanghai (excluding Maglev line), Beijing (excluding airport line), London (including underground, overground, and Transportation for London (TfL) rail), and Tokyo (including subway and some main private rail lines). These four metro networks are shown in Figure2. Table 2 further presents the basic information of each metro network. Note that the operation time between any two stations is obtained from their official websites. The transfer time of Shanghai and Beijing metro networks are also obtained from their official websites, and the transfer time of London and Tokyo metro networks is set to 5 min due to the data unavailability, which is the average transfer time of the Shanghai metro network.Table 2
Basic information of the four metro networks.
City Metro system information # of different types of stations # of lines # of stations Length (km) Non-transfer Two lines Three lines Four lines Five lines Shanghai 14 304 602 250 (82.24%) 46 7 1 0 Beijing 17 291 546 239 (82.13%) 50 2 0 0 London 13 381 569 309 (81.10%) 58 7 6 1 Tokyo 16 257 361 188 (73.15%) 46 14 6 3 Note: the station shared by two or more lines is treated as a single station in the third column; the number in the parenthesis represents the proportion of non-transfer stations.Figure 2
Topologies of the four metropolitan metro networks.
(a)
Shanghai (July, 2017) (b)
Beijing (July, 2017) (c)
London (July, 2017) (d)
Tokyo (July, 2017)According to Table2, among the four metropolitan cities, the London metro network has the largest number of stations (i.e., 381 stations), while the Shanghai metro network has the largest total line length. The Tokyo metro network has the smallest number of stations as well as the total line length. In terms of transfer stations, the Tokyo network has the most transfer stations among the four networks. The number of nontransfer stations accounts for 73.15% in Tokyo, which is the smallest among the four networks. Meanwhile, there are 6 four-line and 3 five-line transfer stations in the Tokyo network, which are larger than those in the London network, while the Shanghai and Beijing networks do not have five-line transfer stations.


## 4.2. Route Redundancy Results

Using the computational method in Section3.2, we can obtain the number of effective paths between each O-D pair. Since the four metro systems have different network scales, the proportion of O-D pairs with each number of effective paths is calculated for a fair comparison. Figure 3 shows the distributions of the number of effective paths among all O-D pairs in each network. Their statistical indicators are also presented in Table 3.Table 3
Statistical indicators of route redundancy distribution.
City Max Min Median Average Standard deviation Proportion of O-D pairs with only 1 effective path Shanghai 13 1 1 1.47 1.0258 73.55% Beijing 14 1 1 1.50 1.0207 72.64% London 50 1 1 2.31 2.8962 56.60% Tokyo 58 1 1 1.93 2.0779 66.23%Figure 3
Distributions of the number of effective paths (the histogram in the middle of each figure shows the detailed distribution of the number of effective paths).
(a)
Shanghai (b)
Beijing (c)
London (d)
TokyoOne can see that all O-D pairs in the four metro networks have at least one effective path. The Tokyo metro network has at most 58 effective paths between two stations, while the Beijing metro network only has at most 14 effective paths between two stations and Shanghai has at most 13 effective paths. The Beijing and Shanghai metro networks have more than 70% of the O-D pairs with only 1 effective path, while Tokyo has 66.23% and London has 56.60% of the O-D pairs with only 1 effective path. This means that passengers of more than 70% of the O-D pairs have no other effective alternatives for their metro trips in Shanghai and Beijing, while more than 40% of the O-D pairs in the London network and more than 30% of the O-D pairs in the Tokyo network have other effective alternatives. Also, the average numbers of effective paths in the Shanghai and Beijing networks are much smaller than 2 (i.e., 1.47 and 1.50), while there are 2.31 and 1.93 in London and Tokyo, respectively. The Shanghai and Beijing metro networks have a more concentrated distribution of the number of effective paths as indicated by their smaller average value and standard deviation, while the London and Tokyo metro networks have more diversely distributed route redundancy with a larger average value and standard deviation. As we mentioned before, the existence of more effective paths between an O-D pair means that there are more rerouting opportunities under both normal operations and disruptive events. The travellers’ inconvenience generated by disruptions and congestions can be reduced by the availability of alternative effective paths, i.e., route redundancy in the network. Overall, the London metro network has more route redundancy (i.e., predisaster preparedness) than the Tokyo metro network; the Shanghai and Beijing metro networks have similar performance of route redundancy, which have less route redundancy than the London and Tokyo metro networks.The number of effective paths between any two stations characterizes the route redundancy of metro networks at the O-D level. It is also meaningful to know how many effective paths originating from a station and going to a station. Therefore, the effective connection of each station can be measured. This information is related to the accessibility of metro stations and can be used in business and residential location decisions. We further define thestation-level route redundancy index (SRI) as the average number of effective paths originating from and going to a station. As there is at least one effective path from a station and one effective path to a station, SRI is not less than 2. The formulation of SRI is as follows:(5)SRIi=∑j=1,j≠iNnij+∑j=1,j≠iNnjiN-1where nij is the number of effective paths from stationi to stationj; N is the total number of stations in the metro network. The distributions of SRI of the four networks are shown in Figure 4. We can observe that the station-level route redundancy of the Shanghai and Beijing metro networks are highly concentrated in the interval of [2,4] with an average SRI of 2.95 and 2.99, respectively. The London and Tokyo metro networks have a larger range of SRI (i.e., from 2 to 11 and from 2 to 8). Both of London and Tokyo are mostly concentrated in the interval of [3,4], but the London network has more stations with SRI being greater than 5. Therefore, the average SRI of London (i.e., 4.62) is the highest among the four cities. Overall, the distribution of SRI is consistent with the distribution of the O-D-level number of effective paths shown in Figure 3 and Table 3. This further verifies the promising route redundancy performance of the London and Tokyo metro networks.Figure 4
Distributions of station-level route redundancy index.


## 4.3. Comparison of Route Redundancy and Other Measures

The results in Section4.2 show that the London metro network has the best performance in the O-D-level and station-level route redundancy compared with the Tokyo, Shanghai, and Beijing metro networks. As summarized in Table 1, the typical network performance measures based on the topology network can be divided into two categories: connectivity measures and accessibility measures. The route redundancy is also based on the topology metro network. Below we discuss the difference and relationship between the route redundancy and these typical measures using the above four metro networks.(  1) Route Redundancy versus Connectivity Measures.Table 4 presents the results of connectivity measures of the four metro networks. In terms of the Alpha index, Beta index, and Gamma index, the decreasing sequence is Tokyo, Shanghai, London, and Beijing, which means that the Tokyo metro network has the best connectivity among the four networks. Among the three indices, Alpha index is equal to the ratio of the number of cycles to the maximum possible number of cycles in a network. The result of the cyclomatic number shows that the Tokyo network has the largest number of cycles (i.e., 66 cycles) among the four metro networks, and London has more cycles than Shanghai and Beijing. The result difference between the Alpha index and the cyclomatic number is due to the larger number of stations in the London metro network than Shanghai and Beijing. The average degree and clustering coefficient are both node-level metrics. For a single line, the degree of most of stations is 2 except for the beginning and ending nodes. The degree of transfer stations in a network is usually greater than 2. The average degrees of the four metro networks are all between 2 and 3, and the largest one is also in the Tokyo network as the transfer stations account for the largest proportion. The clustering coefficient describes the degree to which nodes in the network tend to cluster together. The results show that the clustering coefficient of the four networks are all close to 0. The Tokyo network is the highest, and the nodes of the London network are more clustered than Shanghai and Beijing. Overall, the Tokyo metro network has the best connectivity, which is the most complex one among the four metro networks. The values of connectivity measures of the Beijing metro network are the lowest. The London metro network has more cycles and its nodes are more clustered than Shanghai, but the other four measures indicate that Shanghai has slightly better connectivity than London.Table 4
Connectivity measures of the four metro networks.
City Alpha index Beta index Gamma index Average Degree Cyclomatic number Clustering coefficient Shanghai 0.0796 1.1546 0.3874 2.3092 48 0.0081 Beijing 0.0711 1.1375 0.3818 2.2749 41 0.0023 London 0.0753 1.1470 0.3843 2.2940 57 0.0103 Tokyo 0.1297 1.2529 0.4209 2.5058 66 0.0214Among the typical measures of network connectivity, Alpha index, Beta index, Gamma index, and the cyclomatic number are calculated based on the number of nodes and the number of edges; the average degree and the clustering coefficient are aggregated from the node-level metrics to the network level. These measures are mainly related to the network structure. In contrast, the route redundancy measure proposed in this paper is able to consider passengers’ route choice besides the network topology and is aggregated from the O-D level, which could explicitly reflect alternative routes information (besides the shortest path only) for each O-D pair. Therefore, although the London metro network does not have the best topological connectivity as shown in Table4, it could provide more alternative routes for travellers than the other three metro networks as shown in Section 4.2.(  2) Route Redundancy versus Accessibility Measures.The results of accessibility measures are provided in Table 5. As introduced in Section 2.2, diameter and average shortest path length are directly related to the shortest paths. The Shanghai metro network has the largest diameter (i.e., 152), which is about two times the Tokyo metro network. Both Beijing and London also have diameters greater than 100. The average shortest path length of Tokyo is the lowest (i.e., 14.9963) and the other three networks have the average shortest path length, greater than 23. This means that travellers of each O-D pair should take at least an average of 23 minutes in Shanghai, Beijing, and London metro networks. Therefore, the network efficiency of the Tokyo network is much higher than the other three networks, as network efficiency is calculated by the harmonic mean of the length of all the shortest paths in the network. Compared to the above three measures, the average node betweenness is a node-level measure quantifying the importance of each node, which is also related to the shortest paths. For the London metro network, each node would be passed by the shortest paths of around 6,641 O-D pairs on average, while this number is less than 5,000 for the other three networks. It indicates that the nodes in the London metro network tend to be more important as they would be passed by more shortest paths. In summary, similar to the connectivity results, the Tokyo metro network also has the best accessibility performance among the four networks, as shown by the smaller diameter, shorter path length, and higher network efficiency. As to the average node betweenness, the nodes in the Tokyo metro network are also less important than the other three networks. The Shanghai, Beijing, and London networks have a similar accessibility performance but the nodes of the London metro network tend to be more important.Table 5
Accessibility measures of the four metro networks.
City Diameter (min) Average shortest path length (min) Network efficiency (min−1) Average node betweenness Shanghai 152 23.7878 0.0159 4,719 Beijing 142 23.4021 0.0164 4,496 London 127 23.0497 0.0155 6,641 Tokyo 77 14.9963 0.0955 4,138The accessibility measures, i.e., diameter, average shortest path length, network efficiency, and node betweenness, are calculated based on the shortest path of each O-D pair (Table5). Empirical studies (e.g., [30, 47, 48]) have shown that travellers may not always select the shortest path due to many reasons such as perception error and multicriterion consideration (e.g., [53]). Considering this behaviour realism, this paper explicitly captures the number of effective alternative paths with travel costs constraints. Although the number of effective paths cannot directly reflect the distance or efficiency of a network, the concept of effective path could be further applied to measure the network accessibility by replacing the shortest paths. Therefore, although the Tokyo metro network has the best accessibility, it has fewer effective alternatives for travellers than the London metro network.Overall, the results of connectivity and accessibility measures are quite different from the results of route redundancy. Among the four metro networks, the Tokyo metro network has better connectivity and accessibility, while the London metro network has more route redundancy. The main reason is that the route redundancy measure considers the O-D-level travellers’ route choice (i.e., efficient route and not-too-long route) beyond the pure network topology (as in the connectivity measures) and the shortest path (as in the accessibility measures) considerations.


## 5. Conclusions

In this paper, we provided a new dimension of metro network performance explicitly from travellers’ perspective—route redundancy/diversity. The route redundancy was defined as the number of behaviourally effective paths (i.e., efficient and not-too-long paths) between two stations, which reflects the predisaster preparedness of the metro network. Based on the O-D level route redundancy, we further defined the station-level route redundancy as the average number of effective paths originating from or going to a station. For presenting the characteristics of this measure, route redundancy of four dense metropolitan metro networks, i.e., Shanghai, Beijing, London, and Tokyo, were examined. As the route redundancy proposed in this paper is still based on the topology network, the results of typical measures of topology network performance, including connectivity and accessibility, were presented to discuss the differences and relationships between the route redundancy and these typical measures.The route redundancy results indicated that the London metro network has the best route redundancy performance in terms of the mean and standard deviation of the number of effective paths between an O-D pair as well as the proportion of O-D pairs with only 1 effective path. The average number of effective paths of the Tokyo network is less than London, even if the maximum number of effective paths of Tokyo is the largest. In case of normal operations or disruptions, the London metro network would provide the most rerouting opportunities for travellers among the four networks. Both of the Shanghai and Beijing metro networks have less route redundancy than the London and Tokyo metro networks, as there are fewer effective alternatives for travellers in the Shanghai and Beijing networks. According to the results of typical topology network performance measures, the Tokyo metro network has the best connectivity and accessibility performances among the four networks. The differences between the route redundancy and these typical connectivity and accessibility measures are attributed to the following two reasons: on the one hand, compared with the measures based on the number of nodes and edges or aggregated from the node level to the network level, route redundancy provides disaggregate O-D level information and takes the travellers’ route choice behaviour into account. On the other hand, compared with the measures related to the shortest paths, the route redundancy explicitly captures the number of behaviourally effective alternative paths with travel costs constraints, which is more consistent with the empirical observation that in reality travellers may not always select the shortest path.There are some limitations in this paper that should be addressed in future research.(i)
Based on the data of actual disruptions or agent-based simulations, the route redundancy measure proposed in this paper could be applied to examine the network performance under disruptions and to justify the vulnerability analysis results of metro networks. Using the concept of route redundancy, we can further identify which stations (i.e., critical stations) have the largest impact on the route redundancy of a metro network (e.g., [54, 55]). The identification of critical stations could assist in the resource allocation for strategically protecting the metro network and the decision-making for emergency evacuation planning.(ii)
It is interesting to examine the redundancy of a multimodal transportation network, which would provide not only alternative routes (i.e., route redundancy proposed in this paper) but also alternative travel modes for travellers.(iii)
This paper only examined the route redundancy dimension of network redundancy. To provide a more comprehensive assessment, the network capacity dimension of metro network redundancy could also be modelled and examined by considering both travellers’ and planners’ perspectives.



---

*Source: 4576961-2019-07-03.xml*