This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Hadjar, A. Articles by Soumis, F. Search for Related Content

A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem

Département de mathématiques et génie industriel, École Polytechnique de Montréal, C.P. 6079, succursale Centre-ville, Montréal, Québec, Canada H3C 3A7
Département d’informatique, Université du Québec à Montréal, C.P. 8888, succursale Centre-ville, Montréal, Québec, Canada H3C 3P8
Département de mathématiques et génie industriel, École Polytechnique de Montréal, C.P. 6079, succursale Centre-ville, Montréal, Québec, Canada H3C 3A7
ahmed.hadjar{at}gerad.ca
odile.marcotte{at}gerad.ca
francois.soumis{at}gerad.ca

We consider the multiple depot vehicle scheduling problem (MDVSP) and propose a branch-and-bound algorithm for solving it that combines column generation, variable fixing, and cutting planes. We show that the solutions of the linear relaxation of the MDVSP contain many "odd cycles." We derive a class of valid inequalities by extending the notion of odd cycle and describe a lifting procedure for these inequalities. We prove that the lifted inequalities represent, under certain conditions, facets of the underlying polytope. Finally, we present the results of a computational study comparing several strategies (variable fixing, cutting planes, mixed branching, and tree search) for solving the MDVSP.

Subject classifications: transportation; scheduling; vehicles; multiple depot vehicle scheduling problem; networks/graphs; multicommodity; multicommodity formulation; programming; integer; algorithms; cutting plane/facet; branch-and-cut algorithm for the MDVSP.
History: Received June 2001; revision received June 2004; accepted October 2004.

This article has been cited by other articles:

				A. Ceselli, G. Righini, and M. Salani A Column Generation Algorithm for a Rich Vehicle-Routing Problem Transportation Science, February 1, 2009; 43(1): 56 - 69. [Abstract] [PDF]