Year: 2019

Abstract:
This paper presents a method to solve the city metro network expansion problem using reinforcement learning (RL). In this method, we formulate the metro expansion as a process of sequential station selection, and design feasibility rules based on the selected station sequence to ensure the reasonable connection patterns of the metro line. Following this formulation, we train an actor critic model to design the next metro line. The actor is a seq2seq network with attention mechanism to generate the parameterized policy which is the probability distribution over feasible stations. The critic is used to estimate the expected reward, which is determined by the output station sequences generated by the actor during training, in order to reduce the training variance. The learning procedure only requires the reward calculation. Thus our general method can be extended to multi-factor cases easily. Considering origin-destination (OD) trips and social equity, we expand the current metro network in Xi’an, China, based on the real mobility information of 24,770,715 mobile phone users in the whole city. The results demonstrate the effectiveness of our method.

heading: 1 INTRODUCTION
text: City metro network plays an important role in public transportation system. With the development of city, new transportation demands have led to the expansion of metro network. The last few years have witnessed tremendous expansion of metro network (Sun et al., 2018). On the other hand, the expansion of the metro network in turn has a profound impact on the city. The expanded lines may change the mobility trend of city population. Most previous research focuses on the design of metro network from scratch (Gutiérrez-Jarpa et al., 2018; Laporte & Pascoal, 2015). However, in the subsequent construction process, the dynamic of the city has been different from that in the initial stage. The original scheme may not be suitable for the current situation. Therefore, it is more reasonable to gradually design new lines to expand the metro network according to current city dynamic.
Usually, transportation planning objectives are mobility-based, such as maximizing OD trips. As the society progressed, sustainability has increasingly become the demand of city development. The sustainability prompts governments to re-recognize the role of the transport system, and thereby influences their transport policy (Manaugh et al., 2015). One conception of sustainability, social equity, which can be measured by the distributable benefit accessibility (Behbahani et al., 2019), has been acknowledged important. There have been several real transportation plans considering social equity (Arsenio et al., 2016). Metro network, an important transportation system, has a great influence on social equity. Therefore, in this work, we consider both OD trips and social equity to expand city metro network.
However, the problem becomes difficult when the city becomes large. First, it is difficult to formulate the problem efficiently (Laporte & Mesa, 2015). Existing studies formulate the problem as nonlinear integer programming, and call for an exponential number of subtour elimination constraints to ensure the rationality of expanded metro lines (Gutiérrez-Jarpa et al., 2013; Wei et al., 2019), which hinders solving the problem efficiently.
Second, the huge solution space makes it difficult to find a good solution effectively. Exact methods are inapplicable for integer programming problems with large solution space (Farahani et al., 2013). One common method in existing studies is to limit the search space. Previous work (Gutiérrez-Jarpa
et al., 2013; Wei et al., 2019; Laporte & Pascoal, 2015; Gutiérrez-Jarpa et al., 2018) predefines corridors based on expert knowledge, and only consider to design metro lines in these corridors. Their results depend on expert guidance, and it is possible that the best solution is left out. Therefore, we call for a method which does not require expert knowledge.
Carefully handcrafted heuristics, embedded with problem-specific knowledge, are usually efficient for large search space (Dufourd et al., 1996). However, the factors considered in the expansion of metro line vary with different cities and stages. Once the objectives of metro expansion change, heuristic methods need to be revised. Rather than handcrafting different heuristics for different objectives, a general method is necessary.
In this paper, we propose a method without expert knowledge to solve the city metro network expansion problem using RL. We formulate the metro line expansion as a process of sequential station selection, an MDP, and design feasibility rules based on the selected station sequence to ensure the reasonable connection patterns of the metro line. This formulation efficiently characterize the expansion of the metro line, without heavy constraints like existing studies (Wei et al., 2019).
Following this formulation, we propose an actor critic model (Konda & Tsitsiklis, 2000) to generate the next metro line. The actor is based on the seq2seq model (Sutskever et al., 2014). In the actor, an encoder characterizes the timely metro station information in the expansion process. After encoding, an RNN decoder is used to characterize the sequence information of the selected stations. Moreover, we employ an attention layer to produce the probability distribution over feasible candidate stations. Only requiring the reward calculation, we train the model with the critic reducing training variance, in order to find the high-priority metro line following feasibility rules. The reward function takes the final output station sequence as input only, which is friendly to objective changing. Therefore, our model is general for different objectives. Without expert knowledge, the learning procedure drives the policy to keep track of the better solution during the search and to search for better solutions. Its natural exploration mechanism determines that RL is suitable for large scale solution space.
Based on real city-scale human mobility information of 24,770,715 mobile phone users obtained from a citywide 3G cellular network, we expand the current metro network in Xi’an, China. The results demonstrate the effectiveness of our method.
Our contributions are as follows:
1. We formulate the expansion of a metro line as a process of sequential stations selection, a Markov decision process (MDP). We design feasibility rules based on the selected station sequence to ensure the reasonable connection patterns of metro line, which is more efficient to formulate the problem than integer programming models.
2. We firstly propose a RL based method to solve the city metro network expansion problem. Without expert knowledge, our general method can be easily extended to the metro expansion considering multi-factors.
3. We incorporate social equity concerns into metro network expansion. Compared with the realistically planned lines, the results show the rationality of considering social equity in transportation planning.
4. We use real city-scale human mobility information to expand a metro network. The experimental results demonstrate the effectiveness of our method.

