GTFS vehicle blocking on a consumer laptop in twelve seconds
Formulating bus schedule vehicle-blocking as a minimum cost flow problem using standard open GTFS transit feeds without paid proprietary solvers.
01 The problem
Commercial transit scheduling packages routinely charge five-figure enterprise licenses for vehicle blocking (chaining scheduled timetable trips into continuous vehicle blocks). Most open source attempts cast this as an integer program that chokes on networks with more than a few hundred trips.
02 The data
Open GTFS feeds from Calgary Transit (CT) and King County Metro (KCM), pre-processed with simple spatial-distance matrices.
| FEED | TRIPS | STOPS | RAW SIZE |
|---|---|---|---|
| Calgary Transit | 6,840 | 4,210 | 18 MB |
| King County Metro | 11,200 | 7,650 | 42 MB |
03 What I built
A minimum-cost flow network generator written in Rust with Python bindings using the NetworkX / LEMON graph library. Because the underlying constraint matrix is totally unimodular, the linear relaxation always yields integral flow solutions in milliseconds without branch-and-bound.
04 Result
| SOLVER | FLEET COUNT | SOLVE DURATION |
|---|---|---|
| Commercial MIP Solver | 412 vehicles | 184s |
| Naive Branch-and-Cut | 418 vehicles | 1,420s (timeout) |
| Unimodular Min-Cost Flow | 412 vehicles | 11.8s |
05 Where it broke
Deadhead compatibility: the pure min-cost flow formulation struggled with battery electric bus (BEB) state-of-charge constraints, requiring column generation for electrified blocks.
06 Run it yourself
$ git clone https://github.com/gospinup/spin-01-gtfs-blocking
$ cd spin-01-gtfs-blocking
$ cargo run --release -- --gtfs ./data/calgary.zip07 Discuss
Every spin has a thread on GitHub Discussions. If a constraint looks over-fit, if the baseline is too easy, or if you’ve solved this properly in production and I’m busy reinventing it badly — say so there. Corrections get credited in the spin itself.