PaperlayerView exact revision on arXiv

Source-linked AI summary

AlphaTransit: Learning to Design City-scale Transit Routes

Bibek Poudel, Sai Swaminathan, Weizi Li

arXiv:2605.28730v1cs.AI

TL;DR

TRNDP requires route-extension decisions whose consequences appear only after complete-network simulation, creating delayed and nonlocal feedback. AlphaTransit addresses this with MCTS guided by a neural policy-value network, achieving the highest service rates in both Bloomington demand regimes. The results support learned lookahead as an effective mechanism for route construction under delayed network-level evaluation.

  • Problem

    TRNDP involves interacting route extensions whose quality is observed only after the full network is assembled and simulated, creating delayed and nonlocal feedback.

  • Method

    AlphaTransit couples MCTS with a neural policy-value network that proposes feasible route extensions, estimates downstream design quality, and guides search without simulator rollouts inside the tree.

  • Results

    54.64% and 82.08% are AlphaTransit’s service rates under mixed and full transit demand, with gains over End-to-End RL and Pure MCTS in both settings.

  • Takeaways & Limitations

    The results indicate that coupling learned priors with lookahead search makes sparse terminal feedback more useful for route design.

  • Takeaways & Limitations

    Most experiments and model development rely on Bloomington, while every route starts at a transit-center hub and demand is represented by a static peak-hour OD matrix.

Abstract

from arXiv · show

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 cityscale 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 censusderived 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% and 82.1%, respectively. Relative to reinforcement learning without search, these correspond to 9.9% and 11.4% service rate gains; relative to MCTS without learned guidance, they correspond to 2.5% and 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.

1 Introduction

TRNDP requires sequential route extensions whose effects emerge only after complete-network simulation, making local decisions difficult under sparse, nonlocal feedback. AlphaTransit combines MCTS with a neural policy-value network and achieves the highest service rate across both evaluated demand regimes.

  • Motivation: Learned priors combined with explicit lookahead can extract stronger training signals from sparse-reward environments than policy learning alone.Prior successes include games, planning with learned models, algorithmic discovery, and low-level sorting.
  • Motivation: TRNDP jointly designs interacting routes under operational constraints, so one extension can alter transfers, congestion, shared infrastructure, and distant route-segment value.Its reward is delayed and nonlocal because route extensions are evaluated after the full network is assembled and simulated.
  • Approach: AlphaTransit couples MCTS with a neural policy-value network: the policy proposes feasible extensions, the value estimates downstream quality, and search selects the next extension without simulator rollouts inside the tree.Terminal simulator rewards are obtained only after a complete route set is constructed and then used to update the network.
  • Results: AlphaTransit achieves the highest service rate among evaluated methods in both demand regimes.The evaluation includes comparisons with End-to-End RL, Pure MCTS, heuristic, metaheuristic, neural-evolutionary, and real-world baselines on the Bloomington benchmark.
  • Results: 54.64% and 82.08% are AlphaTransit’s mean service rates under mixed and full transit demand, respectively.These correspond to relative gains of 9.9% and 11.4% over End-to-End RL, and 2.5% and 11.2% over Pure MCTS.

2 Related Work

TRNDP research spans exact, heuristic, metaheuristic, and learning-based methods, but realistic simulator-defined objectives remain difficult to optimize. Existing benchmarks often underrepresent realistic urban scale and the coupled effects of congestion, capacity, transfers, and passenger reassignment.

  • Existing methods: Exact and decomposition-based methods provide structure for analytical TRNDP variants but depend on simplified demand, assignment, and operating models.Those simplifications make simulator-defined objectives involving congestion and vehicle capacity difficult to optimize directly.
  • Existing methods: Metaheuristics such as genetic algorithms, simulated annealing, and bee colony optimization address larger design spaces with heuristic or evolutionary search.They form part of the longstanding exact, heuristic, and learning-based TRNDP literature.
  • Benchmark limitations: Most studies use small or synthetic benchmark networks or analytical objectives that do not reflect realistic urban scale and network coupling.A smaller body of work evaluates bus-oriented redesign and optimization through simulation.
  • Benchmark limitations: Congestion, vehicle capacity, transfer delays, and passenger reassignment make simulator-based TRNDP rewards stochastic, delayed, and nonlocal.These mechanisms motivate evaluation settings that preserve interactions in realistic urban networks.

