Pathfinder 3.0: Radius-Based Merchant Discovery

Background

At Grubhub I was the technical lead for Pathfinder, the vehicle routing platform that estimates drive times for every stage of a delivery — 1.5 billion requests a day. Pathfinder is built on Customizable Route Planning (CRP), the algorithm Microsoft Research developed for Bing Maps.^[1] Before I left, I was designing its next major evolution — internally, Pathfinder 3.0. This page walks through that design and runs the whole thing, end to end, on real map data in your browser.

The problem it solves sounds simple: which merchants can deliver to this customer within a given drive-time radius? The classic architecture answers it backwards. Search first builds a candidate list using straight-line distance and other heuristics, then asks the routing engine for exact drive times to those candidates. That has three structural flaws. Straight-line distance lies — a restaurant across a river may be unreachable while a farther one up the highway is minutes away — so the pre-filter produces both false positives and false negatives. Query cost scales with the number of candidates, O(n) in merchant density rather than in the size of the search radius. And the routing call can't start until candidate selection finishes, putting drive-time estimation squarely on the critical path of every search.

Pathfinder 3.0 inverts the flow: give the routing engine just the diner's location and a time budget, and let it discover every reachable merchant itself. The trick is doing that without searching the entire road network — which is where CRP's partition structure, plus one new precomputed data set, comes in.

Standing on the Engine

Pathfinder's core is a CRP engine, and I've written that up separately — including an interactive demo of a point-to-point query hopping across the partition — in Customizable Route Planning, Visualized. The vocabulary this page needs from it: the road graph is partitioned into cells; the vertices touching edges cut by the partition are the cells' boundary vertices (the design doc calls them perimeter vertices); customization precomputes each cell's clique — all-pairs boundary-to-boundary costs through the cell — refreshed every few minutes with live traffic; and queries run Dijkstra over that small overlay graph instead of the full network, with exact results. Pathfinder 3.0 starts from that machinery and asks one more thing of it.

The New Piece: Precomputed Merchant Data

CRP alone answers point-to-point queries. To discover merchants, Pathfinder 3.0 adds one more precomputed data set, built offline alongside the traffic customization: for every merchant, the travel cost from the merchant to each boundary vertex of its own cell, computed by a Dijkstra constrained to that cell. In production this is serialized into a merchant-to-perimeter cost file and shipped to every query node with each 5-minute traffic refresh — merchant data and traffic data always coherent, hot-swapped together.

The radius query then has four steps:

1. First mile. A Dijkstra constrained to the diner's cell computes the cost from that cell's boundary vertices to the diner (the search runs in the merchant→diner direction, over reversed edges). Merchants in the diner's own cell are caught directly here.

2. Expanding search. Dijkstra over the overlay graph, seeded with the first-mile labels, expanding outward until every frontier label exceeds the time budget.

3. Merchant discovery. When the search settles a boundary vertex $b$ of cell $C$ with label $D(b)$ — the drive time from $b$ to the diner — every merchant $m$ in $C$ gets a candidate time using nothing but precomputed data and one addition:

4. Termination. The search stops when the priority queue's minimum exceeds the requested radius. Every merchant within the radius has been found — exactly, with no heuristic filter in the loop. The result is exhaustive because every merchant→diner path must exit the merchant's cell through some boundary vertex, and both halves of the decomposition are covered: the in-cell prefix by the precomputed costs, the rest by the overlay search.

Query cost is now proportional to the area the time budget can reach — the number of overlay vertices within the radius — rather than to the number of candidate merchants. Pricing a cell's entire merchant inventory costs one array scan when its first boundary vertex settles. Thousands of exact drive times fall out of a search that touches a few hundred vertices, fast enough that Search can fire the request the moment it knows the diner's location, in parallel with everything else it does.

What It Buys

Three properties matter operationally. Exactness: results match a full-graph Dijkstra to the second — the demo below verifies this on every query and reports the max discrepancy. Radius-proportional cost: dense downtown and sparse suburb cost the same for the same time budget. Cacheability: because the query needs only a location and a radius — no candidate list — results can be cached aggressively by geographic bucket, something impossible when every query carries a bespoke merchant list.

About the Demo

Everything below runs in your browser, in a web worker, on real OpenStreetMap data: a 5.8 × 6.7 km slice of downtown Chicago (Grubhub's hometown) with ~5,300 ways collapsing into a road graph of ~9,000 junction vertices, plus ~1,500 real restaurants, fast-food spots, and cafes from OSM as the merchant catalog. The pipeline animates each stage: parsing the extract, contracting the graph, partitioning it (recursive bisection, each split choosing the axis that severs the fewest edges), finding boundary vertices, computing the per-cell cliques, and precomputing every merchant's cost-to-perimeter rows.

Then it's interactive: click anywhere to place a diner, pick a radius, and watch the search expand — sparse jumps between boundary vertices, cells lighting up as their merchants are priced. Toggle to full Dijkstra to see what the same query costs without the overlay: a dense flood over every road vertex, finding the same merchants. The side-by-side settled-vertex counts are the whole argument for CRP, drawn rather than argued. (Unlike a point-to-point query, a radius query can't be goal-directed with A* — there is no destination to steer toward; exhaustiveness is the product.) Scroll to zoom, drag to pan, hover a discovered merchant for its name and drive time.

Idealizations to keep the demo honest but small: one partition level instead of CRP's nested hierarchy; speeds from OSM speed limits and highway classes, scaled by a fixed downtown congestion factor instead of live traffic (the real system re-customizes every five minutes); no turn costs; and a simpler partitioner than production's. The algorithmic structure — constrained Dijkstras, clique overlay, merchant discovery at boundary settlement — is faithful to the design.