A Column Generation Approach to the Multiple-Depot Vehicle Scheduling Problem

Celso C. Ribeiro and François Soumis
Additional contact information
Celso C. Ribeiro: Catholic University of Rio de Janeiro, Rio de Janeiro, Brazil
François Soumis: GERAD and École Polytechnique de Montréal, Montréal, Quebec, Canada

Operations Research, 1994, vol. 42, issue 1, 41-52

Abstract: We give a new formulation to the multiple-depot vehicle scheduling problem as a set partitioning problem with side constraints, whose continuous relaxation is amenable to be solved by column generation. We show that the continuous relaxation of the set partitioning formulation provides a much tighter lower bound than the additive bound procedure previously applied to this problem. We also establish that the additive bound technique cannot provide tighter bounds than those obtained by Lagrangian decomposition, in the framework in which it has been used so far. Computational results that illustrate the robustness of the combined set partitioning-column generation approach are reported for problems four to five times larger than the largest problems that have been exactly solved in the literature. Finally, we show that the gap associated with the additive bound based on the assignment and shortest path relaxations can be arbitrarily bad in the general case, and as bad as 50% in the symmetric case.

Keywords: transportation; mass transit: multiple-depot vehicle scheduling; transportation; scheduling; vehicles: urban bus (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (49)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.1.41 (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:oropre:v:42:y:1994:i:1:p:41-52

Access Statistics for this article

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