MetroGNN: Metro Network Expansion with Deep Reinforcement Learning

Thank you very much for your positive feedback. We have added a formalized definition to both the MDP and the RL framework, and clarified some notations in the equations. All the additions are highlighted in red in the revised version, and we hope the following responses can adress your concerns.

Q1.a. What is the precise definition of OD trips?

Response: Specifically, if an individual starts a journey at region A, reaches region B and remians in B for at least 15 minutes, this travel event contributes a count of 1 to the OD trips from A to B. Furthermore, if the individual subsequently travels to region C, the entire movement will be considered as two separate trips: one from A to B and another from B to C. We have added this definition in Section A.2.

Q1.b. How is the OD trips obtained from our dataset?

Response: We get the spatio-temporal data from a large number of user movement trajectories from Tencent Map, a Map Service Providers in China, and the OD flow matrix in this paper is generated in the way mentioned in Q1.a. We have added the corresponding information in Experiment section.

Q2. How to determine whether a selected region should be an extension of an existing metro line (and which?) or the start of a new line?

Response: If the selected region satistfies the distance and angle constraints with existing lines, it will be considered as an extension. Specifically, if the seleted region are avaliable for multiple lines, the station will be assigned to the closest metro line. On the other hand, if the selected region only satisfies the distance constraints, it will be considered as the start of a new line. We apologize for any confusion this may have caused, and we have updated the formulas as well as the description in Section A.1 for further clarification.

Q3. In equation (5), which metro line do $n_{\pm 1}$ and $n_{\pm 2}$ refer to?

Response: The $n_{\pm 1}$ represents all the terminal stations within the metro network, including both the originating and terminating stations of each metro line. The $n_{\pm 2}$ represents all the subterminal stations directly connected to the $n_{\pm 1}$. Sorry for any confusion caused by the unclear expression, and we have added the appropriate explanation in Method section. To avoid possible ambiguity, the original expression of $n_{\pm 1}$ and $n_{\pm 2}$ has been changed to $n_j \in \mathcal V_{\pm 1}$ and $n_k\in\mathcal V_{\pm 2}$ in Section A.1 of the revised manuscript.

Thank you again for your constructive comments and valuable feedback, and we hope the above response can address your concerns.

Thank you for your valuable feedback. We have added complete mathematical description of the MDP and RL framework in the Method section and Appendix A.5. More importantly, we provide experimental results across several runs with p-values and error bars. We sincerely hope the following responses can address your concerns.

Q1. The authors do not report aggregated results across several runs together with statistical confidence measures (e.g. error bars).

Response: Thank you for your suggestions regarding the reliability of our method. In the previous version, we run multiple experiments with different seeds, and only report the best results in the original manuscript. According to your valuable suggestion, in the revised version, we have integrated the results of multiple (10) runs of the experiment in the Experiment section, please refer to the Table 2, Figure 3 and Figure 6 in the revised manuscript.

Q2.a. The model simplifise the Beijing network with only 50 nodes.

Response: We are sorry for making you confused of the graph size. Actually, the graphs for Beijing and Changsha contain a total of 1,166 and 469 nodes, respectively. It is possible that "B=50" in original Table 1 (Table 2 in revised version) caused this misunderstanding, which represents the expansion budget of $50 billion. We apologize for the ambiguity and have added detailed descriptions of the dataset in Table 1 and provided more precise descriptions.

Q2.b. The model has substantially longer running time than classic methods.

Response: Thank you very much for pointing out this important issue. We would like to provide more explanations in this response. Firstly, classic methods do not have a significant runtime advantage over our method. For example, the evolutionary algorithms take an average of 2 hours, while the mathematical programming methods take over 3 hours and need additional manual adjustments for the metro expansion of Beijing network. Secondly, those classic methods can not generate quality and stable solution for metro network expansion, and must regenerated from scratch for different metro networks. In contrast, though MetroGNN requires 8 hours of training, it constantly generate optimal and stable solutions. Moreover, the complementary experiments show that it takes only 20 seconds for the well-trained agent to generate better metro expansion solutions for different metro networks compared with DRL-CNN. According to your valuable comment, we have added the above discussion to Appendix A.5, and please check the revised manuscript for details.

Q3. The model does not reduce the solution space but enhance the efficiency of search.

