论文标题
乘坐时间的安排算法，以解决拨号问题
A ride time-oriented scheduling algorithm for dial-a-ride problems
论文作者
论文摘要
本文提供了一种新算法，以有效地优化拨号问题的调度决策（DARP），包括考虑电动和自动驾驶汽车（E-ADARP）的问题变体。基于线性编程理论的调度启发式旨在在多项式时间内找到最小的用户乘车时间时间表。该算法可以返回最佳的可行路线，也可以返回错误的可靠性声明，可以通过专门设计的启发式词来恢复可行性。此外，该算法还补充了电池管理算法，该算法可用于确定电动和自动驾驶汽车舰队的充电决定。从DARP和E-ADARP基准实例提取的数百万个路线获得了提议的调度算法的定时解决方案。将它们与从线性程序获得的那些以及来自DARP文献的流行计划程序进行了比较。结果表明，在计算效率和解决方案质量方面，所提出的程序的表现优于最先进的调度算法。
This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theory, aims at finding minimal user ride time schedules in polynomial time. The algorithm can either return optimal feasible routes or it can return incorrect infeasibility declarations, on which feasibility can be recovered through a specifically-designed heuristic. The algorithm is furthermore supplemented by a battery management algorithm that can be used to determine charging decisions for electric and autonomous vehicle fleets. Timing solutions from the proposed scheduling algorithm are obtained on millions of routes extracted from DARP and e-ADARP benchmark instances. They are compared to those obtained from a linear program, as well as to popular scheduling procedures from the DARP literature. Results show that the proposed procedure outperforms state-of-the-art scheduling algorithms, both in terms of compute-efficiency and solution quality.
