MetroZero: Deep Reinforcement Learning and Monte Carlo Tree Search for Optimized Metro Network Expansion

Metro networks necessitate continuous expansion, either extending existing lines or constructing new ones. Optimizing this process, however, presents multifaceted challenges due to complex spatial and demographic relationships, dynamic travel patterns, and a vast solution space with non-linearities and multiple objectives. Existing approaches often fall short, either relying heavily on subjective expert knowledge or limiting their scope to isolated corridors. This paper introduces MetroZero, a deep reinforcement learning (DRL) framework designed to overcome these limitations. We formulate the optimization as a Markov Decision Process (MDP) and leverage a Monte Carlo Tree Search (MCTS) algorithm guided by an actor-critic agent. This powerful combination identifies the optimal sequence of expansion stations within budgetary constraints. To effectively learn network representations, we develop a multiplex graph encoder powered by attentive message passing. A graph attention network (GAT) and a feasibility mask are employed to prioritize high-potential expansion locations and navigate the search space. Inspired by AlphaZero, we train MetroZero through simulated self-play expansion games. Extensive experiments on real-world datasets from Beijing and Changsha demonstrate MetroZero's effectiveness and superiority. In a complex expansion scenario, it achieves remarkable improvements of 19.6% and 20.4% over the second-best model. Further experiments across varied urban contexts underscore MetorZero's scalability and adaptability.