Customizable Route Planning, Visualized

Background

At Grubhub I was the technical lead for Pathfinder, the routing platform that estimates drive times for every stage of a delivery — which restaurants a diner sees, which driver gets offered which order, when the food is promised to arrive. That's about 1.5 billion shortest-path problems a day, and every one of them needs an answer in milliseconds, on a road network whose effective weights — travel times under live traffic — change constantly.

Textbook Dijkstra is exact but explores a huge frontier: a 30-minute query settles every vertex within 30 minutes of the source, which in a metro area is most of the graph. Speed-up techniques like contraction hierarchies get queries down to microseconds, but their preprocessing bakes the edge weights in — and rebuilding it whenever traffic shifts is far too slow. What Pathfinder needed was the specific trade-off made by Customizable Route Planning (CRP), the algorithm Microsoft Research developed for Bing Maps:^[1] spend the heavy preprocessing on the road topology, which never changes, and make the metric-dependent part — the part traffic touches — cheap enough to rebuild every few minutes.

Three Phases

1. Partition (metric-independent). Cut the road graph into cells of roughly equal size while severing as few edges as possible. The endpoints of the severed edges are the cell's boundary vertices — sometimes called synthetic vertices, because together they define a synthetic overlay graph that stands in for the full network. This phase knows nothing about travel times, so it runs rarely.

2. Customization (metric-dependent). For every cell, compute the shortest path between every pair of its boundary vertices without leaving the cell — one small constrained Dijkstra per boundary vertex. The resulting all-pairs table is the cell's clique. This is the phase that absorbs traffic updates: re-run the constrained Dijkstras with fresh edge weights and every clique entry reflects current conditions. It's embarrassingly parallel and touches each cell independently.

3. Query. A point-to-point query never searches the full network. It runs three small searches instead: a Dijkstra from the source confined to the source's cell (to price every way out), a search over the overlay graph — boundary vertices connected by clique entries and cut edges (this is where the search "hops" between cells) — and a backward Dijkstra from the target confined to the target's cell (to price every way in). The overlay search is goal-directed: it runs as A* with an admissible heuristic — straight-line distance at the network's fastest road speed, which can never overestimate the remaining travel time — so the frontier reaches toward the destination instead of flooding in every direction, without giving up exactness. Stitching the three searches together:

The result is exact, not approximate: any shortest path decomposes into stretches that each stay inside one cell between two boundary crossings, and every such stretch is captured by a clique entry. The search terminates as soon as the overlay frontier can no longer beat the best complete route found. To recover the actual road geometry — not just the cost — the winning chain of boundary hops is unpacked: each clique hop re-runs its little in-cell Dijkstra to reveal the streets it summarized.

About the Demo

Everything below runs in a web worker on real OpenStreetMap data: a 5.8 × 6.7 km extract of downtown Chicago — about 5,300 ways contracted to ~4,700 junction vertices — partitioned into 48 cells with the boundary cliques computed live in front of you. Then click any two points. The green wave is the source-cell search, the red wave is the backward target-cell search, the purple flashes are the overlay A* hopping boundary-to-boundary across cells — watch it lean toward the destination — and the gold trace is the unpacked shortest path. Every query also runs a goal-directed A* over the full road graph for comparison — same heuristic, no overlay — and reported timings are medians of five bare runs of each. The settled-vertex counts side by side are the whole point of the algorithm.

Honest idealizations: a single partition level (production CRP nests several), speeds from OSM speed limits scaled by a fixed downtown congestion factor rather than live traffic, no turn costs, and a simpler partitioner than production's. The structure — the three-phase query, the constrained Dijkstras, the clique overlay, the path unpacking — is the real thing.

The companion white paper — Customizable Route Planning in the Browser (PDF) — is the long version: a proof that the overlay decomposition is exact, the admissibility argument for the goal-directed overlay search, the unpacking trade-off, and a measurement study over 1,500 queries and nine partition granularities — including the honest result that the 2.6× reduction in settled vertices only partly converts to wall-clock time at this graph size, and why.