routelab provides reference implementations of published routing algorithms; kernels in Rust with
Python bindings with a common API for easy comparison.
Requires Python 3.9+ and a Rust toolchain.
git clone https://github.com/bmander/routelab && cd routelab
python -m venv .venv && source .venv/bin/activate
pip install -e '.[dev]' # builds the Rust kernel via maturinDescribe a world as layers, bind a technique to it, plan a route:
import routelab as rl
env = rl.Environment()
env.register(rl.ScalarEdges(("a", "b", 1), ("b", "c", 15)))
technique = rl.Dijkstra() # a configuration, costing nothing
planner = technique.bind(env) # preprocessing, if the technique has any
planner.route("a", "c").routes[0] # Journey('a' → 'b' → 'c', cost=16)The same three steps hold for every technique on the shelf, a real city and a real timetable included:
from datetime import date, time
feed = rl.GTFS("kcm.zip", date(2026, 8, 17))
env = rl.Environment(feed, rl.Footpaths(feed, within=200))
answer = rl.RAPTOR().bind(env).route(downtown, juanita, departing=time(8, 30))
answer.routes
answer.searchspace()Then bmander.github.io/routelab — or
docs/, the same pages as Markdown. There is one per paper:
what it observed, its algorithm as pseudocode, and a runnable hello-world that
the test suite runs, so a page cannot drift from the code.
| Paper | Technique | Page |
|---|---|---|
| Dijkstra, A note on two problems in connexion with graphs (1959) | Dijkstra() |
Dijkstra's algorithm |
| Moore, The shortest path through a maze (1959) | BFS() |
Breadth-first search |
| Hart, Nilsson & Raphael, A formal basis for the heuristic determination of minimum cost paths (1968) | AStar(Euclidean()), AStar(Zero()) |
A* |
| Goldberg & Harrelson, Computing the shortest path: A* search meets graph theory (2005) | AStar(Landmarks(16)) |
ALT landmarks |
| Geisberger, Sanders, Schultes & Delling, Contraction hierarchies (2008) | ContractionHierarchy(EdgeDifference()) |
Contraction hierarchies |
| Dreyfus, An appraisal of some shortest-path algorithms (1969) | TimeDependentDijkstra() |
Time-dependent Dijkstra |
| Pyrga, Schulz, Wagner & Zaroliagis, Efficient models for timetable information in public transportation systems (2007) | TimeExpanded(), TimeDependent(), Footpaths(feed, within=) |
Two models of a timetable |
| Delling, Pajor & Werneck, Round-based public transit routing (2012) | RAPTOR() |
RAPTOR |
| Dibbelt, Pajor, Strasser & Wagner, Intriguingly simple and fast transit routing (2013) | CSA() |
Connection scan |
| Witt, Trip-based public transit routing (2015) | TripBased() |
Trip-based routing |
| Delling, Dibbelt, Pajor & Werneck, Public transit labeling (2015) | PTL() |
Public transit labeling |
| Baum, Buchhold, Sauer, Wagner & Zündorf, UnLimited TRAnsfers for multi-modal route planning (2019) | ULTRA(RAPTOR()), ULTRA(CSA()) |
ULTRA |
| Barrett, Jacob & Marathe, Formal-language-constrained path problems (2000) | LabelConstrained(), Modes(...) |
Label-constrained routing |
| Dibbelt, Pajor & Wagner, User-constrained multi-modal route planning (2012) §3 | UCCH() |
UCCH |
Not yet implemented, in the order the literature filled them: Delling, Pajor & Wagner, Engineering time-expanded graphs for faster timetable information (2009); Geisberger, Contraction of timetable networks with realistic transfers (2010); and Bast et al., Fast routing in very large public transportation networks using transfer patterns (2010).
Every kernel here is checked against something that cannot be wrong in the same direction — a pure-Python reference, a brute-force oracle, or the paper's own second model. See the contract.
- What preprocessing buys — the whole shelf as two axes: what each technique paid at bind time against what a query cost.
- Seeing it run — the command-line demos, and the node board
behind
demos/serve.py. - How it is built — what this is for, the contract, the layout, and the decisions underneath.
MIT.