AI Driver-Rider Matching System

Batched dispatch with learned ETAs

Design the dispatch system of a ride-hailing app: track drivers in real time, predict pickup times, match riders and drivers in small batches instead of one at a time, and move idle drivers toward coming demand.

Overview

When a rider taps 'request', the app must pick a driver. The obvious rule, nearest free driver, right now, is fast and simple, and it is often wrong for the system as a whole: two riders a block apart may both be best served by the same driver, and whoever asked first takes that driver, leaving the other with a long wait.

A better dispatcher collects the requests that arrive in a short window (here 2 seconds), looks at all the nearby free drivers, and solves an assignment problem: which pairs give the lowest total pickup time. That only works if the pickup times are right, and straight-line distance is a poor guide in a city (rivers, one-way streets, traffic), so the system predicts ETAs from a routing engine corrected by a learned model.

Around this core sit three supporting pieces: a stream of driver locations and a spatial index to find nearby drivers fast; an offer step that makes sure a driver is never given to two riders; and a forecast of demand by area, used to nudge idle drivers to where riders will be.

Questions to ask first

How big? — 20 million trips a day, peak 3 times the average; 1 million drivers online at peak
How often do drivers report location? — Every 4 seconds while online
How fast must a rider hear back? — A driver offer within a few seconds (our target: 5 s at p95)
What does matching optimize? — Total predicted pickup time, with limits so nobody waits far longer than greedy would give them
Vehicle types? — Yes: standard, XL, accessible; a request only matches compatible vehicles
Can a driver decline? — Yes; the offer times out and the rider goes back into the next batch

What you will be able to do

Index moving drivers with H3 cells and find candidates for a pickup in milliseconds.
Explain how learned ETAs improve on distance, and where the model sits.
Show with a small example why batched assignment beats greedy, and choose the batch window.
Offer a driver to exactly one rider, even with concurrent matchers and timeouts.
Partition the problem by region, forecast demand, and fall back safely.

Key concepts

Geospatial index (H3)
Location ingestion
Learned ETA
Candidate generation
Bipartite assignment
Batch window
Atomic offers
Demand forecasting
Repositioning
Regional partitioning

Functional requirements

Ingest driver locations and status (available, offered, on trip, offline) in real time
Accept ride requests with pickup, drop-off and vehicle type, and show a live estimated wait
Every batch window, assign pending requests to compatible free drivers to minimize total predicted pickup time
Offer the trip to the chosen driver; on accept, lock the pair; on decline or timeout, return the rider to the next batch
Forecast demand per area and suggest where idle drivers should go
Fall back to nearest-driver matching when the solver or ETA service is unavailable

Non-functional requirements

Rider gets a driver offer within 5 s at p95 in normal supply (a target we chose)
A driver is never offered to two riders at once
Location updates are visible to the matcher within about one ping interval (4 s)
Regions are independent: an overloaded or failed city does not affect others
Every assignment is logged with predicted ETA and, later, the actual pickup time, to train and evaluate the ETA model

Interview questions

Why not just dispatch the nearest driver?
How do you find nearby drivers quickly?
How do you predict pickup ETAs?
How do you solve the assignment, and how big does it get?
How do you make sure a driver is not assigned twice?
How long should the batch window be?
How do you use demand forecasts?