Models and Algorithms for Single-Depot Vehicle Scheduling

Richard Freling, Albert P. M. Wagelmans and José M. Pinto Paixão
Additional contact information
Richard Freling: Econometric Institute, Erasmus University, Rotterdam, The Netherlands
Albert P. M. Wagelmans: DEIO, Universidade de Lisboa, Lisbon, Portugal
José M. Pinto Paixão: DEIO, Universidade de Lisboa, Lisbon, Portugal

Transportation Science, 2001, vol. 35, issue 2, 165-180

Abstract: 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.

Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.35.2.165.10135 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:35:y:2001:i:2:p:165-180

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().