City Metro Network Expansion with Reinforcement Learning
Authors: Yu Wei
Minjia Mao
Xi Zhao
Jianhua Zou
Venue:  (2020)

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 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. 

Under review as a conference paper at ICLR 2020
CITY METRO NETWORK EXPANSION WITH REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
This paper presents method to solve the city metro network expansion problem using reinforcement learning (RL). In this method, we formulate the metro ex- pansion process of sequential station selection, and design feasibility rules based on the selected station sequence to ensure the reasonable connection pat- terns of the metro line. Following this formulation, we train an actor critic model to design the next metro line. The actor is seq2seq network with attention mech- anism to generate the parameterized policy which 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, 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.
INTRODUCTION
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 al. 2018). On the other hand, the expansion of the metro network in turn has 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 (Gutiérrez-Jane 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.
et al., 2018) Laporte & Pascoal (2015). However,
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 al. 2015). One conception of sustainability, social equity, which can be measured by the distributable benefit accessibility (Bchbahani 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 great influence on social equity. Therefore, 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 & Mesal 2015). Existing studies formulate the problem as non- linear integer programming, and call for an exponential number of subtour elimination constraints to ensure the rationality of expanded metro lines (Gutiérrez-larpa al. 2013 Wei et al. 2019 which hinders solving the problem efficiently.
Second, the huge solution space makes it difficult to find 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 (Gutiérrez-Jarpa

---

Under review as a conference paper at ICLR 2020
Gutierrez-Jara 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.
al. 2013 Wei et al. 2019 Laporte & Pascoal 2015
Carefully handerafted heuristics, embedded with problem-specific knowledge, usually efficient for large search space (Dufourd et al. 1996). However, the factors considered 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, general method is necessary.
In this paper, we propose method without expert knowledge to solve the city metro network ex- pansion 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 al. 2019)).
Following this formulation, we propose an actor critic model (Konda Tistsiklis 2000) to generate the next metro line. The actor is based on the seq 2seq 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, train the model with the critic reducing training variance, metro line following feasibility rules. The reward function takes the final output station sequence input only, which 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.
in order to find the
Based on real ccty-scale human mobility information of 24,770,715 mobile phone users obtained from citywide 3G cellular network, we expand the current metro network in Xi'an Xi'an, China. The results demonstrate the effectiveness of our method.
Our contributions are as follows:
1. We formulate the expansion of metro line as 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 formulate the problem than integer programming models.
2. We firstly propose a RL based method to solve the city metro network expansion prob- lem. 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 metro network. The exper- imental results demonstrate the effectiveness of our method.
2 RELATED WORK
2.1 METRO NETWORK DESIGN
Metro network plays an important role in public transportation system. For metro network design, Laporte & Pascoal (2015) predefine set of corridors, and propose path based algorithms. Consid- cring the connection with existing lines, WWi et al. (2019) expand the metro network predefined corridors. However, these methods depend predefined corridors by planner, which may be in- terfered by human judgment. (uutiérrez-Jarr et al. (2018) propose a greedy generation heuristic to select 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
2

---

Under review as a conference paper at ICLR 2020
integer programming models to formulate the metro network design problem, and call for exponen- tial number of constraints to ensure the rationality of expanded metro lines, which makes difficult to solve the problem efficiently. To cope with these problems above, propose general method that suitable for diverse objectives and does not require prior knowledge to expand city metro network.
2.2 REINFORCHMENT LEARNING
The strength of RL lies in its powerful decision- making ability. RL. has made great progress in complicated tasks like playing Atari games (Mnih al. (2013), robot training (Yang et al. (017) and combinatorial optimization (Bello et al., 2016; Nazari et al. 2018). RL is proved efficient in problems with high dimensional search space, such Go (Silver al., 2016) and StarCraft VViyyal et al. 2017). Mcanwhile, classical combinatorial optimization problems like minimum cut et. 2018b), traveling salesman problem (Bello al. 2016 Kool & Welling, 2018) and vehicle routing problem (Nzaaii et al. 2018) are solved by RL. Li et al. 2018a) points out that RL can find important factors which may ignored by human. We believe that RL has the ablity solve the metro expansion problem.
3 PROBLEM FORMULATION
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 target city, we divide into n x n grids in a two dimensional space [g: Each grid gi is square with a width of d, and its center is candidate station s, We define the expansion of metro network on an undirected graph G (S, E), where = {su, $1, -n2_1} 21g-...____11 contains all candidate
stations and E {(s,, 8,) |s 8j E S} contains all direct links between stations in existing lines. Each grid is associated with compound index of development D., and any two candidate stations 8; and 8j are associated with the two-way symmetrical OD trips odi, (= odz,)) between them. We present the expanded metro line as an ordered station sequence Z = (21, should satisfy the following constraints.
2T), E S, and it
The consecutive stations must follow the minimum-maximum distance rules.
The line routing should ensure reasonable connection patterns stations, avoiding subtour and meandering line.
The number of the stations is limited by N.
The budget limited by B.
Satisfied by the new line Z, we denote the newly added OD trips as Roa(2) and the social equity indicator as R2), which aims maximize the total benefits of the society. More details about these two are Appendix A The objective of the new metro line is to maximize the weighted sum of OD trips and social equity
(7) (Z) + 02 x Rac (7)
(1)
where aj and 0g are the weights of added OD trips and social equity, and a + 02 =
4 METHOD
4.1 RL FORMULATION
We focus on the city metro network expansion problem. We denote the station selected at step as
21, and the selected station sequence until step í as Z. = {œ1, 22, 2.]. Given the graph G, we aim to learn parameterized policy P (Z]G) to maximize w.
T
P P(Z =
P
(2)
3

---

Under review as a conference paper at ICLR 2020
and
Mr = M
(3)
Equation (3) characterizes the update of feasibility rules. We use a binary vector Mj to indicate whether each station can selected 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 RI. agent will build the station in order, completing the metro network expansion.
State. For step 6, the selected station sequence Ze is the current state. After agent chooses the next station 1 the state will be updated with Zr+1-
Action. We define the station 2, 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 w as reward. The reward function is calculated when the metro expansion is done.
routing
7,2
Feasible gnd
23
inteasible grd
228
Figure 1: An example of metro line expansion.
4.2 FEASIBILITY RULES
In this section, we present the feasibility rules 3 to satisfy the constraints in Section The RL. agent can only select stations in certain filter to ensure the ninimun-maximum distance rule. The filter is square shape with m X m grids. To ensure reasonable connection patterns of stations, design the action direction rules based 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 certain cost. Once the number of selected stations reaches the upper limit N, 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 (Gutiérrez-Jary et al. Wei et al. 2019). An example is shown in Figure]
2013
4.3
NETWORK ARCHITECTURE
As depicted in Figure 2 the neural network serially chooses the next station, with continuous inter- action 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 1, the encoder which includes single I-dimensional CNN layer is used to embed the in- formation of candidate stations into d-dimensional space. During the encoding step, consider several information for each grid { 2=2-1 including coordinates and whether selected as a station by the RL agent. The information after embedding be denoted X {X;)²²
The decoder consists an RNN layer and is used to output the current hidden state h'. takes the embedded information of the last selected station 2; and memory hidden state input. After
4

---

Under review as a conference paper at ICLR 2020
Canti-Ogriioo
Selation
Acter
Toad Ntaotk
NSF
Lzaph Informaiio
Cziph
Creph Infomatio
Stpt
Mop
Figure 2: Network architecture
decoding, the attention mechanism is employed. The attention mechanism takes the encoder output X, as reference and the hidden state lt as query to generate the probability distribution which indicates the probability of each candidate station. In the attention mechanism, the probability is calculated as
df = tanh W.
(Wa (X]3 softmax
(4)
d' xx
P(z4+19,,5 Z.) softmax(v" tanh(W. (W[[ @ H M,)
(6)
where a' is the relevant parameter, and is the context parameter. Wa. We, 1i and v. are train- ing parameters. [...i... represents the element-wise concatenation operator and represents the element-wise sum operator. H is huge constant and M, reflects the feasibility rules.
Once the station 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
Algorithm Processing Procedure
Input Graph G 1: for = O,..,TT T do
2: Update the feasible stations Mt Equation B
3: Compute embeddings X of the current state by enender.
Compute the query h' according to last hidden state 1--1 and the emhedding last selected station X by decoder (Initialize hº when f = 0).
5:
Compute the attention value a' by Equation ( and the probability P(z Z:) by Equation o
6: Select Station 1 with the probability P(z++1 GG Z.).
end return Solution Zr
4.4 TRAINING
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 8, given the graph G, the training objective be denoted
[( Ez ()w
5

---

Under review as a conference paper at ICLR 2020
Parameters trained with the policy gradient algorithm (Williams (1922).
(J(())) = 10) b(G)) Va log ( [
where b(g) represents the baseline for reducing the training variance.
During training, the well known actor critic algorithm used. For each step, the actor chooses the next station to build according 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
Algorithm 2 Actor Critic Training
Require: Batch size B, Training epoch E, Step
I: Initialize actor parameters f
2: Initialize critic parameters 0g
3: for epoch = 1, ..., E do
4: Reset city metro network G
5: tort=1,,... do
6:
Select the next station by actor, 2 <- SampleSolttion (p(-10))
7:
Update feasibility rules M, ((4)
8:
end for
9:
Find solution Z' for each batch, where E {l...... B3
10:
Calculate baseline b(9) by critic
11:
(J) + 1/ Ei= (Z
(Z' (
b(G)) log pe (Z
12:
Update the parameters of actor 0 + Adam VJ((lG))
13:
The B > ( b())2
14:
Update the parameters of critic 0g < Ad, V
end for
5 EXPERIMENTS
We conduct a case study to investigate behavior of our method. The data and parameters are presented in Section 5. 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 not in need of expert knowledge. We sequentially expand several metro lines in Section 5.4
5.1 DATA AND PARAMETERS
The research is conducted based on the metro network Xi'an, Shaanxi Province, China. Its first line started operation 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 in- formation 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 Section 4.2 as 5 x 5 according to Laporte & Pascoal (2015). Subsequently, we calculate the OD grids. Figure 3(b) presents the distribution of house prices in 2015. The
into 29 x 29 grids. Corresoondingly, we set the size of filter in
trips between any house price of grid is used to charactenize its index of development D,, which is applied to the calculation of social equity (see Appendix A] more details).
5.2 METRO EXPANSION RESULTS
We conduct our method to design the next metro line according to the objective The results shown in Figure 4 and corresponding indicators presented in Table With the decrease
of aj the expanded Tine shifts from satisfying more OD trips in Figure 4(a to achieving higher
social equity indicator in Figure Among them, the expanded line in Figure 4(c) passes through

---

Under review as a conference paper at ICLR 2020
12000
10000
5200
Metro network.
(b) House price (RMB).
Figure 3: The current city operational status.
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 equally important, the expanded line satisfies two factors in a balanced way. Its shape is like partial combination of the 2 subsequently opened lines after October, 2015.
Different objectives lead different metro network. The objectives of metro expansion vary with different cities and stages, which may cause existing methods, whether heuristics 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.
(a) 01 1,00 =
(b) 01
0.5, 02 0.5
(c) 01
0,
=1
Figure 4: The next expanded metro line with higher priority. The blue lines are our expanding lines.
Table 1: The newly satisfied OD trips and social equity
Rod
Rac
W
01, 02 1,0
48.17
34.60
48.17
0n, 02 = 0.5, 0.5
26.79
33.18
29.98
01, 02
27.38
36.64
36.64
5.3 COMPARISONS WITH BASELINE
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. (019 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 the predefined corridor. After the corridor determined, the optimization is conducted by Gurobi with the same objective function (maximizing OD trips). The result corridor is slightly better than ours according to Table 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, conduct the baseline in these two corridors with different objectives respectively. Corresponding results are presented Table [ Compared with our method, all the expanded lines in the fourth and fifth corridors show bad performance.

---

Under review as a conference paper at ICLR 2020
Table 2: Comparisons with baseline (Wei al. 2019).
1
0.5
a1
Method
Rod
Rac
w
Rod
Rac
w
Rod
Rac
Corridor
48.33
48.33
Corridor 2
27.53
33.93
30.73
Corridor 3
37.14
37.14
Corridor
23.97
23.97
16.70
22.68
19.59
26.87
26.87
Corridor 5
28.63
28.63
27.52
21.21
24.37
21.95
21.95
Our model
48.17
48.17
25.03
31.63
28.33
36.64
36.64
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.
(a) The first predefined corridor.
(b) The fourth predefined corridor. (c) The fifth predefined corridor.
Figure 5: Comparisons with the expanded lines in predefined corridors. The area between two yellow lines is the predefined corridors. The blue (violet) lines are the expanded lines with (baseline) method, considering only OD trips.
5.4 EXPANSION OF MULTIPLE METRO LINES
Considering OD trips and social equity equally important, sequentially design the second metro line with the expanded line (bb) as the existing line. The expanded line presented in violet is shown in Figure Its lower left part 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.
10
Figure 6: Multiple expanded metro lines.
CONCLUSION
This paper presents 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 generate 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.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Elisabete Arsenio, Karel Martens, and Floridea Di Ciommo. Sustainable urban mobility plans: Bridging climate change and equity targets? Research in Transportation Economics, 55:30-39, 2016.
Hamid Behbahani, Sobhan Nazari, Masood Jafari Kang, and Todd Litman. A conceptual framework to formulate transportation network design problem considering social equity criteria. Transporta- tion Research Part A: Policy and Practice, 125:171-188 2019.
Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint 1.099900 2016.
Hélène Dufourd, Michel Gendreau, and Gilbert Laporte. Locating a transit line using tabu search. Location Science, 4(1-2):1-19, 1996.
Reza Zanjirani Farahani, Elnaz Miandoabehi, Wai Yuen Szeto, and Hannanch Rashidi. A review of urban transportation network design problems. European Journal of Operational Research, 229 (2):281-302, 2013.
Gabriel Gutiérnez-Jarpa Carlos Obreque, Gilbert Laporte, and Vladimir Marianov. Rapid transit network design for optimal cost and origin destinntstintiion demand capture. Computers & Operations Research, +0(12):3000-3009 2013.
Gabriel Gutiérrez-Jaraa, Gilbert Laporte, and Vladimir Marianov. Corridor-based metro network design with travel flow capture. Computers & Operations Research, 89:58-67, 2018.
Vijay Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances neural information processing systems, pp. (008-1014, 2000.
WWM Kool and M Welling. Attention solves your tsp. arXiv preprint trXiv:1803.0847. 2018.
Michael Kuntz and Marco Helbich. Geostatistical mapping of real estate prices: an empirical com- parison of kriging and cokriging. International Journal of Geographical Information Science, 28 19):1904-1921, 2014.
Gilbert Laporte and Juan A Mesa. The design of rapid transit networks. In Location science, pp- 581-594. Springer, 2015.
Gilbert Laporte and Marta MB Pascoal. Path based algorithms for metro network design. Compulers & Operations Research, 62:78-94 2015.
Yexin Li, Yu Zheng, and Qiang Yang. Dynamic bike reposition: A spatio-temporal reinforcement learning approach. 2018a
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. CoRR, abs/1810. 10659, 2018b.
Kevin Manaugh, Madhav G Badami, and Ahmed M El-Geneidy. Integrating social equity into urban transportation planning: A critical evaluation of equity objectives and measures in transportation plans in north america. Transport policy, 37:167-176, 2015.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 13Xiv:1312.5602, 2013.
MohammadReza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takac. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, pp. 9861-9871, 2018.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7787):484, 2016.

---

Under review as a conference paper at ICLR 2020
Yanshuo Sun, Paul Schonfeld, and Qianwen Guo. Optimal extension of rail transit lines. Interna- tional Journal of Sustainable Transportation, 12(10):753-66)) 7-977773377,,, 2018.
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. In Advances neural information processing systems, pp. 3104-3112, 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems, pp. 5998-6098 -0088, 2017.
Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittwieser, et al. Starcraft ii: A new challenge for reinforcement learning. arXiv preprint arXiv 2017.
Yi Wei, Jian Gang Jin, Jingfeng Yang, and Linjun Lu. Strategic network expansion of urban rapid transit systems: bi-objective programming model. Computer-Aided Civil and Infrastructure Engineering, 34(5):431-445 2019.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-23 1992.
Zhaoyang Yang, Kathryn Merrick, Hussein Abbass, and Lianwen Jin. Multi-task deep rein- forcement learning for continuous action control. In IJCAI, pp. 3301-3307, 2017.
Junjun Yin, Aiman Soliman, Dandong Yin, and Shaowen Wang. Depicting urban boundaries from mobility network of spatial interactions: case study of great britain with geo-located twitter data. International Journal of Geographical Information Science, 31(7):1293-133 2017.
10

---

Under review as a conference paper at ICLR 2020
A ADDED OD TRIPS AND SOCIAL EQUITY INDICATOR
A.1 ADDED OD TRIPS
In our study, the expanded line allowed to connect with existing metro lines to form transfer stations. Thus, our (Z)(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 calculated as the same in Behbbhhan et al. (2019). The expansion of metro has impact on the accessibility of each area. We calculate the accessibility Ac; of area as
Ac; = D,F((())
(9)
3
where
Ciy: the travel cost between and j
F' (czj) is defined
F (cx) = F(yy) = -by
(10)
where taj is travel time and 3 is an adjustment parameter. Dj is the compound index of development and defined
D, Σ wedjk
(11)
where dz.k an economic variable and Wi is the weight.
In our study, we condider that ti 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 g: as its index of development Dj.
Under utilitarianism theory, the social equity indicator Rac( is defined as the total added benefits Σ, Ac,. We prefer the metro line satisfying greater social equity indicator Rae (Z).

---

Under review as a conference paper at ICLR 2020
B ACTION DIRECTION RULES
In practice, the metro line should avoid subtour and squiggly line. Based on history action direction, we design agent action direction rules ensure the rationality of expanded metro lines, shown in Figure] 7
Impermisable direction
direction restriction
History action direction
Permissible direction
History action direction
Permissible direction
+
Figure 7: Action direction rules.
12


Reviews:
[{"review_id": "rJl7sAFy5H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper the authors train a seq2seq model through reinforcement learning to iteratively expand a city metro network. The authors show that different objectives can be satisfied with this approach, such as the accessibility to different areas (something the authors call social equity indicator) or maximising origin-destination trips. \n\nThe paper is interesting but could use a more extensive comparison to alternative approaches or ablated  version of the same approach. For example, what if the approach would only take into account the last metro station instead of the complete previous sequence? Would it work less well? Additionally, the baseline method the approach is compared against is not explained in enough detail. In addition to RL methods, method such as genetic algorithm have shown great promise in producing layouts, such as for wind turbines (e.g. Grady et al. “Placement of wind turbines using genetic algorithms”). I wonder if such an approach would work equally well for designing metro lines and if RL is really the best technique here (which it might be but I’m not convinced yet). Because of the mentioned shortcomings, I believe the paper should be improved before publication. \n\nAdditionally, the paper would benefit from a careful spell and grammar check. I found multiple typos, especially in the introduction.  ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rJgavbZ2tr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nMain arguments \n\nApart from the interesting approach, this paper should be rejected due to several reasons: (1) the specific application field, considered in this paper, have to be generalized to more general cases, in order to be valuable for Machine Learning community, (2) from RL algorithms perspective, the novelty of proposed method is questionable due to lack of literature review and advanced approach to deep reinforcement learning, (3) requirement of explainable AI is essential for deployment and in spite of the quite sufficient explanations of the algorithm’s works, this paper does not well justify its superiority over the traditional methods either by theory or practice, due to experiments suffering from the lack of variability and missing the main point of improvement, which leads to generally insufficient contribution (4) the paper is unpolished and lacks specific formulations from the existing literature on related subjects.\n \nIn detail\n\nThe paper does a great job of justifying neither the novelty of its method nor the guarantees of increased performance or efficiency compared to existing methods. Although the proposed method discusses the specific problem and there could be a lack of existing sufficiently good methods in this specific topic, the reinforcement learning paradigm is utilized by authors in a very superficial and general manner. \n\nFirstly, the paper excludes any comparison to similar problems and already existing methods of RL used by similar fields, which can be expressed as planning with constraints (for example, path planning in mobile robot navigation), thus will be more valuable to ML community than specific application of graph expansion problem, limited to line-by-line addition. \n\nSecondly, except general notice of combinatorial problems solved by RL algorithms, the literature review lacks mentioning graph representation methods or any seq2seq algorithms (which efficiently uses attention), which should serve as an initial guess for the well-performing model in this particular problem. Regarding the RL approach, there are plenty of already solved planning problems, papers comparing RL algorithms and their performances on grid-based, discrete environment problems in order to mention here and ideally, comparing to proposed one within the same specific problem formulation. Because of this reason, there is no justification of concrete architecture construction and choice of actor-critic model for learning this policy in this specific example and so there is no intuition, why this model will work better than existing methods. Besides, this leads to the doubtful novelty of the proposed algorithm, although used first time in this specific field, but composed totally from the same components and sometimes in the same combination as in other works related to RL methods in planning.\n\nMoreover, the explanation of the methods’ architecture and basic components’ influence on the system is insufficient but might serve as an initial explanation of how this algorithm works. However, the number of experiments and their variations leaves much to be desired to justify its practical advantages and its utilization purposes as explainable AI. (1) there is no ablation study conducted to justify the choice of the proposed model over existing reinforcement learning methods, like actor-critic methods and their several variations with baseline, including modifications like attention model, graph representation, encoder and decoder architecture. The mentioning of these methods in the literature review is enough to answer this issue. (2) Using only one, hardly tuned baseline method on one dataset (without any reference to existing benchmark results on it) does not prove the efficiency and good performance of the model. Additional experiments can on different environments structure (city grids, metro network) of complexity of the environments (the width of the cell in the grid) to measure the performance of the algorithm based on hyperparameters (3) Real-world data brings more application-based matter into the subject, but requires more thorough investigation on the optimality of the solutions, proposed by RL method. This means that the comparison with the groundtruth metro network expansion (built after October 15) cannot be used as it is without using the expert evaluation. As a solution and habit in the machine learning literature, without the expert knowledge on the dataset, authors may propose a comparison of the real-world solution with the algorithm’s results, based on the optimized metrics (OD trips score and social equity) included into reward function. \n \nFinally, the proposed paper is imprecise in several ways. In terms of RL formulation and usage of RL terms (commonly introduced in literature), it reveals inappropriate usage of MDP terms and insufficient description policy-gradient approach in actor-critic training algorithm. While not appealing to this issue, authors missed the opportunity to formulate this problem as discrete MDP with high-dimensional action space and sparse rewards, thus had less opportunity to research different model-based reinforcement learning problems in discrete environments to conduct better model selection and experiments. Besides, the paper lacks details in some parts, like the usage of 3G cellular mobile data, which was not mentioned in this work, although it is emphasized as an essential part if not a significant contribution of this research.  \n \n\n \nQuestions to answer\nIntroduction\n\tWhat is the reason by constructing the city metro networks line by line, not iteratively adding stations to the existing network on the grid? This would make your problem closer to general grid-based planning problems. Do traditional methods expand metro networks only line-by-line and can this be there a limitation?\n\tHow does a “good solution” is represented in the literature with traditional approaches? What are the general measures and constraints in practice?\n\tIs incorporating social equity concern your contribution? Then why does the maximization of OD trips is not enough (there is no mention of the preferability of social equity metric based on the results of experiments)?\n\tThe effectiveness of the method due to experimental results is still questionable.\nRelated work\n\tIf the main concern of the paper is still the limitation of other methods which use expert knowledge then it is better to state the usage of additional data (development index) in social equity metric as a reward design part in Appendix to justify this reward engineering\n\t“We believe that RL has the ability to solve the metro expansion problem” is the statement, which should be substituted by extensive literature review on RL methods used for planning with constraints or specifically graph-based expansion methods. \nProblem formulation\n\tIs the network graph undirected or directed (imprecise inclusion of “direct links”)? How does this the OD trips are measured (no information here or in Appendix A).\n\tWhat is the reason behind 4 constraints provided in problem formulation? Are they used or defined in the literature review papers?\n \nMethod\n\tRL and deep learning methods included in the literature review should be the reference of choosing one or another component of the algorithm, including the formula for policy and critic update.\n\tIt is essential to use notation based on RL formulation, for example, use r(s_t,a_t) = 0 if s_t  is not terminal state and r(s_t,a_t) = w(Z|G) in order to state the sparsity of the problem. S_t here is Z_t sequence of chosen stations during the episode (line expansion process) and so on.\n\tUse precise formulation, for example, the proposed P(Z|G) probability distribution is the trajectory distribution and not policy function, which could be denoted as π(z_t | S,G,M(Z_t)) \n\tHow does the choice of filter design is justified, based on similar works in the transportation field?\n\tWhat is the reason by choosing the 1-dimensional CNN layer to represent candidate stations and what is the concrete input information? There is no formal specification of the input data, regarding the existing graph structure, only a short mention of it.\n\tIs the attention mechanism architecture, used here, similar to other models used in seq2seq problems? (Answer: Yes) What is the motivation to use this concrete architecture? \n\tWhy does the permissibility mapping using filter is used in policy function? Are there reasons to use it in policy function, rather than include in reward design? For example, the commonly used approach is to penalize unfeasible actions (stations) with a very low reward, during the episode learning?\n\tTraining: \n\tHow does the sparsity of reward influence the performance? Is there a way to better design reward, so that there will not be a necessity to update actor and critic only after the end of the episode (termination step)?\n\tWhat is the reason for learning critic as V(Z) = w(Z|G)? Is there a need for baseline if the state and the sequence of actions have bijective mapping, meaning that one sequence of stations can generate the unique state of the environment – line expansion, and vice versa? The intuition of the baseline is to measure the value of the state as the average among all possible actions, which lead to this state.\n\tWhat are the batches B used in the actor-critic training procedure?\n\tHow do we generalize the environment training? Do we need to retrain the reinforcement learning algorithm for each different initial metro city network configuration, or it is generalizable to other grids, using the same weights?\nExperiments\n\tPlease, include the training time of the RL algorithm and its inference time, and compare it to the performance of the baseline algorithm, which should be one of the most essential contributions, due to the high time-complexity of traditional methods.\n\tHow does the choice of corridor width influence the performance of the baseline method? \n\tIs there the baseline performance on the same city metro network (Xi’an city metro) mentioned in other literature, to directly compare with? This is necessary to fill the gap in justification of proposed results optimality (for the baseline case).\n\tHow does the partial similarity of the 2 times line expansion by RL method and 6 real-world lines of the city metro network can justify the optimality of the proposed method? Can you provide the measurement based on OD trips and social equity? Can you provide a truly optimal solution based on the grid granularity, initial network graph, and constraints, to compare with as an optimal solution?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "Hyxa9ARAKr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Review of “City Metro Network Expansion with Reinforcement Learning”\n\nIn this work, they investigate the use of RL (actor-critic) for planning the expansion of a metro subway network in a City. They formulate the problem of expanding the metro system as sequence of actions, hence a seq2seq+attn type architecture is used for the actor. The reward calculation is based on a combination of origin-to-destination and social equity metrics. They apply their method to plan the expansion of the current metro lines in a large city in China where they can leverage the mobility information information gathered from ~ 25M mobile phones in the city.\n\nI think this work has great potential, as they identify a data-driven approach that can have a high impact (i.e. design subway lines affecting 25M+ people in a real city). That being said, there are some issues that I feel needs to be addressed before the work can be published at a high quality conference, so I want to help the authors improve the work by highlighting important points that will make the work better:\n\nThe related work section on metro network design is only a paragraph. I think both the related work and experiments sections are missing many substantial contributions, as there is vast literature of work from Operations Research area about solving such problems through constraint optimization. Even a simple google scholar search brings many examples [1]. This is before discussing about existing ML and Genetic Algorithm approaches [2], or with Monte Carlo Tree Search [3].\n\nWithout discussing existing work and offering detailed comparisons and experiments, this paper essentially just shows that RL can be applied to such problems, but the reader wouldn't know whether it is the best tool, or simply if RL is the hammer that is used to treat every problem like a nail. The only baseline the paper compared against is another paper published in 2019 which IMO is not satisfactory.\n\nOn a related note, there are also a few projects doing similar network optimizations with slime mold (Physarum) and different variations using it for shortest path finding in mazes and all sorts of interesting problems [4].\n\nI'm reminded of a nice work called “Neural Combinatorial Optimization with Reinforcement Learning” [5] that proposed the use of neural nets to solve TSP problem, but ultimately needed to put in the work to compare with traditional approaches. I'm including the reference here so the authors can learn from that paper's experiences to help improve the work.\n\nRegarding the dataset: One of the most impressive points is that the work utilized a giant dataset of ~ 25M mobile phones. For an important dataset like this that is central to an impactful application of ML, would be nice to have a discussion (even in the Appendix) to describe how the data is collected, and what regulations / user privacy issues the research team might have to overcome, as these types of issues are becoming very important to the wider research community. Would also like to see a discussion about whether the large amount of data points can be reduced to a simpler 2D density map and achieve similar performance? Would there be any plans to release an anonymized version of the dataset for demonstration purpose?\n\n[1] https://scholar.google.com/scholar?hl=en&as_sdt=0%2C5&q=transportation+network+operations+research+constraint+optimization&btnG=\n\n[2] https://scholar.google.com/scholar?hl=en&as_sdt=0%2C5&q=transportation+network+design+machine+learning&btnG=\n\n[3] i.e. Link Prediction with Monte Carlo Tree Search (https://paperswithcode.com/paper/m-walk-learning-to-walk-over-graphs-using)\n\n[4] https://www.researchgate.net/publication/324791496_Physarum-Inspired_Solutions_to_Network_Optimization_Problems\n\n[5] https://openreview.net/forum?id=rJY3vK9eg", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper explores the use of RL (actor-critic) for planning the expansion of a metro subway network in a City. The reviewers felt that novelty was limited and there was not enough motivation on what is special about this application, and what lessons can be learned from this exercise.  
Decision: Reject