heading: 2 RELATED WORK

heading: 2.1 METRO NETWORK DESIGN
text: Metro network plays an important role in public transportation system. For metro network design, Laporte & Pascoal (2015) predefine a set of corridors, and propose path based algorithms. Considering the connection with existing lines, Wei et al. (2019) expand the metro network in predefined corridors. However, these methods depend on predefined corridors by planner, which may be interfered by human judgment. Gutiérrez-Jarpa et al. (2018) propose a greedy generation heuristic to select a set of corridors with higher passenger traffic from a set of candidate corridors. Enumerating all candidate corridors is impossible, which may leave out some good solutions. The corridors may need frequent adjustments, once the objectives change. In addition, these studies adopt non-linear
integer programming models to formulate the metro network design problem, and call for exponential number of constraints to ensure the rationality of expanded metro lines, which makes it difficult to solve the problem efficiently. To cope with these problems above, we propose a general method that is suitable for diverse objectives and does not require prior knowledge to expand city metro network.

heading: 2.2 REINFORCEMENT LEARNING
text: The strength of RL lies in its powerful decision-making ability. RL has made great progress in complicated tasks like playing Atari games (Mnih et al., 2013), robot training (Yang et al., 2017) and combinatorial optimization (Bello et al., 2016; Nazari et al., 2018). RL is proved efficient in problems with high dimensional search space, such as Go (Silver et al., 2016) and StarCraft (Vinyals et al., 2017). Meanwhile, classical combinatorial optimization problems like minimum cut (Li et al., 2018b), traveling salesman problem (Bello et al., 2016; Kool & Welling, 2018) and vehicle routing problem (Nazari et al., 2018) are solved by RL. Li et al. (2018a) points out that RL can find important factors which may be ignored by human. We believe that RL has the ablity to solve the metro expansion problem.

heading: 3 PROBLEM FORMULATION
text: In this paper, we design the next metro line to expand the current metro network in the target city. The metro line is determined by stations and line routing, and is allowed to connect with existing lines to form transfer stations.
For a target city, we divide it into n× n grids in a two dimensional space {gi}n 2−1 i=0 . Each grid gi is a square with a width of d, and its center is a candidate station si. We define the expansion of metro network on an undirected graph G = (S,E), where S = {s0, s1, ..., sn2−1} contains all candidate stations and E = {(si, sj) |si, sj ∈ S} contains all direct links between stations in existing lines. Each grid gi is associated with a compound index of developmentDi, and any two candidate stations si and sj are associated with the two-way symmetrical OD trips odi,j(= odj,i) between them. We present the expanded metro line as an ordered station sequence Z = (z1, z2, . . . , zT ), zi ∈ S, and it should satisfy the following constraints.
• The consecutive stations must follow the minimum-maximum distance rules. • The line routing should ensure reasonable connection patterns of stations, avoiding subtour
and meandering line. • The number of the stations is limited by N . • The budget is limited by B.
Satisfied by the new line Z, we denote the newly added OD trips as Rod(Z) and the social equity indicator as Rac(Z), which aims to maximize the total benefits of the society. More details about these two are in Appendix A. The objective of the new metro line is to maximize the weighted sum of OD trips and social equity
ω (Z) = α1 ×Rod(Z) + α2 ×Rac(Z) (1)
where α1 and α2 are the weights of added OD trips and social equity, and α1 + α2 = 1.

heading: 4 METHOD

