Data-driven Distributionally Robust Optimization For Vehicle Balancing of Mobility-on-Demand Systems
Data-driven Distributionally Robust Optimization For Vehicle Balancing of Mobility-on-Demand Systems
复制标题
DOI：
10.1145/3418287
复制
发表时间：
2021-01
影响因子：
2.3
通讯作者：
Fei Miao;Sihong He;Lynn Pepin;Shuo Han;Abdeltawab M. Hendawi;Mohamed E. Khalefa;J. Stankovic;G. Pappas
中科院分区：
文献类型：
--
作者：
Fei Miao;Sihong He;Lynn Pepin;Shuo Han;Abdeltawab M. Hendawi;Mohamed E. Khalefa;J. Stankovic;G. Pappas
随着向智慧城市的转型和技术的发展，传感器真实的实时收集了大量数据。出租车、按需移动自动驾驶汽车和自行车共享系统等乘车共享系统提供的服务很受欢迎。这种模式通过主动地向预测的需求分配共乘车辆，为改善交通系统的性能提供了机会。然而，如何处理预测的需求概率分布的不确定性，以提高系统的平均性能仍然是一个具有挑战性和未解决的任务。考虑到这个问题，在这项工作中，我们开发了一个数据驱动的分布式鲁棒车辆平衡方法，以最小化最坏情况下的预期成本。我们设计了有效的算法来构建不同预测方法的需求概率分布的不确定性集，并利用四叉树动态区域划分方法更好地捕捉不确定需求的动态时空特性。然后，我们推导出一个等价的计算易处理的形式数值求解分布鲁棒问题。基于纽约市四年的出租车出行数据，在不同的需求预测和区域划分方法下，对数据驱动的车辆平衡算法进行了性能评估。我们发现，平均总空转行驶距离减少了30%，与基于静态区域划分的车辆平衡方法相比，使用四叉树动态区域划分的分布式鲁棒车辆平衡方法，不考虑需求的不确定性。在纽约市，这相当于每年减少6000万英里或800万美元的成本。
With the transformation to smarter cities and the development of technologies, a large amount of data is collected from sensors in real time. Services provided by ride-sharing systems such as taxis, mobility-on-demand autonomous vehicles, and bike sharing systems are popular. This paradigm provides opportunities for improving transportation systems’ performance by allocating ride-sharing vehicles toward predicted demand proactively. However, how to deal with uncertainties in the predicted demand probability distribution for improving the average system performance is still a challenging and unsolved task. Considering this problem, in this work, we develop a data-driven distributionally robust vehicle balancing method to minimize the worst-case expected cost. We design efficient algorithms for constructing uncertainty sets of demand probability distributions for different prediction methods and leverage a quad-tree dynamic region partition method for better capturing the dynamic spatial-temporal properties of the uncertain demand. We then derive an equivalent computationally tractable form for numerically solving the distributionally robust problem. We evaluate the performance of the data-driven vehicle balancing algorithm under different demand prediction and region partition methods based on four years of taxi trip data for New York City (NYC). We show that the average total idle driving distance is reduced by 30% with the distributionally robust vehicle balancing method using quad-tree dynamic region partitions, compared with vehicle balancing methods based on static region partitions without considering demand uncertainties. This is about a 60-million-mile or a 8-million-dollar cost reduction annually in NYC.