# A Passenger Flow Control Method for Subway Network Based on Network Controllability

Authors: Lu Zeng; Jun Liu; Yong Qin; Li Wang; Jie Yang
Journal: Discrete Dynamics in Nature and Society
 (2018)

---

## Abstract

The volume of passenger flow in urban rail transit network operation continues to increase. Effective measures of passenger flow control can greatly alleviate the pressure of transportation and ensure the safe operation of urban rail transit systems. The controllability of an urban rail transit passenger flow network determines the equilibrium state of passenger flow density in time and space. First, a passenger flow network model of urban rail transit and an evaluation index of the alternative set of flow control stations are proposed. Then, the controllable determination model of the urban rail transit passenger flow network is formed by converting the passenger flow distribution into a system state equation based on system control theory. The optimization method of passenger flow control stations is established via driver node matching to realize the optimized control of network stations. Finally, a real-world case study of the Beijing subway network is presented to demonstrate that the passenger flow network is controllable when driver nodes compose 25.3% of the entire network. The optimization of the flow control station, set during the morning peak, proves the efficiency and validity of the proposed model and algorithm.


---

## Body

## 1. Introduction

Due to their large size, fast speed, and safety, urban rail transit systems have become the backbone of city transportation. In recent years, the volume of passenger flow has increased rapidly. Congestion of passenger flow is very high, especially during the morning and evening rush hours, which is a severe challenge for the operational safety of urban rail transit. With network integration of urban rail transit, traditional passenger flow control methods cannot accommodate the increasingly large-volume, line-intensive, complex organizational conditions in modern transit systems. The strategy of flow control optimization for urban rail transit network controllability provides a new perspective for network control.Along with the increasing in urban rail transit passenger volume, research on subway passenger flow control and related topics has attracted the interest of many scholars. Xu et al. [1] proposed a flow control method and analyzed the relationship between station capacity and demand based on queuing network theory. Cortés [2, 3] developed a strategy to control public transport lines using stop-station waiting and interchange station operation by minimizing the waiting time and uniform time interval. D. Felipe et al. [4] proposed a new mathematical programming model by minimizing the time delay of a bus. The model controls the number of passengers boarding the bus to minimize the delay time. In conclusion, current passenger flow control methods focus on a single station, line, or local network. Few works have considered the use of optimization flow control methods to control the overall stability of the network. In addition, existing passenger flow control is mainly based on static relationships between stations and does not consider the timing sequence. This paper optimizes the current flow control method via network controllability according to the characteristics of urban rail transit network and distribution.The study of network controllability began relatively recently, and we can divide the main research methods into three categories: flock control, traction control, and structural control. The early theory of complex network control was initiated by the study of large-scale system flocking control. Flocking control is the analysis of emerging behavior based on simulations of biological groups in nature. Most flocking control studies are based on the Boids model [5], in which an individual is defined as a node in a cluster system, and the connections between individual are defined as edges. Tanner and Olfai et al. [6, 7] introduced a discontinuous control method based on this model and an algorithm to control the state of change.Pinning control is representative of complex network control. Wang et al. [8, 9] combined pinning control and flocking control and applied pinning control to a scale-free dynamic network. The results showed that pinning control with a high degree of nodes requires fewer controllers than the conventional pinning control. Chen et al. [10] studied the pinning control of complex dynamic networks and the controllability of directed networks and proposed the theory of “network of networks”. Fu [11] demonstrated that the preferential pinning strategy of stochastic pinning is superior to the preferential pinning strategy of clustered complex networks. A new pinning strategy based on the cluster degree was proposed, and the results indicated that the new cluster pinning strategy was superior to the RP strategy when there were fewer pinning nodes.Liu [12] studied the controllability of directed networks in 2011 and applied the judgment of the state-space equation of control theory to network controllability for the first time. In addition, the directed network was transformed into a binary graph, and the maximum matching was calculated. Liu's research represented a new starting point for network controllability and laid the foundation for subsequent studies by others. A great deal of subsequent work has begun to focus on the impact of network topology on the controllable performance of network structure [13–18]. Based on Liu's research, the relationship between the controllability and energy consumption of different types of networks was analyzed from the perspective of energy consumption [19]. Nepusz [20] converted the network to an edge-based model by considering the dynamics of the edges of the network. Lombardi [21] applied a controllable matrix to the network. The value of the matrix element was the path gain from the input signal to the node. Chen et al. [22] evaluated changes and control costs of network controllability under cascade failure conditions. The number of driver nodes of a random network and scale-free network were calculated in cascade failures. A minimum structure perturbation method was proposed to optimize the controllability of the network [23]. The minimum number of edges required for controllable optimization was equal to the minimum number of conversion edges, and a network with positive correlation facilitated optimal control.With the in-depth study of controllability of complex networks, many studies have applied control methods to the control judgment and optimization of real networks. Meng [24] studied the controllability of a railway train service network and defined the driver nodes based on immune transmission and cascade failures. An improved theoretical model for the control of complex network and a dual graph of train service network were constructed. Ravindran [25] identified driver nodes with a maximum matching algorithm and classified the nodes. The key regulatory genes in the cancer signal network were identified by controllable analysis. The topology and controllability of the U.S. power grid were analyzed by Li [26], and a new method was proposed to quantify the probability of the intermittent node becoming the driver node.Previous research on network controllability has mainly been based on the general characteristics of complex networks. In recent years, a few studies have examined controllable analysis of real networks. However, these studies have mainly focused on the analysis of complex topological properties. There is no specific strategy for the optimization of network controllability. Most studies have ignored the function attributes of the nodes and edge weights in the actual network, making it impossible to propose effective control methods and coping strategies for specific issues.This paper analyzes the topological characteristics of an urban rail transit passenger flow network. Then, a controllability model of the passenger flow network is constructed based on traditional control theory. An improved controllability determination method for uncontrollable networks is proposed, and the minimum number of driver nodes in the controllability passenger flow network is calculated. The method of flow control optimization is built based on driver node matching, and the specific flow control station set for controllability of the passenger flow network is presented. The method is validated based on actual passenger flow data for the Beijing subway network. In the actual flow control process, the passenger flow will change. The set of flow control stations is obtained at different time periods. When the passenger flow is relatively stable, the flow control stations tend to be fixed.


## 2. Controllability Model of the Urban Rail Transit Passenger Flow Network

### 2.1. Basic Indicators of the Passenger Flow Network

The model of the passenger flow network must be built based on the rail infrastructure line. We define the station as a node and the rail connecting two adjacent stations as an edge. The nodes and edges constitute a physical network of urban rail transit. We then superimpose passenger flow on the orbital transport physical network, which can be extended to a passenger flow network of urban rail transit. The station is defined as a node of the network. If there is passenger flow between two stations, there is an edge between the two stations. The transferred passenger flow is the weight of the edge. This is the passenger flow network of urban rail transit.A complex network generally has a high number of nodes, a large degree of distribution, high concentration, and so on. The passenger flow has the characteristic of strong fluidity. Therefore, the whole network cannot be controlled effectively solely by determining the flow control node from the aggregation number of passenger flow. This paper analyzes the basic indices of the passenger flow network, thus laying the foundation for study of the controllability of the passenger flow network.(  1) Degree. The degree is defined as the number of connections between node i and other nodes. The greater the degree is, the more connections between nodes and the more important the nodes are in the network. The degree is given by(1)ki=∑i≤jnijwhere nij is a variable from 0 to 1 representing the connection between nodes.The degree value of the passenger flow network of urban rail transit reflects the accessibility of network nodes. A larger value indicates more transfer choices for a station. Conversely, a smaller degree value indicates weaker accessibility of a station. Passengers may need to make a high number of transfers before arriving at their destination.(  2) Node Strength. If wij is the connection weight of nodes i and j, the node strength Si of network node i is defined by(2)Si=∑i=1n∑j=1nwijThe node strength is the sum of the node weights. The node strength of the passenger flow network of urban rail transit reflects the passenger demand of the station. The greater the node strength is, the larger the passenger flow of the station is.(  3) Clustering Coefficient. The clustering coefficient reflects the node aggregation of the network. It assumes that the number of connection edges of node i is ki. The maximum number of edges of node number ki is ki(ki-1)/2. The clustering coefficient Ci of node i is defined as follows:(3)Ci=2Eikiki-1The clustering coefficient of the urban rail transit network reflects the connection of transfer passenger flow between stations. The larger the aggregation coefficient is, the higher the connection degree between stations is.(  4) Average Path Length of the Network. Distance dij between nodes i and j is defined as the number of edges of the shortest path between two nodes. The average path length of network L is defined as follows:(4)L=11/2NN-1∑dijwhere N is the number of network nodes.The average path length of the urban rail transit passenger network reflects the number of passing stations from the origin to the destination. This parameter is an indicator of the connectivity of the passenger flow network of urban rail transit.


