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 in those cells
Filters:
✓ Status = AVAILABLE (not currently carrying a passenger)
✓ Vehicle type matches (Car, Bike, SUV, etc.)
✓ Capacity is sufficient (if a group ride)
✓ Not blocked by the rider
Output: ~10-30 candidate drivers
S2 vs H3: Choosing the Right Spatial Index
Uber originally used S2 geometry (quad-tree squares) for spatial sharding but later developed H3 (hexagons). The difference matters for how the engine finds candidate drivers:
| S2 Geometry (Google) | H3 (Uber) | |
|---|---|---|
| Cell shape | Square | Hexagon |
| Neighbor equidistance | No (diagonal cells are further) | Yes (all 6 neighbors equidistant) |
| Best for | Precise geofencing, hierarchical sharding | Proximity search, surge heatmaps |
| Used by | Lyft, early Uber DISCO | Modern Uber, Grab |
Step 2: ETA Calculation with DeepETA
Straight-line (crow-fly) distance is meaningless in the real world — 500m straight-line might be a 3km drive (due to bridges, intersections, or one-way streets).
Candidate drivers: [D1, D2, D3, D4, D5]
Rider position: R1
Routing Service calculates actual ETA based on:
- Digitized road network graph
- Real-time traffic data
- One-way streets, overpasses, tunnels
- Rush hours / historical traffic patterns
Results:
D1: 800m crow-fly → 2.3km road → ETA 4 mins (heavy traffic)
D2: 1.2km crow-fly → 1.5km road → ETA 3 mins (clear roads) ← Better!
D3: 600m crow-fly → 3.8km road → ETA 7 mins (must U-turn)
Uber developed DeepETA — a hybrid deep learning approach that sits on top of the traditional routing engine:
DeepETA Architecture:
1. Traditional Router → "Naive ETA" (e.g., 4 mins based on road graph)
2. Deep Neural Network → "Residual Prediction" (e.g., +1.5 min due to
traffic signal, weather, specific intersection complexity)
3. Final ETA = Naive ETA + Residual
Input features to the DNN:
- GPS coordinates (cleaned by Kalman Filter)
- Time of day, day of week
- Historical traffic at this location
- Driver/vehicle attributes
- Trip type (airport, downtown, etc.)
Kalman Filter role: Raw GPS signals are noisy in urban environments (tall buildings, tunnels). A Kalman Filter smooths the GPS stream before it feeds into DeepETA, ensuring the model learns from accurate positional data rather than jittery raw coordinates.
Step 3: Batched Matching
This is the most crucial and complex step. Instead of processing each request individually, DISCO batches requests within a short time window (a few seconds) and solves the optimal assignment problem for the entire batch.
Batching Window: 2 seconds
Within 2 seconds, the system receives:
Ride Requests: [R1, R2, R3, R4, R5]
Available Drivers: [D1, D2, D3, D4, D5, D6, D7]
Build Cost Matrix (ETA between every rider-driver pair):
D1 D2 D3 D4 D5 D6 D7
R1 [ 3 5 8 2 7 9 4 ]
R2 [ 6 2 4 7 3 5 8 ]
R3 [ 4 7 3 5 6 2 9 ]
R4 [ 8 4 6 3 5 7 2 ]
R5 [ 5 6 2 8 4 3 7 ]
The Problem: Find a 1-to-1 assignment such that the total cost is minimized.
→ Hungarian Algorithm (or Auction Algorithm)
The Hungarian Algorithm
This is a classic algorithm used to solve the Assignment Problem with a time complexity of O(n³):
Input: N×M Cost Matrix (N riders, M drivers, M ≥ N)
Output: Optimal 1-to-1 assignment
Optimal Results:
R1 ← D4 (ETA 2 mins)
R2 ← D2 (ETA 2 mins)
R3 ← D6 (ETA 2 mins)
R4 ← D7 (ETA 2 mins)
R5 ← D3 (ETA 2 mins)
Total ETA: 10 minutes (compared to a Greedy approach which might yield 20+ minutes)
Ringpop — Distributed Coordination
DISCO runs on multiple servers. How do we ensure two different DISCO servers don't attempt to assign the exact same driver to two different riders?
Uber developed Ringpop — a consistent hashing library based on the SWIM (gossip) protocol:
Ringpop Hash Ring:
Server A ────── Server B ────── Server C ────── Server A
│ │ │
▼ ▼ ▼
Riders & Riders & Riders &
Drivers Drivers Drivers
in Zone 1 in Zone 2 in Zone 3
Each S2 Cell is hashed to a specific DISCO server.
→ All requests and drivers within the same area are processed by the SAME DISCO server.
→ No conflict during assignment.
SWIM Protocol: Every DISCO node periodically "pings" other nodes to check if they are alive. If a node goes down, the ring auto-rebalances — the S2 cells of the dead node are transferred to neighboring nodes in the ring.
Fault Tolerance: State Digest
The problem: If an Uber data center goes down abruptly, will the states of all in-flight trips be lost?
Uber's clever solution: Encrypted State Digest — DISCO periodically pushes the trip state (encrypted) down to be stored directly on the driver's phone.
Normal Flow:
DISCO Server ◄──── state ────► Driver Phone
(Source of truth) (Backup copy)
When a data center crashes:
1. A new DISCO Server boots up
2. Driver phones reconnect
3. DISCO requests driver phones to send back the state digest
4. DISCO decrypts and restores the state of all in-flight trips
5. The system continues operating without dropping a single ride
From Heuristics to Machine Learning: Gojek Jaeger
Gojek's evolution from a simple dispatch heuristic to a production ML system is a masterclass in how marketplace complexity forces you to rethink single-objective optimization.
The Problem with a Single ML Model
Gojek's initial approach used a single machine learning model to rank and select drivers. It worked — until it didn't. The model optimized aggressively for its primary metric (say, acceptance rate) and created feedback loops:
Feedback Loop Problem:
1. Model learns: "Drivers in Zone A accept 90% of the time"
2. Model always sends orders to Zone A drivers
3. Zone A drivers get overwhelmed, acceptance rate drops
4. Zone B drivers are idle, marketplace liquidity drops
5. Riders in Zone B wait longer → lower satisfaction
A single-objective model cannot balance competing goals without explicit guardrails.
Jaeger: Multi-Objective Allocation
Gojek built Jaeger — a multi-objective allocation framework that simultaneously optimizes for:
Jaeger Optimization Objectives:
↓ Minimize pickup ETA (rider experience)
↑ Maximize driver utilization (driver earnings)
↑ Maximize acceptance rate (marketplace flow)
↑ Ensure fairness (prevent driver starvation)
Architecture:
[Real-time Features] ←── GPS, traffic, demand heatmaps
│
▼
[ML Models] ←── Acceptance probability, ETA model
│
▼
[Manual Configs] ←── Business rules, fairness floors
│
▼
[Jaeger Aggregator] ←── Weights & combines all signals
│
▼
[Driver Score] ←── Final ranking for dispatch
The Manual Configs layer is intentional: it gives business teams control to override ML decisions in edge cases (market launches, weather events, regulatory requirements) without retraining the entire model.
The Future: Reinforcement Learning & MDP in Dispatching (Grab DispatchGym)
The Hungarian algorithm solves the immediate assignment optimally. But it has a fundamental limitation: it only optimizes for the current batch. It cannot answer questions like:
- Should I assign a driver now, or wait 30 seconds for a better match?
- If I send this driver 5km across town, will that leave a coverage gap for the next surge?
This is where Reinforcement Learning (RL) and the Markov Decision Process (MDP) formulation come in.
Dispatch as a Markov Decision Process
An MDP models dispatch as a sequence of decisions where each action affects future states:
MDP Formulation for Dispatch:
State (S):
- Current positions of all idle drivers
- Pending ride requests and their locations
- Time of day, predicted demand heatmap
- Traffic conditions across all zones
Action (A):
- Assign Driver D to Rider R
- Hold Driver D idle (wait for a better request)
- Reposition Driver D to Zone X (proactive repositioning)
Transition (T):
- Probability that action A in state S leads to state S'
- e.g., P(driver ends up in Zone B | assigned to trip starting in Zone A)
Reward (R):
- Positive: completed trip, short pickup ETA, high acceptance
- Negative: long idle time, deadhead mileage, rider cancellation
The key difference from greedy matching: the RL agent learns to make decisions that maximize cumulative long-term reward — not just the immediate reward for a single trip.
Grab DispatchGym
Grab built DispatchGym to make RL research accessible for dispatching problems. Its design solves a core challenge: training RL agents in production is dangerous (bad policies lose money and drivers). DispatchGym provides a safe, simulated environment:
DispatchGym Architecture:
┌───────────────────────────────────┐
│ Simulation Layer │
│ - Replays historical trip data │
│ - Injects synthetic demand spikes │
│ - Models driver behavior │
└────────────────┬──────────────────┘
│ State observation
▼
┌───────────────────────────────────┐
│ RL Agent (Policy) │
│ - Gymnasium API compatible │
│ - Trainable with any RL algo │
│ (PPO, SAC, DQN...) │
└────────────────┬──────────────────┘
│ Action (dispatch decision)
▼
┌───────────────────────────────────┐
│ Reward Computation │
│ - Total completed trips │
│ - Average pickup ETA │
│ - Driver earnings equity │
│ - Acceptance rate │
└───────────────────────────────────┘
Deployment:
Reward stabilizes → A/B test in production → Gradual rollout
Multi-Agent RL: When One Agent Isn't Enough
A single RL agent controlling an entire city's fleet hits the curse of dimensionality — the state-action space is too large. The solution is Multi-Agent Reinforcement Learning (MARL):
MARL for Dispatch:
- Each geographic zone (or each driver) is an independent agent
- Agents observe their local state (nearby riders, driver density)
- Agents take local actions (match, hold, reposition)
- Coordination mechanism ensures global objectives are met
Paradigm: Centralized Training, Decentralized Execution (CTDE)
- During training: agents share global information to learn cooperation
- During execution: each agent acts on local observations only
- Result: Scales to city-wide fleets without centralized bottleneck
Academic research on MARL-based dispatch suggests wait time reductions of 25–40% compared to greedy baselines, with significant improvements in driver idle mileage — though real-world results vary by city density and fleet size.
Grab's Fulfilment Platform Architecture
Grab doesn't just run ride-hailing — it runs food, groceries, express delivery, and financial services on the same driver network. Early on, each vertical had its own dispatch engine, causing massive inefficiency.
Grab solved this with the Fulfilment Platform — a unified three-layer architecture:
┌────────────────────────────────────────┐
│ Business Verticals │
│ GrabCar | GrabFood | GrabMart | ... │
└───────────────┬────────────────────────┘
│ Demand signals
▼
┌────────────────────────────────────────┐
│ Fulfilment Platform │
│ - Unified dispatch engine │
│ - Supply shaping & driver incentives │
│ - Global optimization across verticals│
└───────────────┬────────────────────────┘
│ Infrastructure
▼
┌────────────────────────────────────────┐
│ Technology Infrastructure │
│ - DynamoDB (OLTP: live orders) │
│ - MySQL partitioned (OLAP: analytics) │
│ - 1,000+ microservices on AWS/GCP │
└────────────────────────────────────────┘
The critical innovation: a driver finishing a GrabFood delivery can be immediately available for a GrabCar ride — the same Fulfilment Platform sees the full picture and can optimize across verticals. This eliminated "dead time" between trips and significantly improved driver earnings.
Key Metrics for the Matching Engine
| Metric | Meaning | Target |
|---|---|---|
| P50/P99 Matching Latency | Time from request received to dispatch | < 2 seconds (P99) |
| Acceptance Rate | % of drivers accepting when offered | > 85% |
| ETA Accuracy | Error margin between predicted and actual ETA | < 20% |
| Match Rate | % of requests successfully matched | > 95% |
| Total Wait Time | Total time a rider waits (rider + driver travel time) | Minimize |
| Driver Idle Mileage | Distance driven without a passenger | Minimize |
| Marketplace Liquidity | Balance of supply/demand across zones | Maintain |
FAQ: Dispatch Algorithms
What is a dispatch algorithm?
A dispatch algorithm is a system used by ride-hailing platforms like Uber and Grab to optimally match riders with available drivers. It goes beyond finding the closest driver by using batched matching and global optimization to minimize the total wait time (ETA) for all users.
How does Uber match riders and drivers?
Uber uses a system called DISCO that batches ride requests every 2-5 seconds and applies the Hungarian algorithm for global optimization across the entire batch. This ensures system-wide efficiency, not just locally optimal matches for each individual request.
Why is reinforcement learning used in ride-hailing?
RL models treat dispatching as a Markov Decision Process (MDP), allowing the system to optimize for long-term marketplace liquidity and driver earnings, rather than just immediate wait times. Platforms like Grab use RL via DispatchGym to learn when to hold a driver for a better future match, rather than always assigning immediately.
What is the difference between S2 and H3 in dispatch systems?
S2 (Google) uses square cells and is excellent for precise geofencing and hierarchical sharding. H3 (Uber) uses hexagonal cells, which offer uniform adjacency — all 6 neighbors are equidistant — making proximity searches and surge pricing heatmaps more accurate for real-time matching.
Next, we will look into Surge Pricing — the dynamic pricing system based on real-time supply and demand ratios. Continue reading Part 5 — Surge Pricing: Dynamic Pricing Based on Real-time Supply and Demand.
This post was originally published on my blog at Ride-Hailing Dispatch Algorithm: How Uber DISCO & Grab DispatchGym Match Drivers.
Hi, I'm Lê Tuấn Anh (vesviet) 👋
I am a Senior Go Backend Architect & Distributed Systems Engineer with 17+ years of experience building high-traffic platforms (25M+ requests/month).
If you enjoyed this deep-dive, let's connect on LinkedIn or explore my consulting services at tanhdev.com/hire.