Models and Algorithms for Single-Depot Vehicle Scheduling
Models and Algorithms for Single-Depot Vehicle Scheduling
复制标题
DOI：
10.1287/trsc.35.2.165.10135
复制
发表时间：
2001-05
期刊：
影响因子：
--
通讯作者：
R. Freling;A. Wagelmans;J. Paixão
中科院分区：
文献类型：
--
作者：
R. Freling;A. Wagelmans;J. Paixão
车辆调度是将车辆分配给一组具有固定开始和结束时间的预定行程，同时最大限度地降低资本和运营成本的过程。本文考虑了多项式可解情况的建模、算法和计算方面，其中存在单个停车场且车辆相同。审查了准分配公式并给出了替代的不对称分配公式。本文的主要贡献是一种在特殊成本结构情况下有效的新的两阶段方法、一种用于准分配问题的拍卖算法、一种面向核心的方法以及广泛的计算研究。使用随机生成的数据和现实生活中的数据，将新算法与解决车辆调度问题的最成功算法进行比较。新算法在计算时间方面显示出显着的性能改进。例如，当这个特定的车辆调度问题作为更复杂的车辆和机组人员调度问题中的子问题出现时，这种改进可能非常重要。
Vehicle scheduling is the process of assigning vehicles to a set of predetermined trips with fixed starting and ending times, while minimizing capital and operating costs. This paper considers modeling, algorithmic, and computational aspects of the polynomially solvable case in which there is a single depot and vehicles are identical. A quasiassignment formulation is reviewed and an alternative asymmetric assignment formulation is given. The main contributions of the paper are a new two-phase approach which is valid in the case of a special cost structure, an auction algorithm for the quasiassignment problem, a core-oriented approach, and an extensive computational study. New algorithms are compared with the most successful algorithms for the vehicle-scheduling problem, using both randomly generated and real-life data. The new algorithms show a significant performance improvement with respect to computation time. Such improvement can, for example, be very important when this particular vehicle-scheduling problem appears as a subproblem in more complex vehicle- and crew-scheduling problems.