### 2.2. Controllability Determination Method of the Passenger Flow Network

#### 2.2.1. System Controllable Determination Theory

If there is a segmented continuous inputu(t), the system can proceed from an initial state x(t0) to any specified terminal state x(tf) in a finite time interval [t0,tf]. It is then said that the state is controllable. If all states of the system are controllable, it is said that the system is fully controllable.The input-output model of a linear time-invariant system can be represented as follows [27]:(5)x˙=Axt+Butwhere the vector x(t)=(x1(t),......,xN(t))T captures the state of a system of N nodes at time t.The input signalu(t)=(u1(t),...,uM(t))T,M≤N.A is the state matrix: A∈RN×N.B is the input matrix: B∈RN×M.The controllability determination model of an urban rail transit passenger flow network belongs to the linear time-invariance system model. The model has two properties: linear and time invariance. The objective of this paper is to optimize the flow control of the urban rail transit network. In this paper, the time interval of flow control of the passenger flow network is discretized. In subdivided period, the topology link of the passenger flow network is invariant. Therefore, the passenger flow network system in one time interval is constant. Second, the input of the system is the set of flow control stations. The network state is the result of the interaction among flow control stations. Therefore, the optimization of flow control of the urban rail transit network in this paper satisfies additivity.


#### 2.2.2. Controllability Analysis of the Passenger Flow Network of Urban Rail Transit

After the network operation of rail transit, the change and rule of passenger flow are more complicated than those of the single or simple network structures due to the greater number of flow and transfer opportunities. An urban rail transit network is a control system. The external flow control measures are the input signals, and the OD passenger flows of the network are the state variables. Under normal conditions, urban rail transit networks are within the controllable range. However, in the morning and evening peak hours or under large passenger flow conditions, due to the reduced levels of path service and the mismatch between passenger flow and section capacity, the entire network is in disequilibrium. At the system level, this is an uncontrollable state. To maintain the system in a state of controllability, corresponding flow control measures are taken to reduce flow aggregation.During thet+Δt statistical period, Pi(t+Δt) is the number of passengers in station i of the line and is equivalent to the number of people in the station plus the difference between people inbound and outbound plus the difference in transfer passenger flow, which can be shown as follows:(6)Pit+Δt=Pit+Ait-Dit+Iit-Oit∀t>0;where Pi(t) is the passenger flow of station i during period t; Ai(t) is the number of passengers inbound i during period t; Di(t) is the number of passengers outbound i during period t; Ii(t) is the transfer passenger inflow of station i during period t; Oi(t) is the transfer passenger outflow of station i during period t.Passenger flow control is mainly the control of inbound passengers. There is no fundamental reduction in passenger demand, and the distribution of passenger flow demand is adjusted. The passenger flow of the network achieves a relatively stable state of time and space distribution.


#### 2.2.3. Controllability Determination Model of the Urban Rail Transit Network

According to the urban rail transit network topology and passenger flow characteristics, the controllable model of the urban rail transit network is presented in(7)x˙t=∑i=1n∑j=1naijtxit+∑i=1n∑j=1mbijtujtm≤nwhere aij(t) is the element of state matrix a in time t, j is the origination station, and i is the destination station. aij(t) is the number of passengers from j to i in time t. Iij(t) is the number of passengers from j to i in time t. When Iij(t)>k, aij=1; Iij(t)<k, aij(t)=Iij(t)/k, ∀aij(t)∈[0,1].x i ( t ) is the passenger flow state level of station j in time t. According to the national standard subway design specification (GB50157-2013) of China and the Transit Capacity and Quality of Service Manual (2nd Edition) of TCRP, a single facility is divided into four levels (Table 1).Table 1
Facility equipment passenger flow risk rating scale.
Passenger flow status level Passenger flow state Platform Passage Check-in area Per capita area/m2 Average queue length/m Flow density (p/m2) Average speed (m/min) Unit width flow rate (p/m/min) Per capita area(m2/p) Average queue number Speed (m/s) A Severe congestion ≤0.2 ≥3/4d ≥1.6 ≤47 Indefinite ≤0.2 ≥20 Indefinite B Congestion 0.2-0.3 1/2d-3/4d 1.1-1.6 47-69 65-81 0.2-0.3 13-20 0.3-0.5 C More smooth 0.3-0.7 1/4d-1/2d 0.7-1.1 69-76 49-65 0.3-0.7 1-13 0.5-1.33 D Unobstructed ≥0.7 ≤1/4d ≤0.7 ≥76 ≤49 ≥0.7 ≤1 ≥1.33Based on the congestion risk assessment standard for Beijing urban rail transit stations, the risk level is classified as heightened risk, high risk, general risk, and risk free according to the evaluation score. Given the limited and unobstructed equipment and facilities, the risk level has little effect on passenger travel and station operation and is not the basis for classifying the risk rating. Therefore, the congestion level of the whole station can be obtained from the number of survey points, such as platforms, passages, security, up and down staircases, and entrances. The specific principles are as follows:(A.1) If there are more than 5 A or 8 B, the station is classified as a high-risk station (I level).(A.2) If there are 2-5 A or 5-8 B, the station is classified as a heightened-risk station (II level).(A.3) If there are 1-2 A or 1-5 B, the station is classified as a general-risk station (III level).(A.4) If there are 0 A or 0 B, the station is classified as a risk-free station (IV level).According to the overall congestion risk assessment results, the value ofxi(t) is 1, 2, 3, 4.b i j ( t ) is the element of input matrix b in time t and corresponds to the number of flow control stations. If the station implements flow control measures in timet, bij(t)=1; otherwise, bij(t)=0.u j ( t ) is the flow control intensity of station j in time t, ∀uj(t)∈[0,1]. The flow control intensity of the station represents the ratio of the passenger flow in the station to the actual passenger flow demand per unit time. The larger the flow control rate is, the larger the flow control intensity is.The Kalman controllability rank is used to determine the condition. The determination model of the controllability of the urban rail transit network is given by(8)rankc=b,ab,a2b,......,an-1bIfrank(c)=n, the passenger flow network of urban rail transit is controllable. If rank(c)<n, the passenger flow network of urban rail transit is uncontrollable.


## 2.1. Basic Indicators of the Passenger Flow Network

