Buslyft's Real-Time Matching Algorithm: From Prototype to Production

The Matching Problem

At its core, ride-hailing is a bipartite matching problem: given a set of ride requests and a set of available drivers, find the assignment that minimizes total wait time (or maximizes some other objective) while respecting constraints like vehicle type and driver preferences.

Sounds simple. In practice, it's one of the hardest real-time optimization problems in production software — because the inputs are constantly changing. New requests arrive every second, drivers move, cancel, or go offline, and traffic conditions shift. Any solution that takes more than a few hundred milliseconds is already stale.

Buslyft processes over 120,000 ride requests per day across 8 African cities. Our dispatch engine matches riders to drivers with a median latency of 187 ms and achieves a match rate (percentage of requests that result in a completed ride) of 94.2%. Here's how we built it.

Graph-Based Dispatch

The Ride Graph

We model the dispatch problem as a weighted bipartite graph where:

• Left nodes = pending ride requests
• Right nodes = available drivers
• Edge weights = estimated cost of assigning that driver to that request

The cost function for each edge incorporates:

function edgeCost(request: RideRequest, driver: Driver): number {
  const eta = estimateETA(driver.location, request.pickup);
  const detour = estimateDetour(driver, request); // If driver has an active ride
  const driverPreference = driver.preferredZones.includes(request.zone) ? 0 : PREFERENCE_PENALTY;
  const vehicleMatch = request.vehicleType === driver.vehicleType ? 0 : Infinity;
  const earningsBalance = getEarningsBalanceFactor(driver); // Fairness: favor drivers with fewer recent rides

  return (
    WEIGHT_ETA * eta +
    WEIGHT_DETOUR * detour +
    WEIGHT_PREFERENCE * driverPreference +
    WEIGHT_FAIRNESS * earningsBalance +
    vehicleMatch
  );
}

Solving the Assignment

We run the Hungarian algorithm (also known as the Kuhn-Munkres algorithm) on this graph to find the minimum-cost perfect matching. The standard Hungarian algorithm has O(n^3) complexity, which becomes prohibitive when n (the number of pending requests and available drivers) is large.

Our optimization: we don't solve a single global matching. Instead, we partition the city into hexagonal zones using Uber's H3 spatial index, and solve smaller matching problems per zone plus a buffer ring of neighboring zones. This reduces the effective n per solve from thousands to typically 50–200, keeping latency well under our 300 ms target.

┌───────┐  ┌───────┐  ┌───────┐
│Zone A │──│Zone B │──│Zone C │
│ n=45  │  │ n=120 │  │ n=67  │
└───┬───┘  └───┬───┘  └───┬───┘
    │          │          │
    ▼          ▼          ▼
  Solve A    Solve B    Solve C   (parallel)
    │          │          │
    └──────────┴──────────┘
               │
          Conflict Resolution
               │
          Final Assignments

A conflict resolution pass handles edge cases where a driver near a zone boundary could have been assigned to requests in two different zones. We resolve conflicts greedily in favor of the lower-cost assignment.

Batch Window

We don't match requests one-at-a-time as they arrive. Instead, we accumulate requests in a 2-second batch window, then solve the matching for the entire batch simultaneously. This batching is critical — it allows the algorithm to find globally better assignments than a greedy first-come-first-served approach.

In A/B tests, batched matching reduced average rider wait time by 23% compared to greedy assignment.

ETA Prediction

Accurate ETA (Estimated Time of Arrival) is the single most important input to the matching algorithm. A bad ETA estimate leads to bad matches, which lead to long wait times and cancellations.

Road Graph

We maintain a detailed road graph of each city, built from OpenStreetMap data and enriched with:

• Historical speed data from GPS traces of Buslyft drivers (collected over 18 months)
• Turn penalties at intersections (turning left across traffic is slower than going straight)
• Periodic road closures (markets, construction, events) updated by local operations teams

Speed Prediction Model

Real-time ETAs require knowing current traffic conditions. We train a graph neural network (GNN) that takes as input:

• Time of day and day of week (one-hot encoded)
• Recent GPS probe speeds on each road segment (5-minute rolling average)
• Weather conditions (rain significantly impacts driving speeds in many African cities)
• Special events (holidays, football matches)

The GNN outputs predicted speed for every road segment in the city for the next 30 minutes. We update predictions every 5 minutes.

# Simplified ETA computation
def estimate_eta(origin: LatLng, destination: LatLng) -> float:
    path = shortest_path(road_graph, origin, destination)  # A* with traffic-aware weights
    eta_seconds = sum(
        segment.length_meters / predicted_speed(segment, now())
        for segment in path
    )
    return eta_seconds + PICKUP_OVERHEAD_SECONDS

Our ETA model achieves a mean absolute error of 1.8 minutes across all cities, with accuracy improving in cities where we have more historical data.

Dynamic Pricing (Surge)

When demand exceeds supply, we apply dynamic pricing to balance the marketplace. Our pricing model is more nuanced than a simple multiplier.

Zone-Level Supply-Demand Score

Every 30 seconds, we compute a supply-demand score for each H3 zone:

SD_score = (pending_requests - available_drivers) / max(available_drivers, 1)

When SD_score exceeds a threshold (calibrated per city), we activate surge pricing. The surge multiplier is a continuous function of the SD_score, capped at 2.5x:

multiplier = min(2.5, 1.0 + 0.3 × max(0, SD_score - threshold))

Anti-Gaming Measures

Surge pricing creates incentives for manipulation. We guard against:

• Driver collusion: If multiple drivers in the same zone go offline simultaneously (to artificially inflate surge), our system detects the pattern and maintains the pre-offline pricing for 10 minutes
• Phantom rides: Fake ride requests designed to trigger surge. We use device fingerprinting and ride-completion-rate heuristics to detect and block suspicious accounts
• Price anchoring: We always show the estimated total fare before the rider confirms, and we honor that estimate even if surge increases during the ride

Production Architecture

The matching engine runs on a dedicated Kubernetes cluster with:

• Matching service (Rust, for performance): Receives batched requests, builds the bipartite graph, solves the Hungarian algorithm, and emits assignments. Stateless, horizontally scalable
• State service (Go): Maintains the real-time positions and availability status of all drivers. Uses a Redis-backed geospatial index for fast nearest-neighbor queries
• ETA service (Python + C++ extension): Runs the GNN and Dijkstra/A* routing. Pre-computes and caches ETAs for common origin-destination pairs

All three services communicate via gRPC with strict latency budgets:

| Service | P50 Latency | P99 Latency | Budget | |---|---|---|---| | State lookup | 8 ms | 25 ms | 50 ms | | ETA computation | 35 ms | 90 ms | 120 ms | | Matching solve | 45 ms | 180 ms | 200 ms | | End-to-end | 120 ms | 280 ms | 300 ms |

Results and Impact

Since launching Buslyft in Lagos and Nairobi in 2025, we've expanded to 8 cities with the following metrics:

• 94.2% match rate (percentage of requests resulting in a completed ride)
• Average rider wait time: 4.1 minutes (down from 7.8 minutes with our v1 greedy algorithm)
• Driver utilization: 68% of online time spent on active rides (up from 52%)
• Peak throughput: 340 matches/second during Friday evening rush in Lagos

Get started with Buslyft at buslyft.com.