A Column Generation Approach to the Multiple-Depot Vehicle Scheduling Problem Export

@article{ribeiro_1994, abstract = {We give a new formulation to the multiple-depot vehicle scheduling problem as a set partitioning problem with side constraints, whose continuous relaxation is amenable to be solved by column generation. We show that the continuous relaxation of the set partitioning formulation provides a much tighter lower bound than the additive bound procedure previously applied to this problem. We also establish that the additive bound technique cannot provide tighter bounds than those obtained by Lagrangian decomposition, in the framework in which it has been used so far. Computational results that illustrate the robustness of the combined set partitioning-column generation approach are reported for problems four to five times larger than the largest problems that have been exactly solved in the literature. Finally, we show that the gap associated with the additive bound based on the assignment and shortest path relaxations can be arbitrarily bad in the general case, and as bad as 50\% in the symmetric case.}, author = {Ribeiro, Celso C. and Soumis, Francois}, citeulike-article-id = {6037511}, issn = {0030364X}, journal = {Operations Research}, keywords = {15094, mdvsp, optimization, scheduling, transit}, number = {1}, pages = {41--52}, posted-at = {2009-10-29 21:56:46}, priority = {2}, publisher = {INFORMS}, title = {A Column Generation Approach to the Multiple-Depot Vehicle Scheduling Problem}, volume = {42}, year = {1994} }

TY - JOUR ID - ribeiro_1994 L3 - citeulike-article-id:6037511 N2 - We give a new formulation to the multiple-depot vehicle scheduling problem as a set partitioning problem with side constraints, whose continuous relaxation is amenable to be solved by column generation. We show that the continuous relaxation of the set partitioning formulation provides a much tighter lower bound than the additive bound procedure previously applied to this problem. We also establish that the additive bound technique cannot provide tighter bounds than those obtained by Lagrangian decomposition, in the framework in which it has been used so far. Computational results that illustrate the robustness of the combined set partitioning-column generation approach are reported for problems four to five times larger than the largest problems that have been exactly solved in the literature. Finally, we show that the gap associated with the additive bound based on the assignment and shortest path relaxations can be arbitrarily bad in the general case, and as bad as 50% in the symmetric case. IS - 1 JF - Operations Research SN - 0030364X EP - 52 TI - A Column Generation Approach to the Multiple-Depot Vehicle Scheduling Problem PB - INFORMS VL - 42 SP - 41 KW - 15094 KW - mdvsp KW - optimization KW - scheduling KW - transit AU - Ribeiro, Celso AU - Soumis, Francois PY - 1994/// ER -