Bounder: Delivery Boundaries from Isochrones

Background

A delivery marketplace runs on one predicate, evaluated constantly and almost never thought about: can this merchant deliver to this address? It gates every search result, every merchant page, every address change in a cart. At Grubhub it ran millions of times a day, and it had to answer in the time it takes to render a list.

The honest answer is a routing query — "is the drive from this kitchen to this doorstep under our promise?" — and that is exactly the answer nobody can afford. Even at Pathfinder's speed, a routing call per merchant per search is orders of magnitude too much work for a list of fifty restaurants rendered on scroll.

So you precompute. For each merchant, once, work out the region it can actually serve and store it as a polygon. Then the runtime predicate collapses to a point-in-polygon test: microseconds, no network call, no routing engine in the request path at all. Bounder was the service that generated those polygons. I owned it from inception.

The interesting part is not the idea — it's that the polygon is a lossy compression of a routing result, and compression means error. The whole engineering problem is choosing which errors to accept and then actually measuring them, rather than shipping a shape that looks plausible on a map and hoping.

Why Not a Circle

The tempting shortcut is a radius: draw a circle of n miles around the merchant and call it a delivery zone. Plenty of platforms did exactly that, and it fails in both directions at once, for the same reason straight-line distance fails at merchant discovery. Chicago makes the point vividly — the river, the rail corridors, and the expressways all cut the road network in ways a circle can't see. A restaurant three blocks from a diner across the river with no bridge nearby is a fifteen-minute drive; a restaurant a mile up a clear arterial is four minutes.

A circle drawn to cover the arterial over-promises across the river, and a circle drawn to exclude the river under-serves the arterial. There is no radius that gets both right, because the thing being approximated isn't a distance at all. It's a travel-time level set on a directed graph — an isochrone.

Step One: The Isochrone, on the Overlay

Bounder is built on the same CRP engine as everything else in this series (there is a separate write-up with its own demo): the road graph is partitioned into cells, and each cell's clique — all-pairs costs between its boundary vertices — is precomputed, so queries search a small overlay instead of the full network.

But a boundary needs something Pathfinder's radius query never asks for. Merchant discovery only needs travel times to the handful of vertices merchants snap to, so it can stop at the overlay. A boundary is drawn around the road network itself, which means the travel time at every vertex of every road the wavefront touched. That takes a third phase: descending back into each touched cell and filling in its interior from the boundary labels the overlay just proved.

The descent stays exact, and the reason is worth stating precisely. Take the shortest path from the depot to some interior vertex v of cell c, and look at the last time that path enters c. It crosses at some boundary vertex b, and after that it never leaves c again — so the remainder is a path confined to the cell:

Seeding one multi-source Dijkstra per cell with all of that cell's boundary labels evaluates the minimum in a single sweep. In the demo below the CRP isochrone and a plain full-graph Dijkstra are run side by side on every query, and their maximum per-vertex disagreement is printed. Across 1.4 million vertex comparisons over random depots and caps it never exceeded 3 × 10⁻⁵ seconds — floating-point noise, not algorithmic error.

One detail that looks cosmetic and isn't: segments have to be clipped mid-block. The wavefront runs out of budget partway down a street far more often than it runs out exactly at a junction. Keeping only whole segments stops the zone at the last intersection before the cap, so a 15-minute boundary quietly becomes a 13-minute one on every long block. Interpolating the crossing point along the segment puts the edge of the zone where the clock actually runs out.

Step Two: A Buffer Without Polygon Booleans

Now the geometry. The reachable network is thousands of disconnected-looking polylines; the zone is the region within some walk of any of them — a couple of hundred meters, because a diner lives near a road, not on it.

The obvious implementation is to buffer each segment into a capsule and union the lot. This is where geometry libraries go to die. Thousands of overlapping capsules produce coincident edges, near-degenerate slivers, and robustness failures that surface on the one merchant in a thousand whose zone happens to touch a cul-de-sac at a bad angle — and that merchant's zone is broken in production until someone notices.

Rasterizing sidesteps all of it. Stamp the roads into a grid, compute each cell's distance to the nearest road, and the buffered union is just a level set:

The union comes free, because a distance field doesn't care how many segments produced it. There are no boolean operations to be non-robust about. The cost is quantization — bounded by the cell size, which is a dial rather than a robustness cliff. The distance transform itself is a two-pass 5-7-11 chamfer, accurate to about 2% of Euclidean, comfortably inside the error the raster already introduces.

