Public Transit Network Design
Fixed-Charge Network Design · Shortest Path / Greedy
A transit authority designing a bus or light-rail network must decide which corridors to activate from 14 candidates to connect 8 neighbourhoods, minimizing infrastructure cost plus weighted passenger travel time. Each new corridor costs $2–$10M to build, and the authority must balance coverage against a constrained capital budget.
Where This Decision Fits
Transit planning chain — the highlighted step is what this page optimizes
The Problem
Selecting corridors to build a cost-effective transit backbone
A regional transit authority manages 8 neighbourhoods (labelled A–H) spread across a metropolitan area. Between these zones, there are 14 candidate transit corridors, each with a fixed infrastructure cost (in $M) reflecting right-of-way acquisition, construction, and station buildout.
The objective is to activate the minimum-cost set of corridors such that all neighbourhoods are reachable, while respecting a capital budget constraint. Each activated corridor also carries a weighted passenger travel time that contributes to service quality. The authority seeks to minimize infrastructure cost + λ · total travel time, where λ reflects the value of passenger hours saved.
This is the Fixed-Charge Network Design problem: given a graph G = (V, E) with fixed costs fe and flow costs ce on each edge, select a subset of edges to open, minimizing fixed + flow costs while maintaining connectivity. The problem is NP-hard in general, but good heuristics (greedy, MST-based) produce near-optimal solutions for moderate-sized instances.
subject to
Σe∈E fe · ye ≤ B // budget constraint
xe ≤ ye // flow only on open corridors
connectivity(y) // all nodes reachable
ye ∈ {0, 1}, xe ≥ 0 // binary open/close, continuous flow
Where fe is the fixed cost of corridor e, ye indicates whether the corridor is built, ce is the passenger travel time, and B is the available capital budget.
See full network design theoryTry It Yourself
Select a scenario, set the budget, choose an algorithm, and design the transit network
Transit Network Solver
The Algorithms
Three approaches to selecting transit corridors under budget constraints
MST (Cheapest Connected)
O(E log E)Sort all candidate corridors by infrastructure cost in ascending order, then greedily add each corridor that connects two previously unconnected components. This produces the minimum-cost spanning tree — the cheapest way to ensure all 8 neighbourhoods are reachable from each other.
Guarantees full connectivity with exactly |V| − 1 = 7 corridors, but ignores the budget constraint and passenger travel time. Serves as a baseline lower bound on infrastructure cost for connectivity.
Greedy (Coverage/Cost Ratio)
O(E²)At each step, select the corridor with the best ratio of new passenger coverage to cost. Coverage is measured by the number of new origin-destination pairs that become reachable when the corridor is activated. The algorithm continues until all zones are connected.
Often produces better passenger-time solutions than pure MST because it prioritizes high-demand corridors. May use slightly more budget but delivers higher service quality.
Budget-Constrained Greedy
O(E²)Identical to the coverage-driven greedy, but enforces a hard capital budget cap. At each step, corridors whose cost would exceed the remaining budget are skipped. If the budget runs out before all zones are connected, the algorithm reports partial coverage.
The most realistic approach: transit authorities rarely have unlimited funds. Use the budget slider to explore the trade-off between cost and coverage — tight budgets force hard choices about which neighbourhoods to prioritize.
Complexity & Trade-offs
- MST — O(E log E). Guarantees minimum-cost full connectivity. Ignores demand and budget.
- Greedy — O(E²). Balances coverage and cost. Near-optimal for moderate instances.
- Budget-Constrained — O(E²). Most practical. May leave zones unconnected under tight budgets.
- Fixed-charge network design is NP-hard in general; these heuristics provide quality solutions fast.
Key References
Foundational papers and textbooks
- (1984). “Network design and transportation planning: models and algorithms.” Transportation Science, 18(1), 1–55.
- (1997). “Network design.” Annotated Bibliographies in Combinatorial Optimization, Wiley, 311–334.
- (1993). “Network Flows: Theory, Algorithms, and Applications.” Prentice Hall, Ch. 19 (Network Design).
Need to optimize your transit network?
From corridor selection to service scheduling and fleet allocation, mathematical modeling can transform public transit planning decisions. Let’s discuss how Operations Research can work for you.