The model of the passenger flow network must be built based on the rail infrastructure line. We define the station as a node and the rail connecting two adjacent stations as an edge. The nodes and edges constitute a physical network of urban rail transit. We then superimpose passenger flow on the orbital transport physical network, which can be extended to a passenger flow network of urban rail transit. The station is defined as a node of the network. If there is passenger flow between two stations, there is an edge between the two stations. The transferred passenger flow is the weight of the edge. This is the passenger flow network of urban rail transit.A complex network generally has a high number of nodes, a large degree of distribution, high concentration, and so on. The passenger flow has the characteristic of strong fluidity. Therefore, the whole network cannot be controlled effectively solely by determining the flow control node from the aggregation number of passenger flow. This paper analyzes the basic indices of the passenger flow network, thus laying the foundation for study of the controllability of the passenger flow network.(  1) Degree. The degree is defined as the number of connections between node i and other nodes. The greater the degree is, the more connections between nodes and the more important the nodes are in the network. The degree is given by(1)ki=∑i≤jnijwhere nij is a variable from 0 to 1 representing the connection between nodes.The degree value of the passenger flow network of urban rail transit reflects the accessibility of network nodes. A larger value indicates more transfer choices for a station. Conversely, a smaller degree value indicates weaker accessibility of a station. Passengers may need to make a high number of transfers before arriving at their destination.(  2) Node Strength. If wij is the connection weight of nodes i and j, the node strength Si of network node i is defined by(2)Si=∑i=1n∑j=1nwijThe node strength is the sum of the node weights. The node strength of the passenger flow network of urban rail transit reflects the passenger demand of the station. The greater the node strength is, the larger the passenger flow of the station is.(  3) Clustering Coefficient. The clustering coefficient reflects the node aggregation of the network. It assumes that the number of connection edges of node i is ki. The maximum number of edges of node number ki is ki(ki-1)/2. The clustering coefficient Ci of node i is defined as follows:(3)Ci=2Eikiki-1The clustering coefficient of the urban rail transit network reflects the connection of transfer passenger flow between stations. The larger the aggregation coefficient is, the higher the connection degree between stations is.(  4) Average Path Length of the Network. Distance dij between nodes i and j is defined as the number of edges of the shortest path between two nodes. The average path length of network L is defined as follows:(4)L=11/2NN-1∑dijwhere N is the number of network nodes.The average path length of the urban rail transit passenger network reflects the number of passing stations from the origin to the destination. This parameter is an indicator of the connectivity of the passenger flow network of urban rail transit.


## 2.2. Controllability Determination Method of the Passenger Flow Network

### 2.2.1. System Controllable Determination Theory

If there is a segmented continuous inputu(t), the system can proceed from an initial state x(t0) to any specified terminal state x(tf) in a finite time interval [t0,tf]. It is then said that the state is controllable. If all states of the system are controllable, it is said that the system is fully controllable.The input-output model of a linear time-invariant system can be represented as follows [27]:(5)x˙=Axt+Butwhere the vector x(t)=(x1(t),......,xN(t))T captures the state of a system of N nodes at time t.The input signalu(t)=(u1(t),...,uM(t))T,M≤N.A is the state matrix: A∈RN×N.B is the input matrix: B∈RN×M.The controllability determination model of an urban rail transit passenger flow network belongs to the linear time-invariance system model. The model has two properties: linear and time invariance. The objective of this paper is to optimize the flow control of the urban rail transit network. In this paper, the time interval of flow control of the passenger flow network is discretized. In subdivided period, the topology link of the passenger flow network is invariant. Therefore, the passenger flow network system in one time interval is constant. Second, the input of the system is the set of flow control stations. The network state is the result of the interaction among flow control stations. Therefore, the optimization of flow control of the urban rail transit network in this paper satisfies additivity.


### 2.2.2. Controllability Analysis of the Passenger Flow Network of Urban Rail Transit

After the network operation of rail transit, the change and rule of passenger flow are more complicated than those of the single or simple network structures due to the greater number of flow and transfer opportunities. An urban rail transit network is a control system. The external flow control measures are the input signals, and the OD passenger flows of the network are the state variables. Under normal conditions, urban rail transit networks are within the controllable range. However, in the morning and evening peak hours or under large passenger flow conditions, due to the reduced levels of path service and the mismatch between passenger flow and section capacity, the entire network is in disequilibrium. At the system level, this is an uncontrollable state. To maintain the system in a state of controllability, corresponding flow control measures are taken to reduce flow aggregation.During thet+Δt statistical period, Pi(t+Δt) is the number of passengers in station i of the line and is equivalent to the number of people in the station plus the difference between people inbound and outbound plus the difference in transfer passenger flow, which can be shown as follows:(6)Pit+Δt=Pit+Ait-Dit+Iit-Oit∀t>0;where Pi(t) is the passenger flow of station i during period t; Ai(t) is the number of passengers inbound i during period t; Di(t) is the number of passengers outbound i during period t; Ii(t) is the transfer passenger inflow of station i during period t; Oi(t) is the transfer passenger outflow of station i during period t.Passenger flow control is mainly the control of inbound passengers. There is no fundamental reduction in passenger demand, and the distribution of passenger flow demand is adjusted. The passenger flow of the network achieves a relatively stable state of time and space distribution.


### 2.2.3. Controllability Determination Model of the Urban Rail Transit Network

According to the urban rail transit network topology and passenger flow characteristics, the controllable model of the urban rail transit network is presented in(7)x˙t=∑i=1n∑j=1naijtxit+∑i=1n∑j=1mbijtujtm≤nwhere aij(t) is the element of state matrix a in time t, j is the origination station, and i is the destination station. aij(t) is the number of passengers from j to i in time t. Iij(t) is the number of passengers from j to i in time t. When Iij(t)>k, aij=1; Iij(t)<k, aij(t)=Iij(t)/k, ∀aij(t)∈[0,1].x i ( t ) is the passenger flow state level of station j in time t. According to the national standard subway design specification (GB50157-2013) of China and the Transit Capacity and Quality of Service Manual (2nd Edition) of TCRP, a single facility is divided into four levels (Table 1).Table 1
Facility equipment passenger flow risk rating scale.
Passenger flow status level Passenger flow state Platform Passage Check-in area Per capita area/m2 Average queue length/m Flow density (p/m2) Average speed (m/min) Unit width flow rate (p/m/min) Per capita area(m2/p) Average queue number Speed (m/s) A Severe congestion ≤0.2 ≥3/4d ≥1.6 ≤47 Indefinite ≤0.2 ≥20 Indefinite B Congestion 0.2-0.3 1/2d-3/4d 1.1-1.6 47-69 65-81 0.2-0.3 13-20 0.3-0.5 C More smooth 0.3-0.7 1/4d-1/2d 0.7-1.1 69-76 49-65 0.3-0.7 1-13 0.5-1.33 D Unobstructed ≥0.7 ≤1/4d ≤0.7 ≥76 ≤49 ≥0.7 ≤1 ≥1.33Based on the congestion risk assessment standard for Beijing urban rail transit stations, the risk level is classified as heightened risk, high risk, general risk, and risk free according to the evaluation score. Given the limited and unobstructed equipment and facilities, the risk level has little effect on passenger travel and station operation and is not the basis for classifying the risk rating. Therefore, the congestion level of the whole station can be obtained from the number of survey points, such as platforms, passages, security, up and down staircases, and entrances. The specific principles are as follows:(A.1) If there are more than 5 A or 8 B, the station is classified as a high-risk station (I level).(A.2) If there are 2-5 A or 5-8 B, the station is classified as a heightened-risk station (II level).(A.3) If there are 1-2 A or 1-5 B, the station is classified as a general-risk station (III level).(A.4) If there are 0 A or 0 B, the station is classified as a risk-free station (IV level).According to the overall congestion risk assessment results, the value ofxi(t) is 1, 2, 3, 4.b i j ( t ) is the element of input matrix b in time t and corresponds to the number of flow control stations. If the station implements flow control measures in timet, bij(t)=1; otherwise, bij(t)=0.u j ( t ) is the flow control intensity of station j in time t, ∀uj(t)∈[0,1]. The flow control intensity of the station represents the ratio of the passenger flow in the station to the actual passenger flow demand per unit time. The larger the flow control rate is, the larger the flow control intensity is.The Kalman controllability rank is used to determine the condition. The determination model of the controllability of the urban rail transit network is given by(8)rankc=b,ab,a2b,......,an-1bIfrank(c)=n, the passenger flow network of urban rail transit is controllable. If rank(c)<n, the passenger flow network of urban rail transit is uncontrollable.


