A COLUMN GENERATION APPROACH TO THE MULTIPLE-DEPOT VEHICLE SCHEDULINGPROBLEM

We give a new formulation to the multiple-depot vehicle scheduling pro blem as a set partitioning problem with side constraints, whose contin uous relaxation is amenable to be solved by column generation. We show that the continuous relaxation of the set partitioning formulation pr ovides a much tighter lower bound than the additive bound procedure pr eviously applied to this problem. We also establish that the additive bound technique cannot provide tighter bounds than those obtained by L agrangian decomposition, in the framework in which it has been used so far. Computational results that illustrate the robustness of the comb ined set partitioning-column generation approach are reported for prob lems four to five times larger than the largest problems that have bee n exactly solved in the literature. Finally, we show that the gap asso ciated with the additive bound based on the assignment and shortest pa th relaxations can be arbitrarily bad in the general case, and as bad as 50% in the symmetric case.