Matching Drivers to Riders: A Two-Stage Robust Approach
Matching Drivers to Riders: A Two-Stage Robust Approach
复制标题
DOI：
10.4230/lipics.approx/random.2021.12
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Omar El Housni;Vineet Goyal;Oussama Hanguir;C. Stein
中科院分区：
文献类型：
--
作者：
Omar El Housni;Vineet Goyal;Oussama Hanguir;C. Stein
高效地匹配需求（乘客）与供应（司机）是乘车共享平台的一个基本问题，这些平台需要在请求到达时（几乎）立即匹配乘客，而对未来的乘车请求只有部分了解。一个短视的方法，计算当前请求的最佳匹配，忽略未来的不确定性可能是非常次优的。在本文中，我们考虑了一个两阶段的强大的优化框架，这个匹配问题，未来的需求不确定性建模使用一组的需求场景（明确或隐含地指定）。目标是将当前请求匹配到驱动程序（在第一阶段中），使得第一阶段匹配的成本和第二阶段匹配的所有场景中的最坏情况成本最小化。我们表明，两阶段的鲁棒匹配是NP-困难的各种成本函数和目前的常数近似算法，我们的两个阶段的问题的不同设置。此外，我们测试了我们的算法在现实生活中的出租车数据从深圳市，并表明，他们大大提高近视的解决方案，并减少了第二阶段的乘客的最大等待时间平均为30\%$在我们的实验结果。
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\%$ in our experimental results.