Problem
A ride-hailing platform must pair riders with drivers continuously: millions of possible decisions open every second, and driver positions, demand and traffic keep changing. A poor pairing means longer pickups for riders and wasted time and earnings for drivers. Two choices are hard: how long to wait before matching a group of requests, and how not to spend a driver on a pair that is best now but wrong for the next request.
Example from the article: at time two drivers are free for one request and the white car is sent. At a new request appears, only the black car is left, and that rider waits longer.
Solution in brief
Model each batch of riders and drivers as a bipartite graph with edge weights equal to the benefit of each pair, and pick the edges with the maximum total weight. On this graph the linear-programming relaxation already returns whole-number answers, so fast solvers work. To reduce short-sightedness, add forecasted demand or long-term objectives to the weights, and rebalance drivers with incentives.
Questions this case answers
- How to assign units on one side of a two-sided market to units on the other side every few seconds so that total benefit is maximal while each unit is used at most once
- How to keep repeated short-horizon assignment from hurting long-horizon efficiency when future demand and supply are uncertain
- How to match riders and drivers in batches so that the total benefit of all matches is maximal?
- How to choose the batching interval between faster pickups and better matches?
Tools and methods
- Bipartite matching graph — riders and drivers as two sides, edge weight = benefit of the pair
- Integer linear program and LP relaxation — choose the best set of pairs; the relaxation solves faster
- Hungarian algorithm / commercial solvers — solve the matching
- Batching window — groups nearby riders and drivers per solve
- Demand forecasting and dynamic rebalancing — reduce short-sighted matches
Google or a one-time email code. No password.