Skip to main content
Springer Nature Link
Log in

Integer Programming Approaches for Solving the Delay Management Problem

  • Conference paper
Algorithmic Methods for Railway Optimization

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4359))

  • 2750 Accesses

Abstract

The delay management problem deals with reactions in case of delays in public transportation. More specifically, the aim is to decide if connecting vehicles should wait for delayed feeder vehicles or if it is better to depart on time. As objective we consider the convenience over all customers, expressed as the average delay of a customer when arriving at his or her destination.

We present path-based and activity-based integer programming models for the delay management problem and show the equivalence of these formulations. Based on these, we present a simplification of the (cubic) activity-based model which results in an integer linear program. We identify cases in which this linearization is correct, namely if the so-called never-meet property holds. We analyze this property using real-world railway data. Finally, we show how to find an optimal solution in linear time if the never-meet property holds.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Ackermann, T.: Die Bewertung der Pünktlichkeit als Qualitätsparameter im Schienenpersonennahverkehr auf Basis der direkten Nutzenmessung. PhD thesis, Universität Stuttgart (1999)

    Google Scholar 

  2. Anderegg, L., Penna, P., Widmayer, P.: Online train disposition: to wait or not to wait? Electronic Notes in Theoretical Computer Science, 66(6) (2002)

    Google Scholar 

  3. Bissantz, N., Güttler, S., Jacobs, J., Kurby, S., Schaer, T., Schöbel, A., Scholl, S.: DisKon - Disposition und Konfliktlösungs-management für die beste Bahn (in German). Eisenbahntechnische Rundschau (ETR) 45(12), 809–821 (2005)

    Google Scholar 

  4. Carey, M.: Ex ante heuristic measures of schedule reliability. Transportation Research 53B(3), 473–494 (1999)

    Google Scholar 

  5. Elmaghraby, S.E.: Activity Networks. Wiley Interscience Publication, Chichester (1977)

    MATH  Google Scholar 

  6. Engelhardt-Funke, O.: Stochastische Modellierung und Simulation von Verspätungen in Verkehrsnetzen für die Anwendung der Fahrplanoptimierung. PhD thesis, Univerität Clausthal (2002)

    Google Scholar 

  7. Engelhardt-Funke, O., Kolonko, M.: Simulating delays for realistic timetable-optimization. In: Operations Research Proceedings 2001, pp. 9–15. Springer, Heidelberg (2001)

    Google Scholar 

  8. Gatto, M., Glaus, B., Jacob, R., Peeters, L., Widmayer, P.: Railway delay management: Exploring its algorithmic complexity. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 199–211. Springer, Heidelberg (2004)

    Google Scholar 

  9. Gatto, M., Jacob, R., Peeters, L., Schöbel, A.: The computational complexity of delay management. In: Kratsch, D. (ed.) WG 2005. LNCS, vol. 3787, Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  10. Gatto, M., Jacob, R., Peeters, L., Widmayer, P.: On-line delay management on a single train line (presented at ATMOS 2004). In: Algorithmic Methods for Railway Optimization. LNCS, Springer, Heidelberg, 2006 (to appear)

    Google Scholar 

  11. Ginkel, A., Schöbel, A.: The bicriterial delay management problem. Technical report, Universität Kaiserslautern (2002)

    Google Scholar 

  12. Giovanni, L., Heilporn, G., Labbé, M.: Optimization models for the delay management problem in public transportation. European Journal of Operational Research, 2006 (to appear)

    Google Scholar 

  13. Goverde, R.M.P.: The max-plus algebra approach to railway timetable design. In: Computers in Railways VI: Proceedings of the 6th international conference on computer aided design, manufacture and operations in the railway and other advanced mass transit systems, Lisbon, 1998, pp. 339–350 (1998)

    Google Scholar 

  14. Kliewer, N.: Mathematische Optimierung zur Unterstützung kundenorientierter Disposition im Schienenverkehr. Master’s thesis, Universität Paderborn (2000)

    Google Scholar 

  15. Nachtigall, K.: Periodic Network Optimization and Fixed Interval Timetables. Deutsches Zentrum für Luft– und Raumfahrt, Institut für Flugführung, Braunschweig, Habilitationsschrift (1998)

    Google Scholar 

  16. Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, Chichester (1988)

    MATH  Google Scholar 

  17. Peeters, L.: Cyclic Railway Timetabling Optimization. PhD thesis, ERIM, Rotterdam School of Management (2002)

    Google Scholar 

  18. De Schutter, B., de Vries, R., De Moor, B.: On max-algebraic models for transportation networks. In: Proceedings of the International Workshop on Discrete Event Systems, Cagliari, Italy, pp. 457–462 (1998)

    Google Scholar 

  19. Schöbel, A.: A model for the delay management problem based on mixed-integer programming. Electronic Notes in Theoretical Computer Science 50(1) (2001)

    Google Scholar 

  20. Schöbel, A.: Customer-oriented optimization in public transportation. In: Applied Optimization, Springer, New York, 2006 (to appear)

    Google Scholar 

  21. Scholl, S.: Anschlusssicherung bei Verspätungen im öPNV. Master’s thesis, Universität Kaiserslautern (2001)

    Google Scholar 

  22. De Schutter, B., van den Boom, T.: Model predictive control for railway networks. In: Proceedings of the 2001 IEEE/ASME International Conference on Advanced Intelligent Mechatronics, Como, Italy, pp. 105–110 (2001)

    Google Scholar 

  23. Suhl, L., Biederbick, C., Kliewer, N.: Design of customer-oriented dispatching support for railways. In: Voß, S., Daduna, J. (eds.) Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical systems, vol. 505, pp. 365–386. Springer, Heidelberg (2001)

    Google Scholar 

  24. Suhl, L., Mellouli, T.: Managing and preventing delays in railway traffic by simulation and optimization. In: Mathematical Methods on Optimization in Transportation Systems, pp. 3–16. Kluwer, Dordrecht (2001)

    Google Scholar 

  25. Suhl, L., Mellouli, T., Biederbick, C., Goecke, J.: Managing and preventing delays in railway traffic by simulation and optimization. In: Pursula, M., Niittymäki (eds.) Mathematical methods on Optimization in Transportation Systems, pp. 3–16. Kluwer, Dordrecht (2001)

    Google Scholar 

  26. van Egmond, R.J.: An algebraic approach for scheduling train movements. In: Proceedings of the 8th international conference on Computer-Aided Transit Scheduling, Berlin, 2000 (2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute for Numerical and Applied Mathematics, Georg-August University, Göttingen,  

    Anita Schöbel

Authors
  1. Anita Schöbel
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Frank Geraets Leo Kroon Anita Schoebel Dorothea Wagner Christos D. Zaroliagis

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Schöbel, A. (2007). Integer Programming Approaches for Solving the Delay Management Problem. In: Geraets, F., Kroon, L., Schoebel, A., Wagner, D., Zaroliagis, C.D. (eds) Algorithmic Methods for Railway Optimization. Lecture Notes in Computer Science, vol 4359. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74247-0_7

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-74247-0_7

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-74245-6

  • Online ISBN: 978-3-540-74247-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation