AlphaTransit: Learning to Design City-scale Transit Routes

Bibek Poudel, Sai Swaminathan, Weizi Li · 2026

Read AlphaTransit: Learning to Design City-scale Transit Routes by Bibek Poudel, Sai Swaminathan, Weizi Li (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-28730.txt.

Introduction

Bibek Poudel, Sai Swaminathan, and Weizi Li introduce AlphaTransit, a planning framework for city-scale bus networks. Route building suffers delayed feedback: a useful-looking extension can create bottlenecks, redundant overlap, or lower throughput. AlphaTransit couples Monte Carlo Tree Search with a neural policy network, giving decision-time lookahead without simulator rollouts. On a Bloomington benchmark with realistic roads and census-derived demand, it posts the top service rate in both demand settings. It beats reinforcement learning without search and tree search without learned guidance, gaining up to about 11 percent.

Catalog record

CREATORBibek Poudel, Sai Swaminathan, Weizi Li
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE96944
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.28730

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

AlphaTransit: Learning to Design City-scale Transit Routes Bibek Poudel, Sai Swaminathan, Weizi Li Abstract Designing a transit network requires many sequential route extension decisions, but their quality is often visible only after the full network is assembled. This delayed-feedback challenge lies at the heart of the Transit Route Network Design Problem (TRNDP), where route interactions can be deceptive: an extension that appears useful locally can create transfer bottlenecks, produce redundant overlap, or reduce overall throughput. To guide route construction under delayed simulator feedback, we introduce AlphaTransit, a search-based planning framework for city-scale bus network design. AlphaTransit couples Monte Carlo Tree Search (MCTS) with a neural policy-value network: the policy proposes route extensions, the value estimates downstream design quality, and search uses these predictions to refine each decision. This provides decision-time lookahead during route construction without running simulator rollouts inside the search tree. We evaluate AlphaTransit on a new Bloomington TRNDP benchmark with realistic road topology and census-derived demand, under mixed and full transit demand settings. In the Bloomington network, AlphaTransit attains the highest service rate in both demand settings, reaching 54.6 % 54.6\% and 82.1 % 82.1\% , respectively. Relative to reinforcement learning without search, these correspond to 9.9 % 9.9\% and 11.4 % 11.4\% service rate gains; relative to MCTS without learned guidance, they correspond to 2.5 % 2.5\% and 11.2 % 11.2\% gains. These results suggest that coupling learned guidance with MCTS is more effective than using either approach alone for transit network design. Our code and data are publicly available in https://github.com/poudel-bibek/AlphaTransit . Figure 1: Learning dynamics and search cost under mixed demand ( \alpha=0.3 ). LEFT : Curves show averages over two training seeds per reward mode. Reward shaping is critical for End-to-End RL. Early Stopping (ES) penalizes routes that terminate before L_{\max} , while Delta-coverage ( \Delta ) rewards only newly covered demand. The \Delta variants are strongest; \Delta + No ES is best. MIDDLE : MCTS search improves sample efficiency under the same environment-step budget. At search depth N_{\mathrm{iter}}=500 , AlphaTransit surpasses End-to-End RL around 3\times 10^{5} steps and finishes with a final smoothed reward 1.31 versus -4.02 . RIGHT : Learned policy and value estimates make MCTS search practical across search depths N_{\mathrm{iter}}\in[100,500] , when benchmarked on the Bloomington network with a single CPU worker. AlphaTransit stays within seconds per decision, whereas Pure MCTS requires hundreds to thousands of seconds per decision. 1 Introduction Learning to act under sparse rewards is a central challenge in sequential decision making 54 . In such settings, combining policy priors and value estimates with Monte Carlo Tree Search (MCTS) has notably achieved superhuman performance in games such as Go, chess, and shogi 51 ; 53 ; 52 . This approach has also succeeded with unknown dynamics by planning with a learned model 47 , and has yielded breakthroughs in algorithmic discovery for matrix multiplication 19 and low-level sorting routines 35 . Together, these results suggest that learned priors combined with explicit lookahead extract a stronger training signal from sparse reward environments than policy learning alone. We study this principle in Transit Route Network Design Problem (TRNDP), a combinatorial optimization problem in which a planner designs a set of possibly overlapping routes on a shared street network to serve many-to-many passenger flows under operational constraints such as fleet size and cost 46 ; 18 . Unlike classical routing problems such as the travelling salesman problem 31 or the vehicle routing problem 55 , TRNDP jointly designs a route network whose components interact through transfers, congestion, and shared infrastructure 11 . As a result, changing one route can reassign passengers across the network and alter the value of distant route segments. The reward signal is therefore delayed and nonlocal, since the effect of each route extension is observed only after the full network is assembled and simulated. TRNDP is NP-hard 28 ; 43 ; the Bloomington setting studied in this work admits \approx 10^{82} candidate route sets (Appendix A ). The optimization landscape is also deceptive: a locally attractive route extension can create transfer bottlenecks, redundant overlap, and lower global throughput. In addition, the objective is inherently multi criteria, balancing passenger facing metrics such as coverage, waiting time, and journey time against operator side constraints such as fleet size, route overlap, and vehicle utilization. Figure 2: AlphaTransit overview. At each route-construction state s_{t} , MCTS uses the policy-value network f_{\theta}=(P_{\theta},V_{\theta}) to perform selection, expansion, evaluation, and backpropagation. The visit count statistics define a MCTS policy \pi_{t} , from which the next action is sampled to advance the state. After the full route set is completed, UXsim evaluates the design and returns a terminal reward z . Tuples (s_{t},\pi_{t},z) are stored in buffer \mathcal{D} and sampled to train f_{\theta} with policy and value losses. Prior TRNDP methods handle this difficulty by simplifying the evaluation model, iteratively modifying candidate route sets, or learning route construction policies. Exact and decomposition-based methods follow the first path, making optimization tractable by using analytical passenger routing and travel time objectives rather than simulation 5 ; 62 . Metaheuristics follow the second path, generating and modifying candidate route sets with problem specific heuristic or evolutionary operators 38 ; 41 . More recently, learning based methods reduce manual design by learning policies that construct routes directly or heuristics that guide search 70 ; 24 . Across these approaches, local design choices remain hard to assess because their value depends on the completed route set. This limitation motivates a route construction procedure that improves local decisions through lookahead over partial networks, while avoiding expensive simulation at every node. To address this, we introduce AlphaTransit, a search-guided framework that couples MCTS with a neural policy-value network, shown in Fig. 2 . For each partial route, the policy provides priors over feasible extensions, and the value estimates downstream design quality. MCTS combines these predictions into a visit-count policy, from which the next extension is sampled to advance the design. During search, leaf states are evaluated by the value head rather than simulator rollouts. The simulator returns a terminal reward only after a complete route set is constructed; the resulting samples are used to update the network to match search-improved policies and predict final rewards. Our contributions are: • We introduce AlphaTransit and show that learned lookahead is effective for simulator-defined bus TRNDP, achieving the highest service rate among evaluated methods in both demand regimes. • We present a Bloomington TRNDP benchmark with a topologically accurate road network, census-derived origin-destination demand, and an existing human-designed bus transit reference. • We isolate the role of learned lookahead by comparing AlphaTransit against End-to-End Reinforcement Learning (RL) without decision-time search and Pure MCTS without learned priors or value estimates, alongside heuristic, metaheuristic, neural-evolutionary, and real-world baselines. We evaluate AlphaTransit on the Bloomington benchmark under mixed and full transit demand regimes. AlphaTransit reaches mean service rates of 54.64\% and 82.08\% , respectively, yielding relative service-rate gains of 9.9\% and 11.4\% over End-to-End RL, and 2.5\% and 11.2\% over Pure MCTS. Under mixed-demand, AlphaTransit also attains the highest bus utilization and second-highest route efficiency. Under full transit demand, it obtains the lowest wait time, highest route efficiency, and highest bus utilization. Together, these comparisons indicate that

Read the complete text