Marching squares then extracts that level set as closed rings, and holes fall out for free as rings of opposite winding — the rail yard, the cemetery, the pocket across the expressway with no crossing for a mile. Two things there cost me real debugging time and are worth writing down:

Address crossings by grid edge, not by coordinate. Two adjacent cells share an edge and must agree on exactly where the contour crosses it. Interpolating from the same two corner samples happens to be bit-identical, so coordinate matching works — right up until it doesn't. Keying the stitcher on the edge index makes agreement structural rather than a floating-point coincidence, and removes epsilon matching from the code entirely.

Pad the grid, and pad it against the geometry you actually rasterized. If the level set touches the border, its contour is clipped, and a clipped contour is an open chain — the walk never returns to its start, the signed area is meaningless, and the ring silently fails to close. I hit this exactly once and it presented as delivery zones that shrank as the time cap grew. The cause was that road shape points lie slightly outside the bounding box of the road junctions, so padding measured against the graph's bounding box wasn't padding at all. The demo counts unclosed chains and shows the number; it should always be zero, and saying so out loud is cheaper than rediscovering it.

Step Three: Making It Shippable

The raw contour is faithful and useless: at 25-meter resolution a 15-minute zone comes off the raster with roughly eight thousand vertices. That is a payload to replicate to every service that needs it, and a point-in-polygon test proportional to it.

So it gets cleaned up. Holes below a threshold are filled — a genuine unreachable pocket is worth keeping, but a one-block hole is raster noise and punching it through a delivery zone helps nobody. Disconnected slivers below a threshold are dropped: real, but too small to staff or explain. Then Chaikin corner-cutting rounds the staircase the raster leaves behind, and Douglas–Peucker takes the vertex count down.

Simplifying a closed ring needs one adjustment, since there are no endpoints to anchor the recursion. Splitting at an arbitrary vertex tends to shave the ring's most distinctive corner — precisely the feature a zone is recognized by on a map. Anchoring at the two most distant vertices instead keeps the silhouette. And a ring that can't survive the tolerance gets dropped rather than passed through unsimplified: handing back the original is the tempting fallback, and it makes raising the tolerance increase the vertex count, which is exactly backwards.

On the numbers below, that pipeline takes a 15-minute zone from 7,909 contour vertices to 83 at a 100-meter tolerance — a 95× reduction — with coverage still at 100%.

The Two Errors, Measured

A boundary is a lossy compression of an isochrone, and compression introduces error in two opposite directions. Reporting only one of them is choosing which way to be wrong in silence, so Bounder reports both:

Coverage is how much reachable road ends up inside the polygon. Misses are the expensive failure, and the insidious one: a diner who could have been served is told nobody delivers to them, they close the tab, and no metric anywhere ever records the order that didn't happen. There is no feedback loop. This is the number you protect.

False inclusion is how much unreachable road ends up inside. Buffering and simplification both inflate the zone, and every point they add is an order promised at a drive time the router never agreed to — a late delivery, a refund, a courier stuck in traffic on a run that should never have been offered.

These trade against each other directly, and the buffer radius is the dial. Widen it and coverage is trivially safe while false inclusion climbs; on the sweep below, a 15-minute zone goes from 13.5% false inclusion at a 40-meter buffer to 73% at 300 meters. The right operating point isn't a geometry question — it's a question about which failure your marketplace can better absorb, which is exactly the kind of decision that should be a visible parameter rather than a constant buried in a geometry routine.

Both numbers are computed the same way on every query in the demo: take every junction in the graph, test it against the final polygon, and compare that verdict to what the router actually said. Drag the sliders and watch them move.

What This Version Leaves Out

The pipeline here is the real one; the operational scaffolding around it is not. Production Bounder regenerated zones on a schedule as traffic patterns shifted, which raises a problem this demo doesn't have: stability. A merchant's zone flickering between builds is its own kind of bug — support tickets about an address that worked yesterday, and no clean answer. It also had to accept manual overrides, because ops teams know things the road graph doesn't: a bridge closed for construction, a neighborhood a merchant simply refuses to serve, a tower whose loading dock faces the wrong street. Any generator that can't be overridden gets worked around instead.

The demo also runs one merchant at a time against a static graph. The real service ran the whole roster against a live-traffic overlay — which is precisely why it was built on CRP, where re-customizing the cliques against new traffic is cheap and the topology is untouched.