Matching Drivers to Riders: A Two-Stage Robust Approach

DOI10.4230/LIPICS.APPROX/RANDOM.2021.12MaRDI QIDQ6090882zbMATH OpenOpenAlexFDO

Authors Omar El Housni, Vineet Goyal, Oussama Hanguir, Clifford Stein

Publication date 20 November 2023

Full work available at URL https://arxiv.org/abs/2011.03624

zbMATH Keywords

matchingapproximation algorithmsrobust optimization

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Abstract: Matching demand (riders) to supply (drivers) efficiently is a fundamental problem for ride-sharing platforms who need to match the riders (almost) as soon as the request arrives with only partial knowledge about future ride requests. A myopic approach that computes an optimal matching for current requests ignoring future uncertainty can be highly sub-optimal. In this paper, we consider a two-stage robust optimization framework for this matching problem where future demand uncertainty is modeled using a set of demand scenarios (specified explicitly or implicitly). The goal is to match the current request to drivers (in the first stage) so that the cost of first stage matching and the worst case cost over all scenarios for the second stage matching is minimized. We show that the two-stage robust matching is NP-hard under various cost functions and present constant approximation algorithms for different settings of our two-stage problem. Furthermore, we test our algorithms on real-life taxi data from the city of Shenzhen and show that they substantially improve upon myopic solutions and reduce the maximum wait time of the second-stage riders by an average of $30\mathrm{\%}$ in our experimental results.

Cited in

(3)

• The value of shared information for allocation of drivers in ride-hailing: a proof-of-concept study
• LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization
• LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization

This page was built for publication: Matching Drivers to Riders: A Two-Stage Robust Approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6090882)