Design the ride-hailing matching and pricing system for a platform like Uber. When a rider requests a ride, the system must find the nearest available drivers, estimate time of arrival, compute a dynamic price based on supply and demand, and match the rider to a driver, all within seconds. The platform operates in hundreds of cities with millions of drivers and riders, and the matching must account for driver availability, traffic conditions, driver preferences (direction, distance), and rider wait time.
The ETA model must predict travel time from the driver to the pickup point and from pickup to destination, accounting for real-time traffic, road network, and time of day. The surge pricing model must balance supply and demand in real time while remaining transparent to riders. The system must handle peak hours when demand far exceeds supply, and it must gracefully degrade when GPS or network connectivity is poor.
How would you design this system? Cover the geospatial indexing architecture (quadtree vs H3 vs geohash), the driver-rider matching algorithm, the ETA prediction model, the dynamic pricing strategy, and how you handle peak load and graceful degradation.
The Problem: the nearest car on the map is rarely the nearest car in traffic, and the right price changes minute by minute. The system must pick a driver, an ETA, and a price before the rider closes the app.
Answer
The design is a city-sharded real-time marketplace built on three layers: an in-memory geospatial index that answers “who is near this point” in tens of milliseconds, a batched assignment solver that matches a small window of requests and drivers jointly, and two learned models (ETA and demand/supply forecasting) that supply the numbers the solver and the pricing engine consume. The pivotal decisions are to index driver locations with H3 hexagons and retrieve candidates by k-ring expansion rather than radius scans, to replace greedy first-come dispatch with a min-cost bipartite match over a 2-5 second window, and to compute ETA as a routed baseline plus a learned residual so the physics and the learning each do what they are good at. Everything sits behind a degradation ladder, so bad GPS or a dead model server produces a worse ride rather than a hard failure in most cases.
(1) H3 Hexagonal Index: driver positions live in a sharded in-memory store keyed by H3 cell at resolution 8-9, and candidate retrieval expands k-rings until enough drivers are found, so neighbor distance is uniform in every direction.
(2) Batched Bipartite Matching: requests accumulate for a few seconds per cell cluster, then a min-cost assignment over pickup ETA, accumulated rider wait, and predicted driver acceptance beats greedy nearest-car dispatch on total wait.
(3) Two-Stage ETA: route the road graph with live segment speeds for the physical baseline, then a learned residual model corrects for pickup friction, time of day, and driver behavior, with a quantile head for the pessimistic bound shown to riders.
(4) Capped Cell-Level Surge: the multiplier comes from a smoothed demand/supply ratio per cell over a short window, is capped and hysteresis-smoothed to stop oscillation, and is folded into a single upfront price the rider sees before confirming.
(5) City-Level Isolation: each city is an independent dispatch shard with its own index, models, and pricing state, so a stadium letting out in one market cannot stall dispatch in another.
(6) Degradation Ladder: map matching and dead reckoning for noisy GPS, cached-speed ETA when the model server is unhealthy, greedy dispatch when the solver is down, and last-known-cell routing during connectivity loss.
Figure 1: The dispatch path: request → cell lookup → candidate filter → ETA scoring → batched assignment → dispatch and quote, with the location stream, road graph, and surge engine feeding each stage from below.
Clarify Before Designing:
(1) Product Scope: single rider-to-driver trips only, or pooled and scheduled rides too, since pooling turns assignment into a vehicle-routing problem with a different solver?
(2) Latency Budget: how long between tap and price quote, and how many seconds may a request sit in a batching window before the rider perceives a stall?
(3) Objective Weights: are we minimizing rider wait, maximizing completed trips, or maximizing marketplace earnings, and how heavily does driver fairness and utilization count?
(4) Pricing Constraints: regulatory multiplier caps, emergency policies, upfront fixed price versus metered fare, and what transparency the rider is legally owed?
(5) Data Coverage: do we have historical GPS traces and a maintained road graph in every city, or are we launching cold-start markets with no traffic history?
(6) Partition Posture: during a network partition, do we prefer to refuse dispatch or risk a double assignment, given the safety and trust cost of two drivers arriving?
Leave a Reply