[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 (