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. It is also established that the additive bound technique cannot provide tighter bounds than those obtained by Lagrangean decomposition, in the framework in which it has been used so far. Computational results illustrating the robustness of the combined set partitioning - column generation approach are reported for problems four to five times larger than the largest problems exactly solved in the literature so far. 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.