Models and Algorithms for Vehicle Scheduling

Richard Freling, José Pinto Paixão and Albert Wagelmans

No EI 9562-/A, Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute

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

Keywords: vehicle; scheduling (search for similar items in EconPapers)
Date: 1995-01-01
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:ems:eureir:1368

Access Statistics for this paper

More papers in Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute Contact information at EDIRC.
Bibliographic data for series maintained by RePub ( this e-mail address is bad, please contact ).