3 AlphaTransit

AlphaTransit formulates transit route construction on a road graph as sequential decisions over feasible route extensions, with a simulation-based terminal reward. Its graph policy-value network supplies masked action priors and value estimates to MCTS, while scaling results show that compute allocation matters.

  • Problem formulation: The road network is modeled as an undirected graph with intersections as nodes, bidirectional road segments as edges, and exogenous origin–destination demand.Edges carry length and free-flow speed attributes.
  • Problem formulation: The transit design consists of ordered simple paths operated bidirectionally, with route spacing and service frequencies associated with each completed route.The simulator evaluates passenger itineraries on the induced transit graph, including transfers across multiple routes.
  • Problem formulation: The learned decision variables reduce to the route tuple because stop spacing is fixed and frequencies are assigned deterministically by a max-load rule.The max-load projection is the componentwise minimal positive frequency vector satisfying fixed-load capacity constraints.
  • Problem formulation: Route construction is a finite-horizon MDP in which masked node actions extend one route from a transit-center hub by one unvisited one-hop neighbor.Routes terminate automatically at maximum length or when no valid extension exists; in this setting K = 16 and Lmax = 14.
  • Reward: The terminal reward combines coverage, service, waiting and movement times, route overlap, fleet size, and bus utilization after complete-network simulation.The service term uses a fixed citywide OD-demand denominator, while reported service rate uses a different denominator.
  • Policy-value network: The policy-value network maps graph state to action probabilities and a completion value, using GATv2 message passing, Jumping Knowledge aggregation, masking, and graph pooling.AlphaTransit uses the policy probabilities as MCTS action priors and the value as the leaf estimate.
  • Scaling behavior: 400 search iterations produce top-5 reward 1.67, whereas 500 iterations lower reward to 1.29 with higher runtime under mixed demand.Thirty-two episodes per iteration reach reward 2.20 at the highest compute cost, while the 2× policy reaches 2.05 and the 16× policy falls below 0.

4 Experiment

Experiments evaluate AlphaTransit on the Bloomington benchmark and cross-city Laval transfer using simulator-based transit metrics. AlphaTransit achieves the strongest service-rate results while balancing coverage, overlap, efficiency, utilization, and computational cost.

  • Benchmark and setup: The Bloomington benchmark combines a topologically correct 143-node, 243-edge road graph, census-derived origin-destination demand, and 16 existing transit routes.The network covers approximately 152.3 km² and supplies a real-world transit reference.
  • Metrics: Evaluation measures service rate against fleet size, passenger experience through journey time and transfer rate, and operator efficiency through route efficiency and bus utilization.Service rate is the percentage of potential demand boarded.
  • Search efficiency: AlphaTransit improves sample efficiency under the same environment-step budget, while learned estimates keep decision-time search in seconds rather than Pure MCTS’s hundreds to thousands of seconds.Performance improves through Niter = 400, while larger search depth can reduce performance at Niter = 500.
  • Cross-city transfer: 90.72% service rate versus 55.03% for End-to-End RL on full-demand Laval transfer gives AlphaTransit its clearest cross-city advantage.Under mixed demand, Shortest Path has the highest service rate, while AlphaTransit remains close and has the lowest wait time.
  • Bloomington results: 54.64% service rate with 80 buses and 22.10% bus utilization makes AlphaTransit the mixed-demand leader on Bloomington.Under full demand, AlphaTransit reaches 82.08% service rate and leads wait time, route efficiency, and bus utilization.
  • Bloomington results: 9.9% and 11.4% service-rate gains over End-to-End RL, and 2.5% and 11.2% gains over Pure MCTS, occur under mixed and full demand respectively.At mixed demand, AlphaTransit reaches 54.64% with 80 buses versus Pure MCTS at 53.30% with 86 buses.

5 Conclusion and Discussion

