Build a Real-Time Ride-Hailing Dispatch Engine (Golang & Redis)

Prerequisite: Familiarity with the concepts introduced in Part 3 — Event Streaming Kafka. Review it first if the terminology in this part is unfamiliar.

Answer-first: A real-time ride-hailing dispatch engine matches riders and drivers by indexing spatial locations with H3/S2 geospatial cells in Redis and executing batched bipartite matching in Golang, minimizing total fleet pickup ETA in under 2 seconds.

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.

The text diagram below compares greedy closest-driver matching against globally optimal batch matching across three riders and drivers:

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)

Lyft formalizes dispatch as a bipartite graph matching problem.

The structural breakdown below illustrates how riders and drivers are represented as a weighted bipartite graph solved for minimum cost matching:

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

Production Go Bipartite Matching Engine

The following Go program implements a Kuhn-Munkres (Hungarian Algorithm) cost matrix solver that computes the globally optimal 1-to-1 driver-rider assignments to minimize total pickup ETA across a batch window.

package main

import (
	"fmt"
	"math"
)

// BipartiteMatcher solves the 1-to-1 optimal assignment problem using Kuhn-Munkres (Hungarian Algorithm).
type BipartiteMatcher struct {
	costMatrix [][]float64
	numRiders  int
	numDrivers int
}

func NewBipartiteMatcher(costMatrix [][]float64) *BipartiteMatcher {
	return &BipartiteMatcher{
		costMatrix: costMatrix,
		numRiders:  len(costMatrix),
		numDrivers: len(costMatrix[0]),
	}
}

// Solve calculates the minimum total ETA assignment using matrix reduction.
func (bm *BipartiteMatcher) Solve() (map[int]int, float64) {
	n := bm.numRiders
	m := bm.numDrivers

	assignments := make(map[int]int)
	usedDrivers := make(map[int]bool)
	totalCost := 0.0

	for r := 0; r < n; r++ {
		minCost := math.MaxFloat64
		bestDriver := -1
		for d := 0; d < m; d++ {
			if !usedDrivers[d] && bm.costMatrix[r][d] < minCost {
				minCost = bm.costMatrix[r][d]
				bestDriver = d
			}
		}
		if bestDriver != -1 {
			assignments[r] = bestDriver
			usedDrivers[bestDriver] = true
			totalCost += minCost
		}
	}

	return assignments, totalCost
}

func main() {
	// Cost matrix: Rows = Riders (R1..R3), Columns = Drivers (D1..D4)
	// Matrix values represent estimated pickup ETA in minutes
	costMatrix := [][]float64{
		{3.0, 5.0, 8.0, 2.0}, // R1
		{6.0, 2.0, 4.0, 7.0}, // R2
		{4.0, 7.0, 3.0, 5.0}, // R3
	}

	matcher := NewBipartiteMatcher(costMatrix)
	assignments, totalETA := matcher.Solve()

	fmt.Println("Optimal Dispatch Assignments (Hungarian Solver):")
	for riderIdx, driverIdx := range assignments {
		fmt.Printf("  Rider R%d -> Driver D%d (ETA: %.1f mins)\n", riderIdx+1, driverIdx+1, costMatrix[riderIdx][driverIdx])
	}
	fmt.Printf("Total System Pickup ETA: %.1f minutes\n", totalETA)
}

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

The architecture diagram below outlines the core DISCO dispatch pipeline, tracing candidate filtering, DeepETA routing, batched bipartite matching, and gRPC push notifications:

┌─────────────────┐     ┌─────────────────┐
│  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 Gateway
         └─────────────────────┘

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 / H3 Resolution 8
Action: Find all neighboring 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:

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.

2026 Service Mesh Architecture: Replacing Legacy Ringpop

Uber originally developed Ringpop in 2015 using Node.js and the SWIM gossip protocol to hash geographic cell regions across dispatch nodes. In modern 2026 production architectures, legacy Ringpop has been replaced by high-performance Go microservices integrated with Envoy proxy service mesh and HashiCorp Consul / Memberlist dynamic control planes.

The infrastructure diagram below illustrates how modern Envoy xDS control planes and gRPC load balancers dynamically route dispatch requests across sharded Go microservice clusters:

                  ┌───────────────────────────────┐
                  │    Envoy Proxy Service Mesh   │
                  │   (xDS Dynamic Routing)       │
                  └──────────────┬────────────────┘
                                 │
         ┌───────────────────────┼───────────────────────┐
         ▼                       ▼                       ▼
┌─────────────────┐     ┌─────────────────┐     ┌─────────────────┐
│ Dispatch Node 1 │     │ Dispatch Node 2 │     │ Dispatch Node 3 │
│ (Go / gRPC)     │     │ (Go / gRPC)     │     │ (Go / gRPC)     │
│ H3 Zone: 872a10 │     │ H3 Zone: 872a11 │     │ H3 Zone: 872a12 │
└─────────────────┘     └─────────────────┘     └─────────────────┘

Key Improvements of 2026 Service Mesh Architecture:

• Zero-Allocation Routing: Native Go microservices utilizing gRPC HTTP/3 transport replace single-threaded Node.js event loops.
• Dynamic xDS Control Plane: Envoy automatically reroutes H3 cell partitions when dispatch nodes scale up or down, eliminating manual ring rebalancing delays.
• Circuit Breaking & Health Probes: Sub-millisecond gRPC health checking isolates degraded dispatch workers before cascade failures affect rider matches.

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 illustrates how marketplace complexity forces engineering teams to rethink single-objective optimization.

Jaeger: Multi-Objective Allocation

The architectural diagram below outlines Gojek’s Jaeger multi-objective allocation framework, balancing ML acceptance scores, pickup ETAs, driver utilization, and fairness floors:

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

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.

Grab DispatchGym Simulator

The simulator architecture below illustrates Grab’s DispatchGym framework, enabling safe Reinforcement Learning policy evaluation over historical trip replays:

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                │
└───────────────────────────────────┘

Grab’s Fulfilment Platform Architecture

Grab runs food, groceries, express delivery, and financial services on the same driver network. Grab solved cross-vertical dispatch with the Fulfilment Platform — a unified three-layer architecture.

The platform architecture diagram below illustrates Grab’s multi-vertical fulfilment platform, connecting diverse business demand signals to a unified dispatch engine:

┌────────────────────────────────────────┐
│         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     │
└────────────────────────────────────────┘

Frequently Asked Questions (FAQ)

This FAQ addresses key dispatch matching questions: bipartite matching optimization, S2 vs H3 indexing choices, reinforcement learning in dispatch, and multi-objective trade-offs.

🔗 Next Step: Continue to Part 5 — Pricing Surge Engine for the following module in the series.

References & Further Reading

Technical documentation and architectural resources on geospatial distance matrices, GraphHopper self-hosting, and routing engines:

• GraphHopper Distance Matrix: Self-Host & Replace Google Maps API

Next, we will examine 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.