Models and Algorithms for Vehicle Scheduling

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 the polynomially solvable case in which there is a single depot and one type of vehicle. Several assignment types of formulations are discussed and a new quasi-assignment algorithm is provided. This algorithm is based on an auction algorithm for the linear assignment problem. Furthermore, several ways for dealing with a large number of feasible connections between trips, a bottleneck for vehicle scheduling, are discussed. An important contribution of this paper is a computational study that compares our algorithms with the most successful algorithms for the vehicle scheduling problem, using both randomly generated and real life data. This can serve as a guide for both scientists and practioners. The new quasi-assignment algorithm is shown to be considerably faster for most of the test problems. This improvement in computation time is also very important when this particular vehicle scheduling problem appears as a subproblem in more complex vehicle and crew scheduling problems.