## 2.2.1. System Controllable Determination Theory

If there is a segmented continuous inputu(t), the system can proceed from an initial state x(t0) to any specified terminal state x(tf) in a finite time interval [t0,tf]. It is then said that the state is controllable. If all states of the system are controllable, it is said that the system is fully controllable.The input-output model of a linear time-invariant system can be represented as follows [27]:(5)x˙=Axt+Butwhere the vector x(t)=(x1(t),......,xN(t))T captures the state of a system of N nodes at time t.The input signalu(t)=(u1(t),...,uM(t))T,M≤N.A is the state matrix: A∈RN×N.B is the input matrix: B∈RN×M.The controllability determination model of an urban rail transit passenger flow network belongs to the linear time-invariance system model. The model has two properties: linear and time invariance. The objective of this paper is to optimize the flow control of the urban rail transit network. In this paper, the time interval of flow control of the passenger flow network is discretized. In subdivided period, the topology link of the passenger flow network is invariant. Therefore, the passenger flow network system in one time interval is constant. Second, the input of the system is the set of flow control stations. The network state is the result of the interaction among flow control stations. Therefore, the optimization of flow control of the urban rail transit network in this paper satisfies additivity.


## 2.2.2. Controllability Analysis of the Passenger Flow Network of Urban Rail Transit

After the network operation of rail transit, the change and rule of passenger flow are more complicated than those of the single or simple network structures due to the greater number of flow and transfer opportunities. An urban rail transit network is a control system. The external flow control measures are the input signals, and the OD passenger flows of the network are the state variables. Under normal conditions, urban rail transit networks are within the controllable range. However, in the morning and evening peak hours or under large passenger flow conditions, due to the reduced levels of path service and the mismatch between passenger flow and section capacity, the entire network is in disequilibrium. At the system level, this is an uncontrollable state. To maintain the system in a state of controllability, corresponding flow control measures are taken to reduce flow aggregation.During thet+Δt statistical period, Pi(t+Δt) is the number of passengers in station i of the line and is equivalent to the number of people in the station plus the difference between people inbound and outbound plus the difference in transfer passenger flow, which can be shown as follows:(6)Pit+Δt=Pit+Ait-Dit+Iit-Oit∀t>0;where Pi(t) is the passenger flow of station i during period t; Ai(t) is the number of passengers inbound i during period t; Di(t) is the number of passengers outbound i during period t; Ii(t) is the transfer passenger inflow of station i during period t; Oi(t) is the transfer passenger outflow of station i during period t.Passenger flow control is mainly the control of inbound passengers. There is no fundamental reduction in passenger demand, and the distribution of passenger flow demand is adjusted. The passenger flow of the network achieves a relatively stable state of time and space distribution.


## 2.2.3. Controllability Determination Model of the Urban Rail Transit Network

According to the urban rail transit network topology and passenger flow characteristics, the controllable model of the urban rail transit network is presented in(7)x˙t=∑i=1n∑j=1naijtxit+∑i=1n∑j=1mbijtujtm≤nwhere aij(t) is the element of state matrix a in time t, j is the origination station, and i is the destination station. aij(t) is the number of passengers from j to i in time t. Iij(t) is the number of passengers from j to i in time t. When Iij(t)>k, aij=1; Iij(t)<k, aij(t)=Iij(t)/k, ∀aij(t)∈[0,1].x i ( t ) is the passenger flow state level of station j in time t. According to the national standard subway design specification (GB50157-2013) of China and the Transit Capacity and Quality of Service Manual (2nd Edition) of TCRP, a single facility is divided into four levels (Table 1).Table 1
Facility equipment passenger flow risk rating scale.
Passenger flow status level Passenger flow state Platform Passage Check-in area Per capita area/m2 Average queue length/m Flow density (p/m2) Average speed (m/min) Unit width flow rate (p/m/min) Per capita area(m2/p) Average queue number Speed (m/s) A Severe congestion ≤0.2 ≥3/4d ≥1.6 ≤47 Indefinite ≤0.2 ≥20 Indefinite B Congestion 0.2-0.3 1/2d-3/4d 1.1-1.6 47-69 65-81 0.2-0.3 13-20 0.3-0.5 C More smooth 0.3-0.7 1/4d-1/2d 0.7-1.1 69-76 49-65 0.3-0.7 1-13 0.5-1.33 D Unobstructed ≥0.7 ≤1/4d ≤0.7 ≥76 ≤49 ≥0.7 ≤1 ≥1.33Based on the congestion risk assessment standard for Beijing urban rail transit stations, the risk level is classified as heightened risk, high risk, general risk, and risk free according to the evaluation score. Given the limited and unobstructed equipment and facilities, the risk level has little effect on passenger travel and station operation and is not the basis for classifying the risk rating. Therefore, the congestion level of the whole station can be obtained from the number of survey points, such as platforms, passages, security, up and down staircases, and entrances. The specific principles are as follows:(A.1) If there are more than 5 A or 8 B, the station is classified as a high-risk station (I level).(A.2) If there are 2-5 A or 5-8 B, the station is classified as a heightened-risk station (II level).(A.3) If there are 1-2 A or 1-5 B, the station is classified as a general-risk station (III level).(A.4) If there are 0 A or 0 B, the station is classified as a risk-free station (IV level).According to the overall congestion risk assessment results, the value ofxi(t) is 1, 2, 3, 4.b i j ( t ) is the element of input matrix b in time t and corresponds to the number of flow control stations. If the station implements flow control measures in timet, bij(t)=1; otherwise, bij(t)=0.u j ( t ) is the flow control intensity of station j in time t, ∀uj(t)∈[0,1]. The flow control intensity of the station represents the ratio of the passenger flow in the station to the actual passenger flow demand per unit time. The larger the flow control rate is, the larger the flow control intensity is.The Kalman controllability rank is used to determine the condition. The determination model of the controllability of the urban rail transit network is given by(8)rankc=b,ab,a2b,......,an-1bIfrank(c)=n, the passenger flow network of urban rail transit is controllable. If rank(c)<n, the passenger flow network of urban rail transit is uncontrollable.


## 3. Optimization Method of Flow Control of an Urban Rail Transit Network

### 3.1. Optimization Graph Method of Network Structure

In complex network control, Liu [12] proposed a network control method based on minimizing node ND. The simulation results showed that the number of driver nodes is mainly determined by the degree distribution of the network. Sparse heterogeneous networks tend to be more difficult to control, while dense homogeneous networks require fewer driver nodes to be controlled. Sparsity means that the average degree of the network is much smaller than the maximum possible connectivity N (number of network nodes), such as in an urban rail transit network. A heterogeneous network considers not only the topology structure but also the attribute information of nodes and edges in the network.Combining the network structure with graph theory, the matching method of the node and edge is used to determine whether the network can be controlled. If the input signal can reach all paths by input signalsu1,u2, and u3, the system is controllable (Figure 1). How can an uncontrollable network be converted into a controllable network, and how can the minimum input signal be determined? This is a matching problem. The nodes in the network can be matched by the binary graph method. A matching edge means that any two directed edges do not have a common vertex (head or tail node). The matching node is the head node of the matching edge.Figure 1
Schematic diagram of a controllable network.The determination of the minimum input for a directed network can be converted to a maximum matching problem to solve the network (Figure2). According to the system structure (Figure 2(a)), the edges between nodes correspond to state matrix A in the equation (Figure 2(b)).Figure 2
Schematic diagram of uncontrollable system structure.
(a) (b)


