We consider the multiple depot vehicle scheduling problem (MDVSP) and propose a branch-and-bound algorithm for solving it that combines column generation, variable ﬁxing 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 ﬁxing, cutting planes, mixed branching and tree search) for solving the MDVSP.
Published July 2001 , 47 pages
This cahier was revised in June 2004