Matching Drivers to Riders: A Two-Stage Robust Approach

DOI10.4230/LIPICS.APPROX/RANDOM.2021.12arXiv2011.03624OpenAlexW3202674443MaRDI QIDQ6090882FDOQ6090882

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

Publication date: 20 November 2023

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.

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)

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)