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

Serafino Cicerone (), Gianlorenzo D’Angelo (), Gabriele Stefano (), Daniele Frigioni () and Alfredo Navarra ()
Additional contact information
Serafino Cicerone: University of L’Aquila
Gianlorenzo D’Angelo: University of L’Aquila
Gabriele Stefano: University of L’Aquila
Daniele Frigioni: University of L’Aquila
Alfredo Navarra: University of Perugia

Journal of Combinatorial Optimization, 2009, vol. 18, issue 3, No 2, 229-257

Abstract: 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.

Keywords: Timetable optimization; Robust optimization; Recoverable robustness (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-009-9247-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:18:y:2009:i:3:d:10.1007_s10878-009-9247-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-009-9247-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().