Models and algorithms for single-depot vehicle scheduling

Vehicle scheduling is the process of assigning vehicles to a set of predete rmined trips with fixed starting and ending times, while minimizing capital and operating costs. This paper considers modeling, algorithmic, and compu tational aspects of the polynomially solvable case in which there is a sing le depot and vehicles are identical. A quasiassignment formulation is revie wed 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 quasiass ignment problem, a core-oriented approach, and an extensive computational s tudy. New algorithms are compared with the most successful algorithms for t he vehicle-scheduling problem, using both randomly generated and real-life data. The new algorithms show a significant performance improvement with re spect to computation time. Such improvement can, for example, be very impor tant when this particular vehicle-scheduling problem appears as a subproble m in more complex vehicle- and crew-scheduling problems.