论文标题
多车拨号问题的分层分组算法
A Hierarchical Grouping Algorithm for the Multi-Vehicle Dial-a-Ride Problem
论文作者
论文摘要
共享是现代城市流动性的重要方面。在本文中，我们考虑了乘车共享的经典问题 - 多车拨号问题（多车辆DARP）。鉴于有固定容量驻扎在各个位置的车队，以及由起源和目的地指定的一组乘车请求，其目标是服务于所有要求，以便在旅途中任何时候，任何车辆的乘客都超过其容量。我们提出了一种算法HRA，该算法是第一个用于多车辆DARP的非平底近似算法。主要的技术贡献是将多车辆DARP减少到某个电容分区问题，我们使用新型的层次分组算法来解决该问题。实验结果表明，与最先进的基线相比，我们算法生产的车辆路线不仅显示出较小的总行进距离，而且还享有较小的过渡潜伏期，这与骑手的旅行时间至关重要。这表明HRA在节能的同时增强了骑手的体验。
Ride-sharing is an essential aspect of modern urban mobility. In this paper, we consider a classical problem in ride-sharing - the Multi-Vehicle Dial-a-Ride Problem (Multi-Vehicle DaRP). Given a fleet of vehicles with a fixed capacity stationed at various locations and a set of ride requests specified by origins and destinations, the goal is to serve all requests such that no vehicle is assigned more passengers than its capacity at any point along its trip. We propose an algorithm HRA, which is the first non-trivial approximation algorithm for the Multi-Vehicle DaRP. The main technical contribution is to reduce the Multi-Vehicle DaRP to a certain capacitated partitioning problem, which we solve using a novel hierarchical grouping algorithm. Experimental results show that the vehicle routes produced by our algorithm not only exhibit less total travel distance compared to state-of-the-art baselines, but also enjoy a small in-transit latency, which crucially relates to riders' traveling times. This suggests that HRA enhances rider experience while being energy-efficient.
