Route Finding & ETA Backbone

The problem: routing for a ride-hailing service

A ride-hailing platform is, underneath the app, a giant matching and routing engine. A rider taps a pickup point $s$ and a destination $t$, and before anything else can happen — before a price is quoted, before a driver is dispatched, before an ETA is shown — the system has to answer two coupled questions on a real road network:

1. What is the fastest route from $s$ to $t$ given current road geometry, one-way streets, and turn restrictions?
2. What is the travel time (the ETA) along that route?

And it does not answer this once. Every pricing estimate, every driver-to-rider assignment, every in-trip reroute, and every "drivers near you" ranking is built on top of this same primitive, called over and over.

Functional requirements — what the routing layer must do:

• Compute the time-optimal path between any two points in a city graph.
• Return the duration of that path (the ETA backbone) and the route geometry.
• Support many-to-many queries — e.g. the ETA from a rider to each of hundreds of nearby drivers (Unit 2 builds directly on this).
• Re-route quickly when a driver goes off-route or conditions change.
• Respect directionality: roads are one-way, U-turns are restricted, weights are asymmetric.

Non-functional requirements — the constraints that make it hard:

• Latency. A single route query sits on the critical path of a tap. Tens of milliseconds at p99, not seconds.
• Throughput. A large market generates routing and ETA calls on the order of millions per minute across pricing, dispatch, and tracking.
• Scale. A metro graph has $10^5$–$10^6$ nodes; a country graph reaches into the tens of millions.
• Freshness. Edge weights are not constant — traffic, incidents, and road closures change them continuously.

Notice the tension baked into these requirements: the graph is huge, the query budget is tiny, and the volume is enormous. The entire arc of this unit is about resolving that tension by moving work offline — paying a one-time preprocessing cost so that each online query touches as few nodes as possible.

Every example below routes between the same two points on a real 10,000-node San Francisco drive network: pickup A and destination B. The map is that graph — each line is a drivable segment, and the highlighted route is the fastest path. As we change algorithms, the route never changes; only the number of nodes each one must explore to find it shrinks. That shrinking explored set is the whole story.

Note this is the fastest route, not the shortest in distance. Almost every ride-hailing service optimizes for time, because ETA and fare both depend on duration — a longer freeway path usually beats a shorter crawl through residential streets.