TITLE

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

AUTHOR(S)
Hadjar, Ahmed; Marcotte, Odile; Soumis, Fran├žois
PUB. DATE
January 2006
SOURCE
Operations Research;Jan/Feb2006, Vol. 54 Issue 1, p130
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
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.
ACCESSION #
19949374

 

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics