Separating Valid Odd-Cycle and Odd-Set Inequalities for the Multiple Depot Vehicle Scheduling Problem

, , et

référence BibTeX

We consider the multicommodity network flow formulation of the Multiple Depot Vehicle Scheduling Problem (MDVSP) and investigate several strategies within a branch-and-cut framework for solving the MDVSP. In particular we compare subalgorithms for separating the cutting planes introduced by Hadjar, Marcotte, and Soumis in "A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem" (Operations Research 54, pp. 130-149, 2006). We also evaluate the effectiveness of a new criterion for fixing some variables in the multicommodity flow formulation. Finally we present computational experiments to illustrate the strengths and weaknesses of the strategies.

, 27 pages

Ce cahier a été révisé en avril 2013

Axe de recherche

Applications de recherche


Separating valid odd-cycle and odd-set inequalities for the multiple depot vehicle scheduling problem
, , et
EURO Journal on Computational Optimization, 1(3-4), 283–312, 2013 référence BibTeX