Abstract
In the context of scheduling and timetabling, we study a challenging combinatorial problem which is very interesting for both practical and theoretical points of view. The motivation behind it is to cope with scheduled activities which might be subject to unavoidable disruptions, such as delays, occurring during the operational phase. The idea is to preventively plan some extra time for the scheduled activities in order to be “prepared” if a delay occurs, and absorb it without the necessity of re-scheduling all the activities from scratch. This realizes the concept of designing robust timetables. During the planning phase, one should also consider recovery features that might be applied at runtime if disruptions occur. This leads to the concept of recoverable robust timetables. In this new concept, it is assumed that recovery capabilities are given as input along with the possible disruptions that must be considered. The main objective is the minimization of the overall needed time. We show that finding an optimal solution for this problem is NP-hard even though the topology of the network, which models dependencies among activities, is restricted to trees. However, we manage to design a pseudo-polynomial time algorithm based on dynamic programming.
This work was partially supported by the Future and Emerging Technologies Unit of EC (IST priority - 6th FP), under contract no. FP6-021235-2 (project ARRIVAL).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cicerone, S., D’Angelo, G., Di Stefano, G., Frigioni, D., Navarra, A.: Robust Algorithms and Price of Robustness in Shunting Problems. In: Proc. of 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, ATMOS, pp. 175–190 (2007)
Cicerone, S., D’Angelo, G., Di Stefano, G., Frigioni, D., Navarra, A.: Delay Management Problem: Complexity Results and Robust Algorithms. In: Yang, B., Du, D.-Z., Wang, C.A. (eds.) COCOA 2008. LNCS, vol. 5165, pp. 458–468. Springer, Heidelberg (2008)
Cicerone, S., D’Angelo, G., Di Stefano, G., Frigioni, D., Navarra, A.: Recoverable Robust Timetabling: Complexity Results and Algorithms. ARRIVAL-TR-0172, ARRIVAL Project (2008)
Cicerone, S., Di Stefano, G., Schachtebeck, M., Schöbel, A.: Dynamic Algorithms for Recoverable Robustness Problems. In: The 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, ATMOS (2008)
D’Angelo, G., Di Stefano, G., Navarra, A.: A Dynamic Programming Approach for Recoverable Robust Timetables on Trees. ARRIVAL-TR-0217, ARRIVAL Project (2009)
D’Angelo, G., Di Stefano, G., Navarra, A.: Recoverable-Robust Timetables for Trains on Single-Line Corridors. In: The 3rd International Seminar on Railway Operations Modelling and Analysis, RailZurich (2009)
D’Angelo, G., Di Stefano, G., Navarra, A.: Recoverable Robust Timetables on Trees. ARRIVAL-TR-0163, ARRIVAL Project (2008)
De Giovanni, L., Heilporn, G., Labbé, M.: Optimization Models for the Delay Management Problem in Public Transportation. European Journal of Operational Research 189(3), 762–774 (2007)
Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)
Gatto, M., Jacob, R., Peeters, L., Widmayer, P.: Online Delay Management on a Single Train Line. In: Geraets, F., Kroon, L.G., Schoebel, A., Wagner, D., Zaroliagis, C.D. (eds.) Railway Optimization 2004. LNCS, vol. 4359, pp. 306–320. Springer, Heidelberg (2007)
Ginkel, A., Schöbel, A.: The Bicriteria Delay Management Problem. Transportation Science 4(41), 527–538 (2007)
Levy, F.K., Thompson, G.L., Wies, J.D.: The ABCs of the Critical Path Method. Graduate School of Business Administration, Harvard University (1963)
Liebchen, C., Lübbecke, M., Möhring, R.H., Stiller, S.: Recoverable Robustness. ARRIVAL-TR-0066, ARRIVAL Project (2007)
Schöbel, A.: A Model for the Delay Management Problem Based on Mixed Integer Programming. ENTCS 50(1), 1–10 (2004)
Schöbel, A.: Integer Programming Approaches for Solving the Delay Management. In: Geraets, F., Kroon, L.G., Schoebel, A., Wagner, D., Zaroliagis, C.D. (eds.) Railway Optimization 2004. LNCS, vol. 4359, pp. 145–170. Springer, Heidelberg (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
D’Angelo, G., Di Stefano, G., Navarra, A., Pinotti, C.M. (2009). Recoverable Robust Timetables on Trees. In: Du, DZ., Hu, X., Pardalos, P.M. (eds) Combinatorial Optimization and Applications. COCOA 2009. Lecture Notes in Computer Science, vol 5573. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02026-1_43
Download citation
DOI: https://doi.org/10.1007/978-3-642-02026-1_43
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02025-4
Online ISBN: 978-3-642-02026-1
eBook Packages: Computer ScienceComputer Science (R0)