A branch-and-cut algorithm for the multiple depot vehicle scheduling problem
成果类型：
Article
署名作者：
Hadjar, A; Marcotte, O; Soumis, F
署名单位：
Universite de Montreal; Polytechnique Montreal; University of Quebec; University of Quebec Montreal
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1050.0240
发表日期：
2006
页码：
130-149
关键词：
摘要：
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.