AlphaTransit: Learning to Design City-scale Transit Routes

Problem
This paper addresses the Transit Route Network Design Problem (TRNDP), which involves making sequential route extension decisions for city-scale transit networks. A significant challenge in TRNDP is the delayed feedback from the quality of route interactions, as the effectiveness of a route can only be evaluated after the entire network is constructed. This work is presented as a preprint and has not yet undergone peer review.

Method
The authors propose AlphaTransit, a novel search-based planning framework that integrates Monte Carlo Tree Search (MCTS) with a neural policy-value network. The architecture consists of two main components: a policy network that suggests potential route extensions and a value network that estimates the quality of the overall design based on these extensions. The MCTS algorithm is employed to explore the decision space, utilizing the predictions from the neural networks to refine route construction decisions without requiring extensive simulator rollouts within the search tree. The framework is trained on a new benchmark dataset derived from realistic road topology and census data, specifically designed for the Bloomington TRNDP.

Results
AlphaTransit was evaluated on the Bloomington TRNDP benchmark under both mixed and full transit demand scenarios. The framework achieved service rates of 54.6% and 82.1% for mixed and full demand settings, respectively. When compared to a baseline reinforcement learning approach without search, AlphaTransit demonstrated service rate improvements of 9.9% and 11.4%. Additionally, when compared to MCTS without learned guidance, the gains were 2.5% and 11.2%. These results indicate that the combination of learned guidance and MCTS significantly enhances performance over using either method in isolation.

Limitations
The authors acknowledge that the performance of AlphaTransit is contingent on the quality of the neural networks and the training data. They do not address potential scalability issues when applied to larger or more complex urban environments, nor do they discuss the generalizability of the learned models to different cities or transit systems. Furthermore, the reliance on a specific benchmark may limit the applicability of the findings to other contexts.

Why it matters
The development of AlphaTransit has significant implications for urban planning and public transportation optimization. By effectively addressing the delayed feedback problem inherent in transit network design, this framework can lead to more efficient and responsive transit systems. The integration of MCTS with neural networks represents a promising direction for future research in combinatorial optimization problems, potentially influencing other domains where sequential decision-making under uncertainty is critical.

Authors: Bibek Poudel, Sai Swaminathan, Weizi Li
Source: arXiv:2605.28730
URL: https://arxiv.org/abs/2605.28730v1