Models and Algorithms for Vehicle Scheduling

This paper considers the polynom ial solvable case in which there is a single depot and one type of vehicle. Several network representations f or vehicle scheduling are discussed, including important reductions in the size of these networks. Furthermore, a new quasi-assignment algorithm is prov ided. This algorithm is based on an auction algorithm f or the linear assignment problem . An important contribution of this paper is a computational study that compares our algorithms w ith the most successful algorithms f or the vehicle scheduling problem , using both random ly generated and real life data. This can serve as a guide f or both scientists and practioners. The new quasi-assignment algorithm is shown to be considerably f aster f or the test problems corresponding to sparse networks, and competitive f or test problems corresponding to dense networks. A f ast algorithm is f or example very important when this particular vehicle scheduling problem appears as a subproblem in more complex vehicle and crew scheduling problems