heading: 4.1 RL FORMULATION
text: We focus on the city metro network expansion problem. We denote the station selected at step t as zt, and the selected station sequence until step t as Zt = {z1, z2, . . . , zt}. Given the graph G, we aim to learn a parameterized policy P (Z|G) to maximize ω.
P (Z|G) = T∏ t=1 P (zt|G, Zt−1) , (2)
and Mt =M(Zt) (3)
Equation (3) characterizes the update of feasibility rules. We use a binary vector Mt to indicate whether each station can be selected in next step. According to the rules, feasible stations are set to 1, oherwise 0 (see Section 4.2 for more details). Important RL elements are listed as follows.
Environment. The environment correspond to the city in which the metro is expanded. The RL agent will build the station in order, completing the metro network expansion.
State. For step t, the selected station sequence Zt is the current state. After the agent chooses the next station zt+1, the state will be updated with Zt+1.
Action. We define the station zt which the agent chooses to build next step as the action. Once the action is decided, the current state will be updated.
Reward. Since RL are set to maximize the reward, we define the value of objective ω as reward. The reward function is calculated when the metro expansion is done.

heading: 4.2 FEASIBILITY RULES
text: In this section, we present the feasibility rules (3) to satisfy the constraints in Section 3. The RL agent can only select stations in a certain filter to ensure the minimum-maximum distance rule. The filter is a square shape with m × m grids. To ensure reasonable connection patterns of stations, we design the action direction rules based on history actions to determine the candidate action in the next step (see Appendix B for more details). During the expansion, the expanded metro line is allowed to connect with existing lines to form transfer stations, but it cannot coincide with the existing lines. Per unit length of metro line and per station consume a certain cost. Once the number of selected stations reaches the upper limit N , or the cost of construction exceeds the budget B, the expansion process is terminated. Based on these rules, the agent dynamically acquires the next optional stations, which avoids exponential constraints in existing studies (Gutiérrez-Jarpa et al., 2013; Wei et al., 2019). An example is shown in Figure 1.

heading: 4.3 NETWORK ARCHITECTURE
text: As depicted in Figure 2, the neural network serially chooses the next station, with continuous interaction with the environment. We use the seq2seq model with attention mechanism to construct the neural network (Sutskever et al. (2014); Vaswani et al. (2017)).
At step t, the encoder which includes a single 1-dimensional CNN layer is used to embed the information of candidate stations into a d-dimensional space. During the encoding step, we consider several information for each grid {gi}n 2−1 i=1 , including coordinates and whether it is selected as a station by the RL agent. The information after embedding can be denoted as Xt = {Xti} n2−1 i=1 .
The decoder consists of an RNN layer and is used to output the current hidden state ht. It takes the embedded information of the last selected station zt and memory hidden state as input. After
decoding, the attention mechanism is employed. The attention mechanism takes the encoder output Xt as reference and the hidden state ht as query to generate the probability distribution which indicates the probability of each candidate station. In the attention mechanism, the probability is calculated as
qti = v T a tanh(Wa[X t i ;h t]), at = softmax(qt) (4)
ct = ∑ i atiX t i (5)
P (zt+1|G, Zt) = softmax(vTc tanh(Wc[Xti ; ct])⊕H ·Mt) (6)
where at is the relevant parameter, and ct is the context parameter. Wa, Wc, vTa and v T c are training parameters. [. . . ; . . . ] represents the element-wise concatenation operator and ⊕ represents the element-wise sum operator. H is a huge constant and Mt reflects the feasibility rules.
Once the station is selected, the current hidden state and the embedded information of the selected station will be the input of next decoder step. The process of choosing stations repeats until any termination condition is reached. Detailed processing procedure is presented in Algorithm 1.
Algorithm 1 Processing Procedure Input Graph G 1: for t = 0, ...,T− 1 do 2: Update the feasible stations Mt by Equation (3). 3: Compute embeddings Xt of the current state by encoder. 4: Compute the query ht according to last hidden state ht−1 and the embedding of last selected station Xti by decoder (Initialize h
0 when t = 0). 5: Compute the attention value at by Equation (4), and the probability P (zt+1|G, Zt) by Equation (6). 6: Select Station zt+1 with the probability P (zt+1|G, Zt). 7: end for 8: return Solution = ZT