### 3.2. Optimization Method of Flow Control Based on Driver Node Matching

In this paper, the driver node matching method is improved based on the Hopcroft–Karp algorithm [28]. If there is no shared head node or tail node on all edges of the network, the network achieves maximum matching. If the network does not match exactly, the value of the driver node ND is equal to the number of nonmatching nodes. For a nonmatching node, a given input signal can reach all matching nodes to control the entire network. Even with different initial searches of matched edges, the number of minimum driver nodes is fixed. For the network of rail transit passenger flow, it is necessary to identify the driver nodes of the flow control station to optimize the passenger flow network and enable network control.This paper proposes an optimization method of flow control based on driver node matching according to the network topology and the passenger flow characteristics of urban rail transit. The method is described as follows.The method defines an urban rail transit networkG=(V,E), where V is the station set; E is the section of flow transfer; Iij is the passenger flow from stationjto station i; xik is the degree value k of station i; Ai is the passenger flow entering the station; P is the degree threshold; Q is the threshold of passenger flow; and W is the passenger flow threshold entering the station. If Vcan be divided into two mutually disjoint subsets (A,B), the two nodes associated with each edge of the network belong to the two different subsets (A,B). G=(V,E) is then converted to a bipartite graph D(V)=(AV+,AV-,Γ), where AV+={x1+,x1+,....,xN+}, AV-={x1-,x1-,....,xN-}, and Γ={(xj-,xi-)∣aij≠0} represent the edge set.Step 1.
Select an initial matching edgeEi; i fall vertices of V are matched by M, then M is completely matched; return. This result indicates that the network is currently under control. Otherwise, a breadth-first search is performed for all unmatched vertices as the source, and the distance from each node to the source node is marked.Step 2.
Find the vertexx0 unmatched byM; that is xik≥p, and mark S=x0,Γ=⊄.Step 3.
IfN(S)=Γ, there is no greater match; return. Otherwise, x0′∈N(S).Step 4.
Ifx0′ is matched byM, go to Step 6. Otherwise, form an augment path P(x0,x0′), P(x0,x0′)∈M, M=MΔP(x0,x0′). Priority is given to the adjacent nodes connected to x0, which has a large value of integrated index values in the nodes, including the nodes of Iij≥Q and Ai≥W.Step 5.
Sincex0′ has been matched by M, there is an edge (x0′,x0′′) of M,S=S∪x0′′,Γ=Γ∪x0′; go to Step 1.Step 6.
Determine whether the driver node is a transfer node; if it is, keep the connected transfer node.Step 7.
IfND>minND, delete the head node of passenger flow that is larger or equal to Q and smaller than (Q+d1), deleted by d1successive iterations. Delete the node for which passenger flow entering the station is smaller than W, deleted byd2 successive iterations. When ND=minND, a new set of flow control stations is generated.The above search process occurs in a period oft. With the implementation of the flow control strategy and the decrease in passenger flow, the above process can be repeated. Reducing or replacing the current flow control node can formulate the flow control program for subpeak conditions.


## 3.1. Optimization Graph Method of Network Structure

In complex network control, Liu [12] proposed a network control method based on minimizing node ND. The simulation results showed that the number of driver nodes is mainly determined by the degree distribution of the network. Sparse heterogeneous networks tend to be more difficult to control, while dense homogeneous networks require fewer driver nodes to be controlled. Sparsity means that the average degree of the network is much smaller than the maximum possible connectivity N (number of network nodes), such as in an urban rail transit network. A heterogeneous network considers not only the topology structure but also the attribute information of nodes and edges in the network.Combining the network structure with graph theory, the matching method of the node and edge is used to determine whether the network can be controlled. If the input signal can reach all paths by input signalsu1,u2, and u3, the system is controllable (Figure 1). How can an uncontrollable network be converted into a controllable network, and how can the minimum input signal be determined? This is a matching problem. The nodes in the network can be matched by the binary graph method. A matching edge means that any two directed edges do not have a common vertex (head or tail node). The matching node is the head node of the matching edge.Figure 1
Schematic diagram of a controllable network.The determination of the minimum input for a directed network can be converted to a maximum matching problem to solve the network (Figure2). According to the system structure (Figure 2(a)), the edges between nodes correspond to state matrix A in the equation (Figure 2(b)).Figure 2
Schematic diagram of uncontrollable system structure.
(a) (b)


## 3.2. Optimization Method of Flow Control Based on Driver Node Matching

In this paper, the driver node matching method is improved based on the Hopcroft–Karp algorithm [28]. If there is no shared head node or tail node on all edges of the network, the network achieves maximum matching. If the network does not match exactly, the value of the driver node ND is equal to the number of nonmatching nodes. For a nonmatching node, a given input signal can reach all matching nodes to control the entire network. Even with different initial searches of matched edges, the number of minimum driver nodes is fixed. For the network of rail transit passenger flow, it is necessary to identify the driver nodes of the flow control station to optimize the passenger flow network and enable network control.This paper proposes an optimization method of flow control based on driver node matching according to the network topology and the passenger flow characteristics of urban rail transit. The method is described as follows.The method defines an urban rail transit networkG=(V,E), where V is the station set; E is the section of flow transfer; Iij is the passenger flow from stationjto station i; xik is the degree value k of station i; Ai is the passenger flow entering the station; P is the degree threshold; Q is the threshold of passenger flow; and W is the passenger flow threshold entering the station. If Vcan be divided into two mutually disjoint subsets (A,B), the two nodes associated with each edge of the network belong to the two different subsets (A,B). G=(V,E) is then converted to a bipartite graph D(V)=(AV+,AV-,Γ), where AV+={x1+,x1+,....,xN+}, AV-={x1-,x1-,....,xN-}, and Γ={(xj-,xi-)∣aij≠0} represent the edge set.Step 1.
Select an initial matching edgeEi; i fall vertices of V are matched by M, then M is completely matched; return. This result indicates that the network is currently under control. Otherwise, a breadth-first search is performed for all unmatched vertices as the source, and the distance from each node to the source node is marked.Step 2.
Find the vertexx0 unmatched byM; that is xik≥p, and mark S=x0,Γ=⊄.Step 3.
IfN(S)=Γ, there is no greater match; return. Otherwise, x0′∈N(S).Step 4.
Ifx0′ is matched byM, go to Step 6. Otherwise, form an augment path P(x0,x0′), P(x0,x0′)∈M, M=MΔP(x0,x0′). Priority is given to the adjacent nodes connected to x0, which has a large value of integrated index values in the nodes, including the nodes of Iij≥Q and Ai≥W.Step 5.
Sincex0′ has been matched by M, there is an edge (x0′,x0′′) of M,S=S∪x0′′,Γ=Γ∪x0′; go to Step 1.Step 6.
Determine whether the driver node is a transfer node; if it is, keep the connected transfer node.Step 7.
IfND>minND, delete the head node of passenger flow that is larger or equal to Q and smaller than (Q+d1), deleted by d1successive iterations. Delete the node for which passenger flow entering the station is smaller than W, deleted byd2 successive iterations. When ND=minND, a new set of flow control stations is generated.The above search process occurs in a period oft. With the implementation of the flow control strategy and the decrease in passenger flow, the above process can be repeated. Reducing or replacing the current flow control node can formulate the flow control program for subpeak conditions.


## 4. Case Study

### 4.1. Analysis of the Characteristics of the Beijing Urban Rail Transit Network

