Managing disruptions in the multi-depot vehicle scheduling problem

Ezgi Ucar, S. Ilker Birbil, Ibrahim Muter

Research output: Contribution to journalArticlepeer-review

21 Citations (SciVal)
233 Downloads (Pure)


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 occurrence 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.

Original languageEnglish
Pages (from-to)249–269
Number of pages21
JournalTransportation Research Part B: Methodological
Early online date21 Sept 2017
Publication statusPublished - 1 Nov 2017


  • Multi-depot vehicle scheduling
  • Robust planning
  • Column-and-row generation


Dive into the research topics of 'Managing disruptions in the multi-depot vehicle scheduling problem'. Together they form a unique fingerprint.

Cite this