heading: 4.4 TRAINING
text: Taking learning methods into consideration, due to the lack of labels, the metro expansion problem cannot be tackled with supervised learning. The quality of supervised learning model is closely related to the quality of labels which are hard to obtain.
In contrast, RL provides the method for training the network. By setting the network parameters as θ, given the graph G, the training objective can be denoted as
J(θ|G) = EZ∼p(·|θ)ω(Z|G) (7)
Parameters are trained with the policy gradient algorithm (Williams (1992)).
∇J(θ|G) = EZ∼p(·|θ)[(ω(Z|G)− b(G))∇θ log pθ(Z|G)] (8)
where b(G) represents the baseline for reducing the training variance. During training, the well known actor critic algorithm is used. For each step, the actor chooses the next station to build according to the network in Section 4.3. The critic is set to calculate the baseline in Equation (8). The network architecture is simple for critic, containing a single Dense and ReLu layer after the original information is embedded with CNN. Detailed algorithm is shown in Algorithm 2.
Algorithm 2 Actor Critic Training Require: Batch size B, Training epoch E, Step T
1: Initialize actor parameters θ 2: Initialize critic parameters θc 3: for epoch = 1, ...,E do 4: Reset city metro network G 5: for t = 1, ...,T do 6: Select the next station by actor, zt ← SampleSolution (p(·|θ)) 7: Update feasibility rules Mt =M(Zt) 8: end for 9: Find a solution Zi for each batch, where i ∈ {1, . . . , B}
10: Calculate baseline b(G) by critic 11: ∇J(θ|G)← 1B ∑B i=1(ω(Z i|G)− b(G))∇θ log pθ ( Zi|G ) 12: Update the parameters of actor θ ← Adam(θ,∇J(θ|G)) 13: ∇Lc ← 1B ∑B i=1(ω(Z
i|G)− b(G))2 14: Update the parameters of critic θc ← Adam(θc,∇Lc) 15: end for

heading: 5 EXPERIMENTS
text: We conduct a case study to investigate the behavior of our method. The data and parameters are presented in Section 5.1. We conduct our method to expand the metro network in Section 5.2. Compared with baseline in Section 5.3, we demonstrate that our method is not in need of expert knowledge. We sequentially expand several metro lines in Section 5.4.

heading: 5.1 DATA AND PARAMETERS
text: The research is conducted based on the metro network in Xi’an, Shaanxi Province, China. Its first line started operation on September 16, 2011, and four lines are in operation by September 2019. Our experimental data, coming from a citywide 3G cellular data network, records the mobility information of 24,770,715 mobile phone users from October 1, 2015 to October 31, 2015. Figure 3(a) shows the metro network with 4 lines, where the red lines represent the existing 2 lines before October, 2015; the green lines represent the subsequently opened 2 lines; the dots represent stations.
Through data analysis referring to Yin et al. (2017), we set each grid as a square with 1000 meters width and divide the study area into 29 × 29 grids. Correspondingly, we set the size of filter in Section 4.2 as 5 × 5 according to Laporte & Pascoal (2015). Subsequently, we calculate the OD trips between any two grids. Figure 3(b) presents the distribution of house prices in 2015. The house price of grid gi is used to characterize its index of development Di, which is applied to the calculation of social equity (see Appendix A for more details).

heading: 5.2 METRO EXPANSION RESULTS
text: We conduct our method to design the next metro line according to the objective (1). The results are shown in Figure 4, and corresponding indicators are presented in Table 1. With the decrease of α1, the expanded line shifts from satisfying more OD trips in Figure 4(a) to achieving higher social equity indicator in Figure 4(c). Among them, the expanded line in Figure 4(c) passes through
the grids with high development level according to Figure 3(b), which intuitively demonstrates the effectiveness of our method when social equity is considered only. While considering OD trips and social equity as equally important, the expanded line satisfies two factors in a balanced way. Its shape is like a partial combination of the 2 subsequently opened lines after October, 2015.
Different objectives lead to different metro network. The objectives of metro expansion vary with different cities and stages, which may cause existing methods, whether heuristics or predefined corridors, to be revised. By changing the reward function, our method can be easily extended to different objectives, without problem-specific knowledge. Therefore, our method is general, and more suitable for metro expansion.

