We consider two types of disruptions arising in the multi-depot vehicle scheduling; the delays and the extra trips. These disruptions may or may not occur during operations, and hence they need to be indirectly incorporated into the planned schedule by anticipating their likely occurence times. We present a unique recovery method to handle these potential disruptions. Our method is based on partially swapping two planned routes in such a way that the effect on the planned schedule is minimal, if these disruptions are actually realized. The mathematical programming model for the multi-depot vehicle scheduling problem, which incorporates these robustness considerations, possesses a special structure. This special structure causes the conventional column generation method fall short as the resulting problem grows also row-wise when columns are generated. We design an exact simultaneous column-and-row generation algorithm to find a valid lower-bound. The novel aspect of this algorithm is the pricing subproblem, which generates pairs of routes that form recovery solutions. Compromising on exactness, we modify this algorithm in order to enable it to solve practical-sized instances efficiently. This heuristic algorithm is shown to provide very tight bounds on the randomly generated instances in a short computation time.