AlphaTransit combines MCTS with a graph attention policy-value network to guide route construction under delayed, network-level evaluation. On the Bloomington benchmark, it achieved the highest service rate in both demand regimes, while validation remains geographically and operationally limited.

  • Conclusion: AlphaTransit couples MCTS with a graph attention policy-value network to refine feasible route extensions using downstream value estimates without simulator rollouts inside the tree.The policy proposes extensions, the value estimates completed-design quality, and search refines each construction decision.
  • Results: 54.64% and 82.08% service rates were achieved under mixed and full transit demand, respectively.These were the highest service rates among evaluated methods in both regimes.
  • Results: 9.9% and 11.4% relative service-rate gains over End-to-End RL, and 2.5% and 11.2% over Pure MCTS, were reported across the two demand regimes.The comparisons isolate learned lookahead against RL without search and MCTS without learned guidance.
  • Limitations: The study is primarily based on Bloomington, while the route-start assumption and simulator omit several deployment factors.The authors identify limited geographic scope, transit-center starts, static peak-hour demand, and omitted equity, accessibility, reliability, budget, and robustness constraints.
  • Future work: Future work includes broader metropolitan validation, relaxed route-origin constraints, time-varying demand, disruptions, second-stage frequency control, and constrained objectives.These extensions are proposed to address the current geographic, construction, demand, and objective boundaries.

A Size of the search space

The Bloomington design space is enormous even under the experimental transit-center initialization, making exhaustive or near-exhaustive search infeasible. The estimates approximate simple paths while ignoring overlapping edges between routes.

  • Search-space scope: K = 16 routes each visiting 14 distinct nodes define the reported Bloomington design scope.The network has |V| = 143 and |E| = 243, with routes represented by simple paths of L = 13 edges.
  • Random initialization: (d − 1)^12 = 3.65 × 10^4, Prandom ≈ 1.78 × 10^7, and Srandom ≈ 9.5 × 10^115 ≈ 10^116 estimate unconstrained route and network counts.The approximation accounts for non-repeating nodes using average degree d = 2.40.
  • Transit-center initialization: Transit-center initialization removes the |V| factor from each route count because every experimental route starts at the transit-center hub.This constrained space is the relevant one for the reported experiments.
  • Implication: Both initialization spaces are astronomically large, motivating approaches that exploit problem structure instead of exhaustive or near-exhaustive search.The estimate does not adjust for overlapping edges between routes.

B Frequency of Service assignment

AlphaTransit assigns route frequencies through a max-load projection derived from pre-simulation passenger loads rather than letting the agent choose frequencies directly. This projection is operator-cost-minimal under fixed normalized loads, but frequency can still affect simulator reward through passenger interactions.

  • Motivation: Frequency decisions affect passenger waiting and in-vehicle times as well as operator fleet requirements, but partial-route frequency targets can be unstable during sequential construction.A short partial route may appear to benefit from high frequency because it serves a small local demand pair.
  • Load projection: The projection builds an undirected, unweighted route graph and assigns each served OD pair to a deterministic minimum-hop path.Segment loads are accumulated along paths and divided by the number of overlapping routes serving each segment.
  • Max-load assignment: F(Π) = F_ml(Π), so routes serving high-demand corridors receive higher frequencies while overlapping routes may receive lower frequencies after normalized load splitting.The projection uses bus capacity C_k and maximum desired load factor δ_max.
  • Minimality: F_ml(Π) is componentwise minimal among capacity-feasible frequencies when normalized segment loads remain fixed.Under these assumptions, it minimizes any operator-frequency cost that is componentwise nondecreasing in frequency.
  • Minimality: For fixed route geometry and dispatch assumptions, fleet requirements are componentwise nondecreasing in frequency, extending the minimality result to the operator-frequency reward component.This conclusion concerns the operator-frequency component rather than the full simulator reward.
  • Projection gap: The full simulator reward can still depend on frequency through transfer waiting, passenger assignment, and induced load patterns.The frequency-projection gap measures value available from joint frequency choices after route geometry is fixed.
  • Limitation: A second-stage frequency policy could target cases where increasing a connector route’s frequency improves transfer paths or changes passenger assignment.The present study summarizes such effects through Δ_F rather than learning frequencies jointly with route construction.

E Training Procedures and Hyperparameters

Training and search were compared under substantial computational budgets, with AlphaTransit requiring markedly more runtime than End-to-End RL or Pure MCTS in the reported 1M-step runs.

  • Runtime: AlphaTransit with N_iter = 500 took roughly 24–27 hours for 1M-step runs, compared with 3–5 hours for PPO End-to-End RL and 120–168 hours for Pure MCTS.Experiments used an AMD Ryzen Threadripper 7960X CPU, 377 GB RAM, and an NVIDIA RTX PRO 6000 GPU.

