论文标题
车辆调度问题
Vehicle Scheduling Problem
论文作者
论文摘要
我们定义了一个称为车辆调度问题（VSP）的新问题。目的是最大程度地减少目标功能，例如，要维持安全距离，按照艰难的截止日期，以及在允许的最小值和最大值之间的每个连接上保持速度，拖延车辆的数量。我们证明VSP是在车间计划中常用的多个目标功能的NP硬性问题。以迟来的车辆为目标函数，我们根据混合整数线性编程（MIP）和设计启发式算法来制定VSP。我们分析了算法的复杂性，并将解决方案的质量与小型情况下MIP配方的最佳解决方案进行了比较。我们定义VSP的主要动机是将无人驾驶汽车（UAV）的整合到空域中，因此这个新颖的调度框架至关重要。
We define a new problem called the Vehicle Scheduling Problem (VSP). The goal is to minimize an objective function, such as the number of tardy vehicles over a transportation network subject to maintaining safety distances, meeting hard deadlines, and maintaining speeds on each link between the allowed minimums and maximums. We prove VSP is an NP-hard problem for multiple objective functions that are commonly used in the context of job shop scheduling. With the number of tardy vehicles as the objective function, we formulate VSP in terms of a Mixed Integer Linear Programming (MIP) and design a heuristic algorithm. We analyze the complexity of our algorithm and compare the quality of the solutions to the optimal solution for the MIP formulation in the small cases. Our main motivation for defining VSP is the upcoming integration of Unmanned Aerial Vehicles (UAVs) into the airspace for which this novel scheduling framework is of paramount importance.