Based on the train operation schedule and passenger flow data for Beijing urban rail transit in 2015, we extract the connections between stations in the urban rail transit passenger network. The Beijing urban rail transit passenger flow network has 269 stations and 18860 edges, and the average degree is 70.1.The degree distribution of the passenger flow network of Beijing urban rail transit is shown in Figure3(a). The number of stations is high for degree values of 24, 36, 44, 68, and 88. Most stations have low and relatively concentrated distributions, and 90% of the node values are within 100. Based on the cumulative degree distribution shown in Figure 3(b), the Beijing urban rail transit network is more consistent with the power law distribution and is thus a scale-free network. The station strength indirectly reflects the service capacity of the station. The cumulative strength distribution for the Beijing urban rail transit passenger flow network is shown in Figure 3(c). According to the statistics, 4.5% of the station strength is greater than 15 000, and 88.2% of the station strength is smaller than 10 000. These results indicate that the intensity distribution of the station node is extremely uneven. The stations carrying large passenger flow are usually transfer nodes, which enhances the accessibility of the network. The average clustering coefficient of the Beijing urban rail transit network is calculated to be 0.563, indicating high clustering. The cumulative distribution of the clustering coefficient for the Beijing urban rail transit passenger flow network is shown in Figure 3(d). Each station has a high connection degree with adjacent stations. When the clustering coefficient of the station is 1, the station has a low degree value. Therefore, the relationship between the degree value and the clustering coefficient is negative. The average distance of the urban rail transit network indirectly reflects the transfer times of passengers. The shortest distance distribution of the Beijing urban rail transit passenger flow network is shown in Figure 3(e). The average shortest path length of the passenger flow network is 1.69. Thus, passengers reach their destinations on average by 1.69 times. The transfer rate is up to 84% within three times.Figure 3
Characteristics of the Beijing urban rail transit passenger flow network.
(a)
Degree distribution (b)
Cumulative degree distribution (c)
Cumulative strength distribution (d)
Cumulative distribution of the clustering coefficient (e)
Shortest-distance distribution


### 4.2. Controllability of a Simple Passenger Flow Network

In this paper, we selected a small network of the Beijing subway in 2015 to verify the controllability of the network structure. We do not consider the volume of passenger flow. An edge is defined if there is passenger flow between stations.We selected the Dongdan and Jianguomen stations of line 1, the Beijing railway station of line 2, and the Chongwenmen station of line 5 (Figure4(a)). The passenger flow network of the four stations is converted into a binary graph (Figure 4(b)). v1+ and v1- are the Dongdan station; v2+ and v2- are the Jianguomen station; v3+ and v3- are the Chongwenmen station; and v4+ and v4- are the Beijing railway station. The arrow represents the direction of passenger flow. In this case, we consider only unidirectional passenger flow. The maximum matching edge of this small network is shown as the red matching edge in the binary graph (Figure 4(c)). According to the results of the maximum matching edge, v1,v2,v3, and v4 are the matching nodes of the network. The number of nonmatching nodes is 0, and the driver node ND is 0.Figure 4
Example of method for determining the controllability of the local passenger flow network.
(a) (b) (c) (d) (e) (f) (g) (h) (i)We selected the Tiantongyuanbei, Tiantongyuan, Tiantongyuannan, and Lishuiqiao stations of line 5 of the Beijing subway (Figure4(d)). The passenger flow network of the four station nodes is converted into a binary graph (Figure 4(e)). The maximum matching edge of this small network is shown as the red matching edge in the binary graph (Figure 4(f)). v2,v3, and v4 are the matching nodes, and v1 is the nonmatching node. Therefore, the driver node ND is v1.We selected the Junshibowuguan and Wanshoulu stations of line 1 and the Xidiaoyutai, Gongzhufeng, and Lianhuaqiao stations of line 10 of the Beijing subway (Figure4(g)). The passenger flow network of the five station nodes is converted into a binary graph (Figure 4(h)). The maximum matching edge of this small network is shown as the red matching edge in the binary graph (Figure 4(i)). v2,v3, and v5 are the matching nodes, and v1 and v4 are the nonmatching nodes. Therefore, the driver nodes ND are v1 and v4.The example shows that there is no cross road loop or straight line and that there are relatively few required driver nodes. Trifurcated and cross structures are very common among subway passenger flow networks. These structures usually have a high number of nonmatching nodes and require a high number of driver nodes.


### 4.3. Controllability Example for a Passenger Flow Network of Beijing Urban Rail Transit

The Beijing subway had 18 operational lines (including 17 lines and 1 airport line) in 2015. There were 315 stations, including the repeated calculation for transfer stations, except terminal 2 and terminal 3 (269 stations, excluding the repeated calculation for transfer stations).Each station of the network is numbered by line, for example, line 1: Pingguoyuan 0101, Gucheng 0102, Bajiaoyouleyuan 0103, Babaoshan 0104, Yuquanlu 0105, Wukesong 0106; line 2: Xizhimen 0201, Chegongzhuang 0202, Fuchengmen 0203, etc. The first two digits are the line number, and the last two are the station number, as shown in Table2.Table 2
Information for the Beijing Urban Railway Network.
Line Line number Number of stations Station number Line 1 01 23 0101-0123 Line 2 02 18 0201-0218 Line 4/Daxing line 04 35 0401-0435 Line 5 05 23 0501-0523 Line 6 06 26 0601-0626 Line 7 07 19 0701-0719 Line 8 08 17 0801-0817 Line 9 09 13 0901-0913 Line 10 10 45 1001-1045 Line 13 13 16 1301-1316 Line 14 14 17 1401-1417 Line 15 15 19 1501-1519 Batong line 16 13 1601-1613 Fangshan line 17 11 1701-1711 Changping line 18 7 1801-1807 Yizhuang line 19 13 1901-1913The edges between nodes are directed, and the direction is the same as the transport direction of passenger flow. The passenger flow data used in this case are the early peak passenger flow data of the Beijing subway network on December 14, 2015. According to the passenger flow OD data, the state matrixais 18 860∗18 860.(9)a=065178137⋯⋯05104849⋯⋯884715016114⋯457746310158⋯53⋮⋮⋮⋯⋱⋮⋮⋮⋮⋮⋯⋯⋱⋮013246133⋯⋯0Based on the comparison of the passenger flow OD data for the early peak (7:00-9:00) and ordinary periods, we selected a thresholdk of 69. The matrix can be transformed as shown below:(10)a=00.9411⋯⋯00.7400.700.71⋯⋯10.680.2200.231⋯0.6510.670.4501⋯0.77⋮⋮⋮⋯⋱⋮⋮⋮⋮⋮⋯⋯⋱⋮010.671⋯⋯0Matrixb is an input matrix that consists of flow control stations. The flow control stations are shown in Table 3. The matrix removes the evening peak flow control stations, such as Wudaokou, Liangmaqiao, Jintaixizhao, Chaoyangmen, Fuxingmen, Yonganli, Fengtaikejiyuan, and Dongwuyuan. (11)b=100⋯⋯00010⋯⋯0000⋱⋮⋮⋮⋮⋮⋱10⋮⋮⋮⋱00000⋯⋯00000⋯⋯01Table 3
Information on Beijing Urban Railway passenger control stations.
Line Flow control stations Line 1 Sihuidong, Gucheng, Pingguoyuan, Sihui, Babaoshan, Bajiaoyouleyuan, Gongzhufeng, Fuxingmen, Yonganli Batong line Chuanmeidaxue, Shuangqiao, Guanzhuang, Baliqiao, Tongzhoubeiyuan, Guoyuan, Jiukeshu, Liyuan Line 2 Chaoyangmen Line 4 Gongyixiqiao, Jiaomenxi, Beijingnan, Xuanwumen, Dongwuyuan Line 5 Tiantongyuanbei, Tiantongyuan, Tiantongyuannan, Lishuiqiao, Lishuiqiaonan, Beiyuanlubei, Datunludong, Ciqikou, Huixinxijiebeikou, Huixinxijienankou, Puhuangyu, Dongdan, Tiantandongmen, Liujiayao, Songjiazhuang Line 6 Hujialou, Jintailu, Shilipu, Qingnianlu, Talianpo, Huangqu, Changying, Caofang, Wuzixueyuanlu Line 7 Ciqikou Line 9 Beijingxizhan, Liuliqiaodong, Fengtaikejiyuan Line 10 Jinsong, Shuangjing, Liangmaqiao, Sanyuanqiao, Guomao, Jintaixizhao Line 13 Shangdi, Huoying, Huilongguan, Longze, Wudaokou Line 14 Jintailu Changping line Xierqi, Zhuxinzhuang, Shengmingkexueyuan, Shahe, Shahegaojiaoyuan, Nanshao Yizhuang line Jiugong Daxing line XihongmenAccording to Kalman’s controllable rank determination, the rank(c)=12365. This value indicates that the system is uncontrollable. The subway network has a large number of transfer stations. Because the transfer stations connect two or more lines, there are more nonmatching nodes around transfer stations according to the maximum matching theory. The number of driver nodes is insufficient, and the network is uncontrollable.In this paper, an optimization method for flow control based on driver nodes is proposed to optimize an uncontrollable passenger flow network. The ratio of driver nodes to the nodes during early peak is shown in Figure5.Figure 5
Ratio of driver nodes to nodes of a controllable passenger flow network.When the ratio of driver nodes is close to 0.253, the number of driver nodes is 65, and the Beijing urban rail transit network is controllable during early peak. From the perspective of network controllability, it is suggested that the Beijing urban rail transit increase the number of driver nodes to improve controllability and optimize the flow control strategy.We attempt to retain the original finite-flow station during the entire deletion process, and the updated topology diagram of flow control stations in Beijing urban rail transit is shown in Figure6.Figure 6
Control stations of Beijing urban rail transit under the network controllability condition.The resulting flow control scheme is shown in Figure6. The three red nodes are the newly added flow control stations: Jianguomen, Chongwenmen, and Xizhimen. The two blue nodes are the original flow control stations that were deleted.The newly added flow control stations are transfer stations that have 4 or 5 degrees. These transfer stations have large passenger flow, and the internal structures are highly complicated. Among these stations, Xizhimen is a transfer station with three subway lines and, consequently, complicated transfer of passenger flow. Flow control can be implemented inside the station or in security. The proposed method in this paper is repeated. When the flow control measures are implemented after four time cycles, two flow control stations can be eliminated under the controllability condition: the Datunludong station and the Tiantandongmen station.The flow control stations are more concentrated in or near stations with large passenger flow. The flow control of nearby stations is also intended to relieve the station with large passenger flow. Current methods of flow control are restricted to experience. The flow control stations are basically fixed in the same time interval. With the implementation of flow control measures, the passenger flow of some stations is reduced. There may be a subpeak state, and the implementation of flow control measures should be a dynamic process.


