Transit Network Design
Route selection · frequency setting · passenger-time objective
Which bus or rail routes should a city operate, and at what frequencies, to move passengers to their destinations with minimum total travel time subject to a fleet budget? The problem is combinatorially explosive — even small networks have astronomical numbers of feasible route sets. Mandl's 1979 benchmark (15 nodes, 21 edges) anchored decades of algorithmic work; Ceder & Wilson (1986) decomposed the problem into route generation, frequency setting, and timetabling sub-problems that remain the standard framework; Baaj & Mahmassani (1995) gave an influential hybrid heuristic. Every design decision is also a distribution decision about whose commute gets shorter.
Problem context
Origin-destination demand meets a fleet budget
A transit agency operates on an underlying network G = (V, E) of stops and inter-stop corridors. The OD (origin-destination) demand matrix dod gives expected passengers per period wanting to travel between each pair. The design problem is: select a set of routes (sequences of stops and corridors) and frequencies (buses per hour on each route) to minimise total passenger travel time — which breaks down into in-vehicle time, waiting time (half the headway on average), and transfer time — subject to a fleet constraint.
The problem's combinatorial difficulty comes from the route-generation layer: even modest graphs admit exponentially many feasible routes satisfying length / directness constraints. Standard approaches decompose into (1) candidate route generation, (2) route selection ILP, (3) frequency setting, and (4) detailed timetabling. Direct holistic MILPs work only for very small instances; hybrid metaheuristics and genetic algorithms dominate the applied literature. Farahani et al. (2013) survey the modern state of the art.
Multi-stakeholder framing
Mathematical formulation
Route selection ILP + frequency setting
| Symbol | Definition | Domain |
|---|---|---|
| G = (V, E) | Underlying network of stops and corridors | directed or undirected |
| R | Set of candidate routes (generated upstream) | |R| = large |
| dod | Passenger demand from origin o to destination d | ℝ⁺ |
| fr | Frequency of route r (buses per hour) | ℝ⁺ |
| lenr | Length / cycle time of route r | ℝ⁺ |
| yr | Binary: 1 if route r is operated | {0, 1} |
| F | Fleet budget (total buses available) | ℕ⁺ |
| fmin | Minimum frequency per operated route (policy) | ℝ⁺ |
| Lmax | Maximum route length (policy) | ℝ⁺ |
s.t. Σr fr · lenr / speed ≤ F // fleet budget
fr ≥ fmin · yr ∀ r // min-frequency policy on operated routes
lenr ≤ Lmax ∀ r // bounded route length
passengers route via shortest-time path on operated network // assignment model
yr ∈ {0, 1}, fr ≥ 0
Complexity NP-hard even for small variants. Route generation is the combinatorial explosion; route selection given candidates is ILP, solvable for small R via CPLEX / Gurobi. Metaheuristics (GA, tabu, simulated annealing) dominate for realistic scale (50–500 candidate routes).
Wait time approximation twait ≈ 1 / (2 fr) under Poisson-arrival assumption. This breaks down at low frequencies (published schedule becomes the binding reality); corrections exist for low-frequency service (Mohring 1972).
Interactive solver
Small-network design demo with BFS-based candidate generation
Transit Design Solver
Solution interpretation
Efficiency, coverage, and whose trip gets faster
Direct-demand greedy concentrates service on the highest-volume OD corridors — good for aggregate passenger-time but can leave lower-demand areas without service. This is the utilitarian design choice.
Iterative improvement refines by swapping route endpoints to reduce total travel time or connect isolated demand. Typically smaller aggregate gains than the route-set choice but closes coverage gaps.
Adding a route reduces aggregate travel time with diminishing returns (each marginal route covers less incremental demand); there's usually a sweet spot where new routes stop contributing.
Limitations & Critique
What passenger-time minimisation leaves out
Equity of access — Title VI and transit-dependence
Utilitarian passenger-time minimisation concentrates service on high-demand corridors, which are often already well-served. Transit-dependent populations (low-income, elderly, disabled) may live in lower-density areas where “efficiency-optimal” design drops service. Title VI requires equity analysis of major service changes; naive OR optimisation fails this requirement.
Paratransit is a separate, harder problem
ADA-mandated paratransit for riders unable to use fixed-route service is a door-to-door VRPTW, not a network-design problem. Transit-design optimisation ignores it, yet paratransit is a large and rising share of agency cost and a legal obligation.
Demand is elastic and endogenous
The OD matrix dod is an input, but ridership responds to service quality. Better service attracts more riders; degraded service drives riders away. Static demand models understate both the benefit of improvements and the cost of cuts.
Reliability matters more than average travel time
Riders weight variability heavily. A route with 20-minute average + 15-minute std-dev is worse than a 25-minute average + 2-minute std-dev, but passenger-time minimisation treats them inversely. Reliability-aware extensions exist but are rarely used in applied studies.
Integration with land use
Transit design affects where people can afford to live and which jobs they can reach, which recursively affects demand. Treating the network design as standalone ignores land-use feedbacks that take decades to play out.
Transfer burden is poorly modelled
Transfers have uncertain waiting, physical difficulty, and psychological cost that simple time penalties understate. Networks designed to minimise aggregate time often shift burden to transfers, disproportionately affecting riders with mobility limitations.
Extensions & variants
Where the literature has gone
Frequency-aware route selection
Simultaneous route choice + frequency; larger MILP but more accurate than decomposed approaches.
Multi-modal integration
Bus + light rail + commuter rail jointly. Xiong et al. (2020) on integrated-multimodal network design.
Stochastic / robust design
Demand uncertainty; robust route selection under OD scenarios. Yan & Chen (2011).
Bi-level programming
Agency-level design + rider-level route-choice equilibrium. Outer: operator; inner: traffic assignment.
Equity-constrained design
Minimum-service constraints by geography or demographic; Title VI compliance as hard constraint rather than post-hoc review.
Dial-a-ride & microtransit
On-demand transit replacing low-density fixed routes; very different optimisation family (VRPTW).
Network redesign under fare integration
Fare-system changes shift rider behaviour; redesign must reckon with that. Seattle ORCA LIFT, LA METRO.
Climate-aware design
Electrification constraints, battery-range limits, and charging-infrastructure co-location. Active in 2020s.
Key references
Cited above · DOIs where available
Related applications
Network and routing siblings