Matching Drivers to Riders: A Two-Stage Robust Approach

• 成果类型: Article
• 署名作者: El Housni, Omar; Goyal, Vineet; Hanguir, Oussama; Stein, Clifford
• 署名单位: Cornell University; Columbia University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2021.0668
• 发表日期: 2026
• 关键词: approximation algorithms; online; optimization

摘要

Matching demand (riders) to supply (drivers) efficiently is a fundamental problem for ride-sharing platforms that 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 suboptimal. In this paper, we consider a two-stage robust optimization framework for this matching problem in which 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.