## 4.1. Analysis of the Characteristics of the Beijing Urban Rail Transit Network

Based on the train operation schedule and passenger flow data for Beijing urban rail transit in 2015, we extract the connections between stations in the urban rail transit passenger network. The Beijing urban rail transit passenger flow network has 269 stations and 18860 edges, and the average degree is 70.1.The degree distribution of the passenger flow network of Beijing urban rail transit is shown in Figure3(a). The number of stations is high for degree values of 24, 36, 44, 68, and 88. Most stations have low and relatively concentrated distributions, and 90% of the node values are within 100. Based on the cumulative degree distribution shown in Figure 3(b), the Beijing urban rail transit network is more consistent with the power law distribution and is thus a scale-free network. The station strength indirectly reflects the service capacity of the station. The cumulative strength distribution for the Beijing urban rail transit passenger flow network is shown in Figure 3(c). According to the statistics, 4.5% of the station strength is greater than 15 000, and 88.2% of the station strength is smaller than 10 000. These results indicate that the intensity distribution of the station node is extremely uneven. The stations carrying large passenger flow are usually transfer nodes, which enhances the accessibility of the network. The average clustering coefficient of the Beijing urban rail transit network is calculated to be 0.563, indicating high clustering. The cumulative distribution of the clustering coefficient for the Beijing urban rail transit passenger flow network is shown in Figure 3(d). Each station has a high connection degree with adjacent stations. When the clustering coefficient of the station is 1, the station has a low degree value. Therefore, the relationship between the degree value and the clustering coefficient is negative. The average distance of the urban rail transit network indirectly reflects the transfer times of passengers. The shortest distance distribution of the Beijing urban rail transit passenger flow network is shown in Figure 3(e). The average shortest path length of the passenger flow network is 1.69. Thus, passengers reach their destinations on average by 1.69 times. The transfer rate is up to 84% within three times.Figure 3
Characteristics of the Beijing urban rail transit passenger flow network.
(a)
Degree distribution (b)
Cumulative degree distribution (c)
Cumulative strength distribution (d)
Cumulative distribution of the clustering coefficient (e)
Shortest-distance distribution


## 4.2. Controllability of a Simple Passenger Flow Network

In this paper, we selected a small network of the Beijing subway in 2015 to verify the controllability of the network structure. We do not consider the volume of passenger flow. An edge is defined if there is passenger flow between stations.We selected the Dongdan and Jianguomen stations of line 1, the Beijing railway station of line 2, and the Chongwenmen station of line 5 (Figure4(a)). The passenger flow network of the four stations is converted into a binary graph (Figure 4(b)). v1+ and v1- are the Dongdan station; v2+ and v2- are the Jianguomen station; v3+ and v3- are the Chongwenmen station; and v4+ and v4- are the Beijing railway station. The arrow represents the direction of passenger flow. In this case, we consider only unidirectional passenger flow. The maximum matching edge of this small network is shown as the red matching edge in the binary graph (Figure 4(c)). According to the results of the maximum matching edge, v1,v2,v3, and v4 are the matching nodes of the network. The number of nonmatching nodes is 0, and the driver node ND is 0.Figure 4
Example of method for determining the controllability of the local passenger flow network.
(a) (b) (c) (d) (e) (f) (g) (h) (i)We selected the Tiantongyuanbei, Tiantongyuan, Tiantongyuannan, and Lishuiqiao stations of line 5 of the Beijing subway (Figure4(d)). The passenger flow network of the four station nodes is converted into a binary graph (Figure 4(e)). The maximum matching edge of this small network is shown as the red matching edge in the binary graph (Figure 4(f)). v2,v3, and v4 are the matching nodes, and v1 is the nonmatching node. Therefore, the driver node ND is v1.We selected the Junshibowuguan and Wanshoulu stations of line 1 and the Xidiaoyutai, Gongzhufeng, and Lianhuaqiao stations of line 10 of the Beijing subway (Figure4(g)). The passenger flow network of the five station nodes is converted into a binary graph (Figure 4(h)). The maximum matching edge of this small network is shown as the red matching edge in the binary graph (Figure 4(i)). v2,v3, and v5 are the matching nodes, and v1 and v4 are the nonmatching nodes. Therefore, the driver nodes ND are v1 and v4.The example shows that there is no cross road loop or straight line and that there are relatively few required driver nodes. Trifurcated and cross structures are very common among subway passenger flow networks. These structures usually have a high number of nonmatching nodes and require a high number of driver nodes.


## 4.3. Controllability Example for a Passenger Flow Network of Beijing Urban Rail Transit