E.1 Genetic Algorithm

The paper describes genetic, neural-evolutionary, MCTS, and end-to-end reinforcement-learning baselines for transit route construction and optimization. End-to-end RL addresses long-horizon credit assignment with dense shaping, while AlphaTransit trains with MCTS-guided decisions and terminal network evaluations.

  • The genetic algorithm represents each individual as a complete K-route network, with route lengths constrained between Lmin = 2 and Lmax = 14 nodes.
  • Its initial population combines demand-guided routes, constrained random walks, and a warm-start individual sampled from existing real-world routes.
  • Genetic operators use tournament selection, route-exchange crossover, and path-regeneration mutation while preserving route feasibility.
  • The neural evolutionary baseline replaces half of Bee Colony replacement mutations with routes constructed by a graph neural-network policy trained on synthetic 20-node cities.
  • End-to-end RL faces episodes exceeding 200 decisions before terminal reward, creating severe credit assignment demands that are addressed with dense route-construction feedback.
  • AlphaTransit collects complete networks through MCTS-guided decisions, reuses subtrees across route extensions, and trains its policy-value network from stored search targets and terminal rewards.

F.1 Bloomington, Indiana

The Bloomington benchmark models a city-scale transit network using road-derived topology, census-based demand, and existing bus routes. Its construction includes explicit geometric, coordinate, and demand-scaling assumptions for simulation.

  • The Bloomington dataset combines transportation-network structure, census-derived travel demand, and currently operating transit routes.
  • The network contains 143 nodes and 243 bidirectional edges across approximately 152.3 km2.
  • Tunnels, overpasses, and underpasses are represented as planar connections to balance modeling fidelity with simulation efficiency.
  • Edges are consolidated as bidirectional shortest-distance connections and assigned a uniform free-flow speed of 16.67 m/s.
  • Demand is derived from 2022 LODES commuting flows using census-block data from Monroe County, Indiana.
  • Commuting flows are scaled by 150% and converted to hourly demand using an 11% peak-hour share.
  • Bloomington Transit contributes 16 existing bus routes averaging 14.2 nodes per route, with route lengths ranging from 8 to 24 nodes.

F.2 Laval, Quebec

Laval serves as a larger cross-city generalization benchmark for policies trained only on Bloomington. Its network is substantially larger in node count and area while retaining the same graph diameter of 17 hops.

  • The Laval graph contains 632 nodes and 1,971 bidirectional edges across approximately 256 km2, making it roughly 4.4× larger than Bloomington by node count.
  • Node 542 is selected as Laval’s transit center because it has the highest degree, closeness centrality, and betweenness centrality.
  • Despite its larger node count, Laval has the same graph diameter as Bloomington: 17 hops.

G Extended Results

The extended results define the evaluation metrics and compare AlphaTransit with alternative designs under mixed and full demand. AlphaTransit leads service rate in both regimes and is strongest across several metrics under full demand, while trade-offs remain across objectives.

  • Evaluation metrics: Service rate is the fraction of potential demand counted as served, while wait time and transfer rate measure served-rider waiting and trips requiring transfers.
  • Evaluation metrics: Journey time includes waiting and in-vehicle movement, while route efficiency, fleet size, and bus utilization capture infrastructure, deployment, and vehicle-load outcomes.
  • Evaluation metrics: The route-overlap ratio is edge-count based, ranging from 0 when no segments are shared to 1 when every used segment appears in every nonempty route.
  • Bloomington results: 54.64% service rate is achieved by AlphaTransit under mixed demand, and 82.08% under full transit demand, the highest in both settings.
  • Bloomington results: Under full transit demand, AlphaTransit also achieves the best wait time, route efficiency, and bus utilization.
  • Bloomington results: Relative to End-to-End RL, AlphaTransit’s service rate is 9.9% and 11.4% higher across the two regimes; relative to Pure MCTS, it is 2.5% and 11.2% higher.
  • Learning and search cost: MCTS-guided learning improves reward under full demand while reducing decision cost by roughly two orders of magnitude relative to Pure MCTS at the same search depth.
Loading 2605.28730v1…