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

@article{hadjar_2006, 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. 10.1287/opre.1050.0240}, author = {Hadjar, Ahmed and Marcotte, Odile and Soumis, Francois}, citeulike-article-id = {4135915}, citeulike-linkout-0 = {http://dx.doi.org/10.1287/opre.1050.0240}, citeulike-linkout-1 = {http://or.journal.informs.org/cgi/content/abstract/54/1/130}, day = {1}, doi = {10.1287/opre.1050.0240}, journal = {OPERATIONS RESEARCH}, keywords = {15094, mdvsp, optimization, schedule}, month = {January}, number = {1}, pages = {130--149}, posted-at = {2009-03-05 15:54:37}, priority = {3}, title = {A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem}, url = {http://dx.doi.org/10.1287/opre.1050.0240}, volume = {54}, year = {2006} }

TY - JOUR ID - hadjar_2006 L3 - citeulike-article-id:4135915 N2 - 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. 10.1287/opre.1050.0240 IS - 1 JF - OPERATIONS RESEARCH EP - 149 TI - A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem VL - 54 SP - 130 KW - 15094 KW - mdvsp KW - optimization KW - schedule AU - Hadjar, Ahmed AU - Marcotte, Odile AU - Soumis, Francois PY - 2006/01/01/ UR - http://dx.doi.org/10.1287/opre.1050.0240 ER -