EconPapers    
Economics at your fingertips  
 

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

Ahmed Hadjar (), Odile Marcotte () and François Soumis ()
Additional contact information
Ahmed Hadjar: 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
Odile Marcotte: Département d’informatique, Université du Québec à Montréal, C.P. 8888, succursale Centre-ville, Montréal, Québec, Canada H3C 3P8
François Soumis: 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

Operations Research, 2006, vol. 54, issue 1, 130-149

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.

Keywords: 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 (search for similar items in EconPapers)
Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (27)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1050.0240 (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:54:y:2006:i:1:p:130-149

Access Statistics for this article

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

 
Page updated 2025-03-19
Handle: RePEc:inm:oropre:v:54:y:2006:i:1:p:130-149