Solving Dispatch in a Ridesharing Problem Space

Oussama Hanguir31 Jul 2025

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 t=0 two drivers are free for one request and the white car is sent. At t=1 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
Continue reading — it's free

Google or a one-time email code. No password.