A multi-period dial-a-ride problem with driver consistency
A multi-period dial-a-ride problem with driver consistency
复制标题
DOI：
10.1016/j.trb.2016.09.010
复制
发表时间：
2016-12-01
影响因子：
6.8
通讯作者：
Kovacs, Attila A.
中科院分区：
文献类型：
--
作者：
Braekers, Kris;Kovacs, Attila A.
叫车服务为残疾人和老年人提供个性化的交通方式，以保持他们的机动性。通常，在一辆车上同时运送具有不同上落位置的几个用户。拨号叫车问题(DARP)的焦点主要是最小化路由成本。通过设置时间窗口和限制每个用户的最大乘车时间，在模型中考虑了服务质量。我们通过称为驱动程序一致性的服务质量的附加功能来扩展传统的DARP。叫车服务的客户通常对日常生活的变化很敏感。这方面包括提供运输服务的人，即车辆的司机。我们的问题被称为司机一致拨打顺风车问题(DC-DARP)，它通过限制在多周期规划范围内运送用户的不同司机的最大数量来考虑司机一致性。我们提出了问题的不同公式，并检验了它们在分枝切割方式应用时的效率。此外，我们还开发了一个大型邻域搜索算法，可以在很短的时间内生成接近最优解。生成的实例超过1000个，紧密参考真实世界的场景。进行了广泛的计算实验，以评估解决方法的质量并提供对新问题的见解。结果表明，提供司机一致性的成本在很大程度上存在差异。根据实例的不同，为每个用户分配一个驱动程序的成本可能比低成本解决方案高出27.98%。然而，如果用户由至少两个司机运送，则路由成本增加不超过5.80%。(C)2016爱思唯尔有限公司。保留所有权利。
Dial-a-ride services provide disabled and elderly people with a personalized mode of transportation to preserve their mobility. Typically, several users with different pickup and dropoff locations are transported on a vehicle simultaneously. The focus in dial-a-ride problems (DARPs) is mainly on minimizing routing cost. Service quality has been taken into account in the models by imposing time windows and limiting the maximum ride time of each user. We extend the classical DARP by an additional feature of service quality referred to as driver consistency. Customers of dial-a-ride services are often sensitive to changes in their daily routine. This aspect includes the person who is providing the transportation service, i.e., the driver of the vehicle. Our problem, called the driver consistent dial-a-ride problem (DC-DARP), considers driver consistency by bounding the maximum number of different drivers that transport a user over a multi-period planning horizon. We propose different formulations of the problem and examine their efficiency when applied in a Branch-and-Cut fashion. Additionally, we develop a large neighborhood search algorithm that generates near-optimal solutions in a short amount of time. Over 1000 instances are generated with close reference to real world scenarios. Extensive computational experiments are conducted in order to assess the quality of the solution approaches and to provide insights into the new problem. Results reveal that the cost of offering driver consistency varies greatly in magnitude. Depending on the instance, the cost of assigning one driver to each user can be up to 27.98% higher compared to a low-cost solution. However, routing cost increases by not more than 5.80% if users are transported by at least two drivers. (C) 2016 Elsevier Ltd. All rights reserved.