Managing disruptions in the multi-depot vehicle scheduling problem

Ezgi Ucar, S. Ilker Birbil, Ibrahim Muter

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

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.

LanguageEnglish
Pages249–269
Number of pages21
JournalTransportation Research Part B: Methodological
Volume105
Early online date21 Sep 2017
DOIs
StatusPublished - 30 Nov 2017

Fingerprint

scheduling
Scheduling
Recovery
Mathematical programming
Heuristic algorithms
pricing
heuristics
programming
cause
Costs
time

Cite this

Managing disruptions in the multi-depot vehicle scheduling problem. / Ucar, Ezgi; Birbil, S. Ilker; Muter, Ibrahim.

In: Transportation Research Part B: Methodological, Vol. 105, 30.11.2017, p. 249–269.

Research output: Contribution to journalArticle

@article{0cf679d3c47e4b2f83e553ac6d5daf99,
title = "Managing disruptions in the multi-depot vehicle scheduling problem",
abstract = "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.",
author = "Ezgi Ucar and Birbil, {S. Ilker} and Ibrahim Muter",
year = "2017",
month = "11",
day = "30",
doi = "10.1016/j.trb.2017.09.002",
language = "English",
volume = "105",
pages = "249–269",
journal = "Transportation Research Part B: Methodological",
issn = "0191-2615",
publisher = "Elsevier",

}

TY - JOUR

T1 - Managing disruptions in the multi-depot vehicle scheduling problem

AU - Ucar, Ezgi

AU - Birbil, S. Ilker

AU - Muter, Ibrahim

PY - 2017/11/30

Y1 - 2017/11/30

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

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

UR - https://doi.org/10.1016/j.trb.2017.09.002

U2 - 10.1016/j.trb.2017.09.002

DO - 10.1016/j.trb.2017.09.002

M3 - Article

VL - 105

SP - 249

EP - 269

JO - Transportation Research Part B: Methodological

T2 - Transportation Research Part B: Methodological

JF - Transportation Research Part B: Methodological

SN - 0191-2615

ER -