Response: Thank you very much for the correction, we have changed the corresponding statement in the revised manuscript.

Q4. The analysis in 4.5 is tenuous, especially given the lack of multiple runs.

Response: Thank you for your valuable advice. We have added the results with multiple runs to the Figure 6 in the revised manuscript. The results show that the disadvantage of the attentive policy network is just a coincidence. In particular, the model with attentive policy network consistently generates better expansion solutions than the mlp-only policy network in the case of a complete 100 iterations.

Q5. Recent paper [2] that considers metro network planning with reinforcement learning approach should be cited.

Response: Thank you for your reference to this paper. We have carefully gone through the works mentioned in your comment and searched for more related literature. Despite the paper you mentioned, we also found the following two related papers [3,4] and have added proper references in Introduction and Related section:

[3] Yolcu, E., & Póczos, B. (2019). Learning local search heuristics for boolean satisfiability. Advances in Neural Information Processing Systems, 32.

[4] Wang, Q., & Tang, C. (2021). Deep reinforcement learning for transportation network combinatorial optimization: A survey. Knowledge-Based Systems, 233, 107526.

Thank you again for your constructive comments and valuable feedback, and we hope the above response can address your concerns.

Q3. Some important experimental setups are not mentioned or clearly described. For example, the statistics and analysis of datasets and implementation details of baselines.

Response: Thank you for bringing this to our attention. We have added the details of the dataset at Experiment section, and the implementation of baselines are added at Appendix A.3.

Q4. The collected real OD flow data are based on the realistic transportation network. If the metro networks have been changed, how can the authors obtain the corresponding OD flow?

Response: Thank you for this valuable comment. Though there are actually no methods that can predict the OD flow after expansion, research [1] provides an idea for evaluating the feasibility of a metro network to cope with changing OD flows. Following [1], we assume that OD flows do not change drastically after the expansion of the metro network, and add a 5% random noise to all OD trips. As shown in the follow table, MetroGNN outperforms the DRL-CNN with p-value < 0.003 and allows small variations in OD flow (experiments are repeated for 10 times with different random seeds).

[1] Wang, L., Jin, J. G., Sibul, G., & Wei, Y. (2023). Designing Metro Network Expansion: Deterministic and Robust Optimization Models. Networks and Spatial Economics, 23(1), 317-347.

The above results are shown in Section A.5 of the revised manuscript.

Thank you again for your constructive comments and valuable feedback, and we hope the above response can address your concerns.

Thank you for recognizing our work. We sincerely hope the following responses can address your remaining concerns.

Q1. The authors only introduce some of the same or similar methods to a specific combinatorial optimization problem without substantial technical innovations.

Response: Thank you for your comment. We would like to summarize the innovations of our work as follows:

• We propose a specifically designed GNN model for heterogeneous multi-graphs. This model enables effective capturing of intricate patterns in OD trips which is overlooked by traditional methods.
• We scale up the metro network more than tenfold compared to existing studies. The attentive policy network and carefully designed action mask enhances the agent's efficiency in exploring the solution space, enabling our proposed RL model to handle urban region graphs of more than one thousand nodes.
• Our proposed model exhibits remarkable transferability. The trained model demonstrates its ability to quickly generate high-quality expansion solutions when faced with different metro networks or varying OD trips. Please refer the response to Q2 of reviewer zGme for more details. This adaptability distinguishes our approach and enhances its applicability across diverse scenarios.

Q2. Many other factors need to be considered and optimized to construct a realistic metro network, e.g., social equity or fairness, environmental impact, and revenues.

Response: We genuinely appreciate your comment on the problem formulation and completely agree that metro network expansion requires careful consideration of multiple factors. On the one hand, the primary objective of the metro network is to effectively address the travel needs of citizens, thus we believe that the OD flow is a decisive factor in the planning of the metro network. On the other hand, we add additional experiments that incorporate the social equity consideration. Specifically, we quantify the inequity as the population-weighted variance of the shortest distance from regions to the metro network, and use the decline in inequality for evaluation. We also introduce $\alpha$ and $\beta$ for the adjustment of the weighting between OD flows and equity, respectively. As shown in the following table (higher is better), our proposed MetroGNN consistently outperforms DRL-CNN under different weightings, achieving better expansion targets with lower variance (* denotes to p-value < 0.1, and ** denotes to p-value < 0.05).

