[System Design] Ride-Hailing Dispatch Algorithm: How Uber DISCO & Grab DispatchGym Match Drivers

Every time you tap "Book Ride," a system makes dozens of decisions in under two seconds: Which driver? What route? What's the real ETA? This article breaks down exactly how the dispatch algorithm works — from the greedy approach that fails at scale, to the bipartite graphs, batched matching, and surge pricing mechanics that power Uber, Lyft, Grab, and Gojek today. Why a Greedy Dispatch Algorithm Fails (Closest Driver Problem) The first instinct when designing a matching system is to pair every customer with their nearest driver. However, this Greedy approach causes massive losses at a system-wide scale: Example: 3 riders (R1, R2, R3) and 3 drivers (D1, D2, D3) Greedy Matching (closest driver): R1 ← D1 (ETA 2 mins) ✓ R2 ← D3 (ETA 8 mins) ← D2 was "taken" by R1, even though D2 is closer to R2 R3 ← D2 (ETA 10 mins) ← Terrible outcome Total ETA: 2 + 8 + 10 = 20 minutes Optimal Matching (global optimal): R1 ← D2 (ETA 3 mins) R2 ← D1 (ETA 3 mins) R3 ← D3 (ETA 4 mins) Total ETA: 3 + 3 + 4 = 10 minutes ← 50% better! Uber refers to this problem as Global Optimization — finding an assignment strategy that minimizes the total ETA of the entire system , rather than optimizing just for individual pairs. Bipartite Graph Matching: The Mathematical Foundation (Lyft) Before diving into the systems, it helps to understand the mathematical model that all ride-hailing matching engines share at their core. Lyft formalizes dispatch as a bipartite graph matching problem : Bipartite Graph: Set A (Riders): { R1, R2, R3, R4 } Set B (Drivers): { D1, D2, D3, D4, D5 } Edges: every possible Rider ↔ Driver pair Edge Weight: cost of that match (e.g., ETA, driver rating, distance) Goal: Find a set of edges (a "matching") where: - No rider is matched to more than one driver - No driver is matched to more than one rider - The total cost of all selected edges is minimized This is known as the Minimum Weight Bipartite Matching problem. The classical algorithm for solving it is the Hungarian Algorithm (also called the Kuhn-Munkres algorithm), which runs in O(n³) time. Why Batching Matters for Bipartite Matching The key insight is that you can only find a globally optimal bipartite matching if you have multiple riders and drivers available simultaneously . If you match greedily (one-by-one as requests arrive), you lose the ability to find the global optimum. This is why all major ride-hailing platforms introduce a batching window : Batching Strategy: 1. Collect all ride requests in a 2-5 second window 2. Build a complete Rider × Driver cost matrix 3. Run the Hungarian Algorithm on the full batch 4. Dispatch all assignments simultaneously Result: System-wide optimal — not just locally optimal for each individual request Approach Latency Global Optimality Scalability Pure Greedy Near-zero Poor High Batched Matching 2-5 seconds Excellent Medium RL-Adaptive Batching Dynamic Excellent High Uber DISCO: The Core Dispatch Algorithm Architecture DISCO (Dispatch Optimization) is Uber's matching system, responsible for pairing millions of ride requests with drivers every day. Overall Architecture ┌─────────────────┐ ┌─────────────────┐ │ Rider App │ │ Driver App │ │ "Book Ride" │ │ GPS, Status │ └────────┬────────┘ └────────┬────────┘ │ │ ▼ ▼ ┌─────────────────┐ ┌─────────────────┐ │ Demand Service │ │ Supply Service │ │ (Ride Requests)│ │ (Driver Pool) │ └────────┬────────┘ └────────┬────────┘ │ │ └──────────┬────────────┘ ▼ ┌─────────────────────┐ │ DISCO Engine │ │ │ │ 1. Candidate Filter │ ← S2/H3 Geospatial Query │ 2. ETA Calculator │ ← Routing Service + DeepETA │ 3. Batch Optimizer │ ← Hungarian Algorithm │ 4. Dispatch │ ← RAMEN Push └─────────────────────┘ Step 1: Candidate Filtering When a ride request arrives, DISCO doesn't check every driver. It uses the rider's S2 Cell ID (or H3) to rapidly narrow down the list: Input: Rider location → S2 Cell Level 12 Action: Find all neighboring S2 cells (covering circle radius ~3km) Query: Redis/Memory → Retrieve list of drivers