heading: 5.3 COMPARISONS WITH BASELINE
text: We compare our method against the baseline proposed in Wei et al. (2019). As for the baseline, we predefine corridors and end nodes as Wei et al. (2019) did. We conduct the baseline to expand metro line only in these corridors, with the end nodes as endpoints of metro lines.
Specifically, we firstly predefine corridor 1-3 in Table 2, which respectively contain our expanded lines with different objectives in Section 5.2. Taking the first predefined corridor in Figure 5(a) as an example, the area between the two yellow lines is the predefined corridor. After the corridor is determined, the optimization is conducted by Gurobi with the same objective function (maximizing OD trips). The result of corridor 1 is slightly better than ours according to Table 2. The same results appear in corridor 2 and 3 for the corresponding objectives.
Then we randomly predefine the fourth and fifth corridors, which are shown in Figure 5(b) and Figure 5(c). Similarly, we conduct the baseline in these two corridors with different objectives respectively. Corresponding results are presented in Table 2. Compared with our method, all the expanded lines in the fourth and fifth corridors show bad performance.
It can be vividly shown that the baseline method relys heavily on expert guidance. Once the corridor contains several good solutions, optimization tools such as Gurobi perform well in metro expansion problem. While the conditions is far more complicated in real world, causing it difficult to find the appropriate corridors. The fourth and fifth corridors indicate the bad results of choosing the unsuitable area. However, regardless of expert knowledge, RL shows the ability to find a good solution. The results are close to those conducted by Gurobi, showing the effiveness of our method.

heading: 5.4 EXPANSION OF MULTIPLE METRO LINES
text: Considering OD trips and social equity as equally important, we sequentially design the second metro line with the expanded line in Figure 4(b) as the existing line. The expanded line presented in violet is shown in Figure 6. Its lower left part is similar to the manually designed sixth metro line in reality. In this way, we design the metro lines sequentially and gradually expand the metro network.

heading: 6 CONCLUSION
text: This paper presents a method to solve the city metro network expansion problem using RL. By formulating the metro line expansion as a process of sequential station selection, we train a seq2seq model with attention mechanism to generate a parameterized policy. Without expert knowledge, the parameterized policy generates the next metro line. Our method is general for different objectives, thus it is suitable for the expansion of metro network with multi-factor objectives.

heading: A ADDED OD TRIPS AND SOCIAL EQUITY INDICATOR
text: A.1 ADDED OD TRIPS
In our study, the expanded line Z is allowed to connect with existing metro lines to form transfer stations. Thus, our Rod(Z) contains not only the OD trips between the stations on Z, but also contains the OD trips between the stations on Z and the stations on existing lines through transfer stations.
A.2 SOCIAL EQUITY INDICATOR
In this paper, the social equity indicator is calculated as the same in Behbahani et al. (2019). The expansion of metro has an impact on the accessibility of each area. We calculate the accessibility Aci of area i as
Aci = ∑ j DjF (cij) (9)
where
cij : the travel cost between i and j
F (cij) is defined as
F (cij) = F (tij) = e −βtij (10)
where tij is travel time and β is an adjustment parameter.
Dj is the compound index of development and defined as
Dj = ∑ k wkdj,k (11)
where dj,k is an economic variable and wk is the weight.
In our study, we condider that tij is proportional to distance between i and j. Kuntz & Helbich (2014) consider the house price as a socioeconomic variable, thus we take the house price of grid gi as its index of development Dj . Under a utilitarianism theory, the social equity indicatorRac(Z) is defined as the total added benefits∑ iAci. We prefer the metro line satisfying greater social equity indicator Rac(Z).

heading: B ACTION DIRECTION RULES
text: In practice, the metro line should avoid subtour and squiggly line. Based on history action direction, we design agent action direction rules to ensure the rationality of expanded metro lines, shown in Figure 7.

Review summaries:
This paper introduces a method for solving the problem of network expansion, in particular, considers the city metro network and its expansion within the new metro line. Since this problem was previously represented as the non-linear integer problem, having an exponential number of constraints or requiring expert knowledge, authors had an initial motivation to appeal to learnable algorithms from the reinforcement learning paradigm. Authors proposed to consider the problem as Markov Decision Process, so that the environment is represented as the city grid, with constructed metro network, before some timestamp conditioned by additional transportation constraints, while each new state in the expansion process of construction one separate metro line is the state of the metro network as graph with new station added to the metro line, considered as the agent’s action. The custom reward function was represented based on metrics like OD trips used in the traditional approaches and the first time used in this problem specific social equity score. The permissibility constraints of action, i.e. adding a new station, were incorporated into policy function, while the attention mechanism was used here as in other seq2seq models, to query the most suitable station among candidates. Authors use the actor-critic approach, widely exploited in reinforcement learning problems, and with all the above-mentioned modification reached the baseline results on the real-world data, obtained from Xi’an city metro network, Shaanxi province, China.