In this paper, we study the problem of planning a timetable for passenger trains considering that possible delays might occur due to unpredictable circumstances. If a delay occurs, a timetable could not be able to manage it unless some extra time has been scheduled in advance. 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 timetable planning problem in terms of the recoverable robustness model, where a timetable is said to be recoverable robust if it is able to absorb small delays by possibly applying given limited recovery capabilities. The quality of a robust timetable is measured by the price of robustness that is the ratio between the cost of the recoverable robust timetable and that of a non-robust optimal one. We consider the problem of designing recoverable robust timetables subject to bounded delays. We show that finding an optimal solution for this problem is NP-hard. Then, we propose robust algorithms, evaluate their prices of robustness, and show that such algorithms are optimal in some important cases.

Recoverable robust timetabling for single delay: Complexity and polynomial algorithms for special cases

CICERONE, SERAFINO;DI STEFANO, GABRIELE;FRIGIONI, DANIELE;
2009-01-01

Abstract

In this paper, we study the problem of planning a timetable for passenger trains considering that possible delays might occur due to unpredictable circumstances. If a delay occurs, a timetable could not be able to manage it unless some extra time has been scheduled in advance. 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 timetable planning problem in terms of the recoverable robustness model, where a timetable is said to be recoverable robust if it is able to absorb small delays by possibly applying given limited recovery capabilities. The quality of a robust timetable is measured by the price of robustness that is the ratio between the cost of the recoverable robust timetable and that of a non-robust optimal one. We consider the problem of designing recoverable robust timetables subject to bounded delays. We show that finding an optimal solution for this problem is NP-hard. Then, we propose robust algorithms, evaluate their prices of robustness, and show that such algorithms are optimal in some important cases.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

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/11697/4936
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 34
  • ???jsp.display-item.citation.isi??? 28
social impact