An Integrated Decomposition and Approximate Dynamic Programming Approach for On-Demand Ride Pooling
An Integrated Decomposition and Approximate Dynamic Programming Approach for On-Demand Ride Pooling
复制标题
DOI：
10.1109/tits.2019.2934423
复制
发表时间：
2020-09
影响因子：
8.5
通讯作者：
Xian Yu;Siqian Shen
中科院分区：
文献类型：
--
作者：
Xian Yu;Siqian Shen
通过智能手机应用程序，司机和乘客可以动态地进入和离开乘车平台。因此，由于复杂的系统动态和多个利益相关者的不同目标，拼车具有挑战性。在本文中，我们研究了不超过两个乘客群体谁可以共享乘坐在同一辆车的拼车。我们动态地将可用的司机与随机到达的乘客进行匹配，并决定接送路线。目标是最小化乘客等待时间和行程延误时间的加权和。一个空间和时间的分解启发式应用和每个子问题的解决使用近似动态规划（ADP），我们在每个阶段的近似值函数的属性。我们的模型是以优化车辆调度而无需拼车的模型和匹配当前司机和乘客而无需需求预测的模型为基准的。使用基于纽约市出租车数据在一个高峰小时内生成的测试实例，我们进行计算研究和敏感性分析，以显示（i）ADP的经验收敛，（ii）乘坐联营的好处，以及（iii）未来供需信息的价值。
Through smartphone apps, drivers and passengers can dynamically enter and leave ride-hailing platforms. As a result, ride-pooling is challenging due to complex system dynamics and different objectives of multiple stakeholders. In this paper, we study ride-pooling with no more than two passenger groups who can share rides in the same vehicle. We dynamically match available drivers to randomly arriving passengers and also decide pick-up and drop-off routes. The goal is to minimize a weighted sum of passengers’ waiting time and trip delay time. A spatial-and-temporal decomposition heuristic is applied and each subproblem is solved using Approximate Dynamic Programming (ADP), for which we show properties of the approximated value function at each stage. Our model is benchmarked with the one that optimizes vehicle dispatch without ride-pooling and the one that matches current drivers and passengers without demand forecasting. Using test instances generated based on the New York City taxi data during one peak hour, we conduct computational studies and sensitivity analysis to show (i) empirical convergence of ADP, (ii) benefit of ride-pooling, and (iii) value of future supply-demand information.