Above results have been added in Section A.7.

Dear reviewer 6Gv3,

We greatly appreciate your thorough review and positive feedback. In response to your comments, we have clarified the contributions of our work and conducted additional experiments, including the incorporation of societal equity metrics and robustness testing under varying OD trips. We would be grateful if you could confirm whether our responses have effectively addressed your concerns. We are more than willing to provide further clarification on any remaining points.

Thank you for your time and consideration!

Thank you for your valuable comments and we sincerely hope the following responses can address your concerns.

Q1. This paper does not have enough novelty to be published in a top machine learning venue. The reinforcement learning, GNNs and action masks are already widely used.

Response: Thank you for your concern on the innovation of our work. We would like to summarize the three major technical innovations of our work as follows:

• We propose a novel GNN model specially designed for heterogeneous multi-graphs. It allows us to effectively capture the intricate patterns of OD trips, while traditional methods merely focus on the spatial information of regions.
• We scale up the problem to more than ten times larger than those considered in previous studies. With the attentive policy network and the meticulously designed action mask, the agent can search the solution space much more efficiently, enabling our proposed RL model to handle urban region graphs of more than one thousand nodes.
• Our proposed model exhibits excellent transferability. The trained model demonstrates the ability to swiftly generate high-quality expansion solutions when confronted with different metro networks or varying OD trips. Please refer the response to Q2 for more details. This adaptability sets our approach apart and enhances its utility across diverse scenarios.

Q2. The model built by this paper is also preliminary, not considering cities' expansion.

Response: Thank you for your constructive comment on the expansion of cities, and we have added a series of experiments to showcase how our model handle the growing urban regions. Firstly, we remove 20% of the fringe regions of the city to train our model and then applied the trained model to the original complete urban regions. The following table illustrate the strong transferability of MetroGNN. When directly applied to a larger city, MetroGNN can quickly (within 20 seconds) generate solutions which are comparable to DRL-CNN. Notably, the fine-tuned model shows an improvement of more than 10.2% over the DRL-CNN (* denotes to p-value < 0.1, and ** denotes to p-value < 0.05).

Secondly, we introduce 5% noise to OD trips data with 10 different seeds to simulate the changes with urban development. The following table demonstrates that MetroGNN can allow variations in OD flow and still outperforms existing approaches.

Q3. The details of the model and algorithms are not defined in a clear and mathematical way, and this paper could be greatly improved by deleting excessive words and sentences.

Response: Thank you for your valuable comments on the presentation. We have added clear mathematical description of the MDP and the RL framework in Method section and Appendix A.1. We have also removed unnecessary expressions to make the article more concise. We provide critical descriptions of MDP as follows:

• State: The state $S_t$ is a three-tuple $(\mathcal{M}_t, b_t, l_t)$ containing the current metro network $\mathcal{M}_t=(\mathcal{V}_t,\mathcal{E}_t)$, the remaining budget $b_t$, and the number of new metro lines that can be built $l_t$.
• Action: The action $A_t$ corresponds to the selection of a single node in $\mathcal{N}$. Considering that the metro network expansion includes the extension of existing lines and the construction of new lines and needs to satisfy corresponding constraints, available actions are defined as: $A(S_t=(\mathcal{M}_t, b_t))=\{n \in \mathcal{N} | n \in (\mathcal{X}^e(\mathcal{M}_t,b_t) \cup \mathcal{X}^c(\mathcal{M}_t,b_t,l_t)) \},$ where $\mathcal{X}^e(\mathcal{M}_t,b_t)$ and $\mathcal{X}^c(\mathcal{M}_t,b_t,l_t)$ represent the set of regions that are available for extension and construction based on specific constraints, respectively. The details of diverse constraints are in Section A.1.
• Reward: Referring to the definition of total satisfied OD flow in Equation 1, the intermediate reward $R_t$ for action $A_t$ is defined as ${C_{od}(\mathcal M_t)-C_{od}(\mathcal{M}_{t-1})}$.

Dear reviewer zGme,

In our response, we have provided clear illustrations of our contributions, enhanced the mathematical description of our model, and conducted supplementary experiments according to your constructive suggestions. We would greatly appreciate it if you could take a moment to confirm whether our responses have effectively addressed your concerns. We are looking forward to any additional feedback you may have.

Thank you for your time and consideration!