Ride-hailing dispatch: greedy vs batched matching, an interactive simulator

A ride-hailing or delivery platform has to decide which driver goes to which request. The obvious rule, send the nearest free driver the moment a request arrives, is fast and locally sensible, but it ignores the next request a few seconds later. Batched matching collects requests for a few seconds and assigns all of them at once to minimise total pickup time, which shortens pickups for everyone and, when drivers are scarce, keeps the whole system from tipping into long, empty drives.

The playground shows one moment matched both ways, then an hour of a city with 30 drivers under three policies. Raise the demand and compare.

Why greedy matching wastes driving

In the snapshot, rider 1 takes the driver 1.6 km away, although another is only 1.7 km away. The one it took was 0.2 km from rider 6, who asks later and gets a driver 3.1 km away instead. Rider 2 does the same to rider 5. Matching all six at once gives riders 1 and 2 slightly longer pickups and riders 5 and 6 much shorter ones: 11.2 km of pickup driving in total instead of 15.4.

Over a whole hour the difference depends on how scarce drivers are. When drivers are plentiful, every policy finds someone nearby and the averages barely differ. When requests outnumber free drivers, greedy dispatch sends each newly free driver to the oldest waiting rider, wherever that rider is. Drivers spend their time on long empty drives, fewer trips get done, the queue grows, and pickups get longer still. At 4 requests a minute, greedy drivers drive empty 61% of the time and complete 134 trips; batching every 10 seconds brings empty driving down to 42%, completes 198 trips, and halves the time from request to pickup. Ride-hailing researchers call this failure the wild goose chase.

Making batching work in production

• Use travel times, not distances: the cost matrix comes from the routing service’s ETAs, which see rivers, one-way streets and traffic.
• Keep batches small: partition the city into cells, for example with geohashes or H3, and match within each cell and its neighbours every few seconds, so the assignment problem stays tiny.
• Limit how long anyone waits: a pure minimum-total-distance match can leave a remote rider unmatched batch after batch; add a penalty that grows with wait time.
• Beyond the current batch: send idle drivers towards where demand is forecast, and use prices that rise when drivers are scarce, so the system never reaches the point where every driver is chasing distant riders.

A batch assignment in code

from scipy.optimize import linear_sum_assignment
import numpy as np

def dispatch_batch(riders, drivers, eta):
    """Match everyone waiting to free drivers, minimising total pickup time.
    eta(rider, driver) -> minutes, e.g. from the routing service."""
    if not riders or not drivers:
        return []
    cost = np.array([[eta(r, d) for d in drivers] for r in riders])
    rows, cols = linear_sum_assignment(cost)          # Hungarian algorithm, handles rectangles
    return [(riders[i], drivers[j]) for i, j in zip(rows, cols) if cost[i, j] < 15]

# every few seconds, per city cell:
#   pairs = dispatch_batch(waiting_riders(cell), free_drivers(cell), eta)
#   offer each pair; riders not matched wait for the next batch

In a system design interview

For ride-hailing or food delivery, describe the matcher, not just the location index: “Driver locations stream into an in-memory geo index sharded by city cell. Every two seconds a matcher per cell takes waiting requests and free drivers in the cell and its neighbours, gets ETAs from the routing service, and solves the assignment that minimises total pickup time with a wait-time penalty. Offers go out; a driver who declines returns to the pool for the next batch.” Expect the follow-ups: double-assigning a driver across neighbouring cells, stale driver locations, and how surge pricing interacts with dispatch.

Read the guide to dispatch and marketplace matching or location tracking at scale, see shortest path routing for the ETAs, or watch a strong candidate design a ride-sharing service.

Questions people ask