The Beijing subway had 18 operational lines (including 17 lines and 1 airport line) in 2015. There were 315 stations, including the repeated calculation for transfer stations, except terminal 2 and terminal 3 (269 stations, excluding the repeated calculation for transfer stations).Each station of the network is numbered by line, for example, line 1: Pingguoyuan 0101, Gucheng 0102, Bajiaoyouleyuan 0103, Babaoshan 0104, Yuquanlu 0105, Wukesong 0106; line 2: Xizhimen 0201, Chegongzhuang 0202, Fuchengmen 0203, etc. The first two digits are the line number, and the last two are the station number, as shown in Table2.Table 2
Information for the Beijing Urban Railway Network.
Line Line number Number of stations Station number Line 1 01 23 0101-0123 Line 2 02 18 0201-0218 Line 4/Daxing line 04 35 0401-0435 Line 5 05 23 0501-0523 Line 6 06 26 0601-0626 Line 7 07 19 0701-0719 Line 8 08 17 0801-0817 Line 9 09 13 0901-0913 Line 10 10 45 1001-1045 Line 13 13 16 1301-1316 Line 14 14 17 1401-1417 Line 15 15 19 1501-1519 Batong line 16 13 1601-1613 Fangshan line 17 11 1701-1711 Changping line 18 7 1801-1807 Yizhuang line 19 13 1901-1913The edges between nodes are directed, and the direction is the same as the transport direction of passenger flow. The passenger flow data used in this case are the early peak passenger flow data of the Beijing subway network on December 14, 2015. According to the passenger flow OD data, the state matrixais 18 860∗18 860.(9)a=065178137⋯⋯05104849⋯⋯884715016114⋯457746310158⋯53⋮⋮⋮⋯⋱⋮⋮⋮⋮⋮⋯⋯⋱⋮013246133⋯⋯0Based on the comparison of the passenger flow OD data for the early peak (7:00-9:00) and ordinary periods, we selected a thresholdk of 69. The matrix can be transformed as shown below:(10)a=00.9411⋯⋯00.7400.700.71⋯⋯10.680.2200.231⋯0.6510.670.4501⋯0.77⋮⋮⋮⋯⋱⋮⋮⋮⋮⋮⋯⋯⋱⋮010.671⋯⋯0Matrixb is an input matrix that consists of flow control stations. The flow control stations are shown in Table 3. The matrix removes the evening peak flow control stations, such as Wudaokou, Liangmaqiao, Jintaixizhao, Chaoyangmen, Fuxingmen, Yonganli, Fengtaikejiyuan, and Dongwuyuan. (11)b=100⋯⋯00010⋯⋯0000⋱⋮⋮⋮⋮⋮⋱10⋮⋮⋮⋱00000⋯⋯00000⋯⋯01Table 3
Information on Beijing Urban Railway passenger control stations.
Line Flow control stations Line 1 Sihuidong, Gucheng, Pingguoyuan, Sihui, Babaoshan, Bajiaoyouleyuan, Gongzhufeng, Fuxingmen, Yonganli Batong line Chuanmeidaxue, Shuangqiao, Guanzhuang, Baliqiao, Tongzhoubeiyuan, Guoyuan, Jiukeshu, Liyuan Line 2 Chaoyangmen Line 4 Gongyixiqiao, Jiaomenxi, Beijingnan, Xuanwumen, Dongwuyuan Line 5 Tiantongyuanbei, Tiantongyuan, Tiantongyuannan, Lishuiqiao, Lishuiqiaonan, Beiyuanlubei, Datunludong, Ciqikou, Huixinxijiebeikou, Huixinxijienankou, Puhuangyu, Dongdan, Tiantandongmen, Liujiayao, Songjiazhuang Line 6 Hujialou, Jintailu, Shilipu, Qingnianlu, Talianpo, Huangqu, Changying, Caofang, Wuzixueyuanlu Line 7 Ciqikou Line 9 Beijingxizhan, Liuliqiaodong, Fengtaikejiyuan Line 10 Jinsong, Shuangjing, Liangmaqiao, Sanyuanqiao, Guomao, Jintaixizhao Line 13 Shangdi, Huoying, Huilongguan, Longze, Wudaokou Line 14 Jintailu Changping line Xierqi, Zhuxinzhuang, Shengmingkexueyuan, Shahe, Shahegaojiaoyuan, Nanshao Yizhuang line Jiugong Daxing line XihongmenAccording to Kalman’s controllable rank determination, the rank(c)=12365. This value indicates that the system is uncontrollable. The subway network has a large number of transfer stations. Because the transfer stations connect two or more lines, there are more nonmatching nodes around transfer stations according to the maximum matching theory. The number of driver nodes is insufficient, and the network is uncontrollable.In this paper, an optimization method for flow control based on driver nodes is proposed to optimize an uncontrollable passenger flow network. The ratio of driver nodes to the nodes during early peak is shown in Figure5.Figure 5
Ratio of driver nodes to nodes of a controllable passenger flow network.When the ratio of driver nodes is close to 0.253, the number of driver nodes is 65, and the Beijing urban rail transit network is controllable during early peak. From the perspective of network controllability, it is suggested that the Beijing urban rail transit increase the number of driver nodes to improve controllability and optimize the flow control strategy.We attempt to retain the original finite-flow station during the entire deletion process, and the updated topology diagram of flow control stations in Beijing urban rail transit is shown in Figure6.Figure 6
Control stations of Beijing urban rail transit under the network controllability condition.The resulting flow control scheme is shown in Figure6. The three red nodes are the newly added flow control stations: Jianguomen, Chongwenmen, and Xizhimen. The two blue nodes are the original flow control stations that were deleted.The newly added flow control stations are transfer stations that have 4 or 5 degrees. These transfer stations have large passenger flow, and the internal structures are highly complicated. Among these stations, Xizhimen is a transfer station with three subway lines and, consequently, complicated transfer of passenger flow. Flow control can be implemented inside the station or in security. The proposed method in this paper is repeated. When the flow control measures are implemented after four time cycles, two flow control stations can be eliminated under the controllability condition: the Datunludong station and the Tiantandongmen station.The flow control stations are more concentrated in or near stations with large passenger flow. The flow control of nearby stations is also intended to relieve the station with large passenger flow. Current methods of flow control are restricted to experience. The flow control stations are basically fixed in the same time interval. With the implementation of flow control measures, the passenger flow of some stations is reduced. There may be a subpeak state, and the implementation of flow control measures should be a dynamic process.


## 5. Conclusions

This paper proposed an optimization method for flow control of urban rail transit based on the state-space equation and the driver node-matching algorithm. In addition, the characteristics of the optimization control of this method were analyzed by taking the Beijing rail transit network as an example. The conclusions are as follows.(1) The analysis of the characteristics of the complex network based on the passenger flow indicated that the passenger flow of the Beijing urban rail transit network has a “scale-free” characteristic.(2) According to the structure controllability model, this paper constructed a method of controllability determination for an urban rail transit network. This paper proves the theory of network controllability by taking as an example the passenger flow of the Beijing urban rail transit network. The passenger flow network is controllable when the number of driver nodes is 25.3% of the entire network.(3) To address the uncontrollable situation of the morning peak hour of the passenger flow network, an optimization method of flow control of the urban rail transit network was proposed based on driver node matching. The minimum set of driver nodes was identified by an intelligent search algorithm, which can obtain the specific flow control stations that can be controlled by the passenger flow network.The control method of this paper relies on the basic theory of macroscopic analysis of the whole network controllability state and reveals the relationship between driver nodes and controllability. An optimization method for flow control of urban rail transit is proposed based on the controllability of a large-scale network. This method does not have the disadvantages of current research methods that focus on flow control of a single station or local area. This method is highly suitable for the overall optimization of a passenger flow network with complicated operations. However, specific flow control measures are not addressed. To ensure the safe and efficient operation of the urban rail transit system, important directions for future research include determination of the flow control intensity and measures based on the optimization of the flow control stations and realization of the coordinated optimal control of the macroscopic system and micro individual systems.



---

*Source: 5961090-2018-09-04.xml*