In this paper, we study the problem of planning a timetable for passenger trains considering that possible delays might occur due to unpredictable (but bounded) circumstances. Once arrival and departure events are scheduled, if the timetable cannot be respected since an external event has determined a delay to a train, the so called delay management problem occurs. Delays might be managed in several ways and the usual objective function considered for such purpose is the minimization of the overall waiting time caused to passengers. We analyze the interaction between timetable planning and delay management in terms of the recoverable robustness model, where a timetable is said to be robust if it is able to absorb small delays by possibly applying given recovery capabilities. The quality of a robust timetable is measured by the price of robustness that is the ratio between the cost of the robust timetable and that of a non-robust optimal timetable. We consider the problem of designing robust timetables subject to bounded delays. We show that finding an optimal solution for this problem is NP-hard. Hence, we propose robust algorithms and evaluate their prices of robustness. Moreover, we show that such algorithms are optimal with respect to particular assumptions.

Delay Management Problem: Complexity Results and Robust Algorithms

NAVARRA, Alfredo
2008

Abstract

In this paper, we study the problem of planning a timetable for passenger trains considering that possible delays might occur due to unpredictable (but bounded) circumstances. Once arrival and departure events are scheduled, if the timetable cannot be respected since an external event has determined a delay to a train, the so called delay management problem occurs. Delays might be managed in several ways and the usual objective function considered for such purpose is the minimization of the overall waiting time caused to passengers. We analyze the interaction between timetable planning and delay management in terms of the recoverable robustness model, where a timetable is said to be robust if it is able to absorb small delays by possibly applying given recovery capabilities. The quality of a robust timetable is measured by the price of robustness that is the ratio between the cost of the robust timetable and that of a non-robust optimal timetable. We consider the problem of designing robust timetables subject to bounded delays. We show that finding an optimal solution for this problem is NP-hard. Hence, we propose robust algorithms and evaluate their prices of robustness. Moreover, we show that such algorithms are optimal with respect to particular assumptions.
2008
9783540850960
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/159771
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 11
social impact