SpringerLink
Log in

Rescheduling Railway Traffic on Real Time Situations Using Time-Interval Variables

  • Conference paper
  • First Online:
Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2017)

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

  • 1840 Accesses

Abstract

In the railway domain, the action of directing the traffic in accordance with an established timetable is managed by a software. However, in case of real time perturbations, the initial schedule may become infeasible or suboptimal. Subsequent decisions must then be taken manually by an operator in a very limited time in order to reschedule the traffic and reduce the consequence of the disturbances. They can for instance modify the departure time of a train or redirect it to another route. Unfortunately, this kind of hazardous decisions can have an unpredicted negative snowball effect on the delay of subsequent trains. In this paper, we propose a Constraint Programming model to help the operators to take more informed decisions in real time. We show that the recently introduced time-interval variables are instrumental to model this scheduling problem elegantly. We carried experiments on a large Belgian station with scenarios of different levels of complexity. Our results show that the CP model outperforms the decisions taken by current greedy strategies of operators.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Available at https://bitbucket.org/qcappart/qcappart_opendata.

References

  1. Higgins, A., Kozan, E., Ferreira, L.: Optimal scheduling of trains on a single line track. Transp. Res. Part B Methodol. 30, 147–161 (1996)

    Article  Google Scholar 

  2. Ghoseiri, K., Szidarovszky, F., Asgharpour, M.J.: A multi-objective train scheduling model and solution. Transp. Res. Part B Methodol. 38, 927–952 (2004)

    Article  MATH  Google Scholar 

  3. Zhou, X., Zhong, M.: Bicriteria train scheduling for high-speed passenger railroad planning applications. Eur. J. Oper. Res. 167, 752–771 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  4. Harabor, D., Stuckey, P.J.: Rail capacity modelling with constraint programming. In: Quimper, C.-G. (ed.) CPAIOR 2016. LNCS, vol. 9676, pp. 170–186. Springer, Cham (2016). doi:10.1007/978-3-319-33954-2_13

    Google Scholar 

  5. Senthooran, I., Wallace, M., Koninck, L.: Freight train threading with different algorithms. In: Michel, L. (ed.) CPAIOR 2015. LNCS, vol. 9075, pp. 393–409. Springer, Cham (2015). doi:10.1007/978-3-319-18008-3_27

    Google Scholar 

  6. Cacchiani, V., Huisman, D., Kidd, M., Kroon, L., Toth, P., Veelenturf, L., Wagenaar, J.: An overview of recovery models and algorithms for real-time railway rescheduling. Transp. Res. Part B Methodol. 63, 15–37 (2014)

    Article  Google Scholar 

  7. Fay, A.: A fuzzy knowledge-based system for railway traffic control. Eng. Appl. Artif. Intell. 13, 719–729 (2000)

    Article  Google Scholar 

  8. Higgins, A., Kozan, E., Ferreira, L.: Heuristic techniques for single line train scheduling. J. Heuristics 3, 43–62 (1997)

    Article  MATH  Google Scholar 

  9. Dariano, A., Pacciarelli, D., Pranzo, M.: A branch and bound algorithm for scheduling trains in a railway network. Eur. J. Oper. Res. 183, 643–657 (2007)

    Article  MATH  Google Scholar 

  10. D’Ariano, A., Corman, F., Pacciarelli, D., Pranzo, M.: Reordering and local rerouting strategies to manage train traffic in real time. Transp. Sci. 42, 405–419 (2008)

    Article  Google Scholar 

  11. Schachtebeck, M., Schöbel, A.: To wait or not to wait and who goes first? delay management with priority decisions. Transp. Sci. 44, 307–321 (2010)

    Article  Google Scholar 

  12. Dollevoet, T., Huisman, D., Schmidt, M., Schöbel, A.: Delay management with rerouting of passengers. Transp. Sci. 46, 74–89 (2012)

    Article  Google Scholar 

  13. Dollevoet, T., Huisman, D., Kroon, L., Schmidt, M., Schöbel, A.: Delay management including capacities of stations. Transp. Sci. 49, 185–203 (2014)

    Article  Google Scholar 

  14. Corman, F., Goverde, R.M.P., D’Ariano, A.: Rescheduling dense train traffic over complex station interlocking areas. In: Ahuja, R.K., Möhring, R.H., Zaroliagis, C.D. (eds.) Robust and Online Large-Scale Optimization. LNCS, vol. 5868, pp. 369–386. Springer, Heidelberg (2009). doi:10.1007/978-3-642-05465-5_16

    Chapter  Google Scholar 

  15. Foglietta, S., Leo, G., Mannino, C., Perticaroli, P., Piacentini, M.: An optimized, automatic TMS in operations in Roma Tiburtina and monfalcone stations. WIT Trans. Built Environ. 135, 635–647 (2014)

    Article  Google Scholar 

  16. Araya, S., Abe, K., Fukumori, K.: An optimal rescheduling for online train traffic control in disturbed situations. In: The 22nd IEEE Conference on Decision and Control, 1983, pp. 489–494. IEEE (1983)

    Google Scholar 

  17. Lamorgese, L., Mannino, C.: An exact decomposition approach for the real-time train dispatching problem. Oper. Res. 63, 48–64 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  18. Baptiste, P., Le Pape, C., Nuijten, W.: Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems, vol. 39. Springer Science & Business Media, US (2012)

    MATH  Google Scholar 

  19. Barták, R., Salido, M.A., Rossi, F.: New trends in constraint satisfaction, planning, and scheduling: a survey. Knowl. Eng. Rev. 25, 249–279 (2010)

    Article  Google Scholar 

  20. Kelareva, E., Brand, S., Kilby, P., Thiébaux, S., Wallace, M., et al.: CP and MIP methods for ship scheduling with time-varying draft. In: ICAPS (2012)

    Google Scholar 

  21. Kelareva, E., Tierney, K., Kilby, P.: CP methods for scheduling and routing with time-dependent task costs. In: Gomes, C., Sellmann, M. (eds.) CPAIOR 2013. LNCS, vol. 7874, pp. 111–127. Springer, Heidelberg (2013). doi:10.1007/978-3-642-38171-3_8

    Chapter  Google Scholar 

  22. Ku, W.Y., Beck, J.C.: Revisiting off-the-shelf mixed integer programming and constraint programming models for job shop scheduling. Dept Mech. Ind. Eng., Univ. Toronto, Toronto, ON, Canada, Technical report. MIE-OR-TR2014-01 (2014)

    Google Scholar 

  23. Rodriguez, J.: A constraint programming model for real-time train scheduling at junctions. Transp. Res. Part B Methodol. 41, 231–245 (2007)

    Article  Google Scholar 

  24. Laborie, P., Rogerie, J.: Reasoning with conditional time-intervals. In: FLAIRS Conference, pp. 555–560 (2008)

    Google Scholar 

  25. Laborie, P., Rogerie, J., Shaw, P., Vilím, P.: Reasoning with conditional time-intervals. Part II: an algebraical model for resources. In: FLAIRS Conference (2009)

    Google Scholar 

  26. Vilím, P., Laborie, P., Shaw, P.: Failure-directed search for constraint-based scheduling. In: Michel, L. (ed.) CPAIOR 2015. LNCS, vol. 9075, pp. 437–453. Springer, Cham (2015). doi:10.1007/978-3-319-18008-3_30

    Google Scholar 

  27. Laborie, P.: IBM ILOG CP optimizer for detailed scheduling illustrated on three problems. In: Hoeve, W.-J., Hooker, J.N. (eds.) CPAIOR 2009. LNCS, vol. 5547, pp. 148–162. Springer, Heidelberg (2009). doi:10.1007/978-3-642-01929-6_12

    Chapter  Google Scholar 

  28. Vilím, P.: Max energy filtering algorithm for discrete cumulative resources. In: Hoeve, W.-J., Hooker, J.N. (eds.) CPAIOR 2009. LNCS, vol. 5547, pp. 294–308. Springer, Heidelberg (2009). doi:10.1007/978-3-642-01929-6_22

    Chapter  Google Scholar 

  29. Salido, M.A., Escamilla, J., Barber, F., Giret, A., Tang, D., Dai, M.: Energy-aware parameters in job-shop scheduling problems. In: GREEN-COPLAS 2013: IJCAI 2013 Workshop on Constraint Reasoning, Planning and Scheduling Problems for a Sustainable Future, pp. 44–53(2013)

    Google Scholar 

  30. Hait, A., Artigues, C.: A hybrid CP/MILP method for scheduling with energy costs. Eur. J. Ind. Eng. 5, 471–489 (2011)

    Article  Google Scholar 

  31. Theeg, G.: Railway Signalling & Interlocking: International Compendium. Eurailpress (2009)

    Google Scholar 

  32. Cappart, Q., Schaus, P.: A dedicated algorithm for verification of interlocking systems. In: Skavhaug, A., Guiochet, J., Bitsch, F. (eds.) SAFECOMP 2016. LNCS, vol. 9922, pp. 76–87. Springer, Cham (2016). doi:10.1007/978-3-319-45477-1_7

    Chapter  Google Scholar 

  33. Yamada, T., Nakano, R.: Job shop scheduling. IEE Control Engineering Series, p. 134 (1997)

    Google Scholar 

  34. Dechter, R., Meiri, I., Pearl, J.: Temporal constraint networks. Artif. Intell. 49, 61–95 (1991)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

This research is financed by the Walloon Region as part of the Logistics in Wallonia competitiveness pole. Experiments have been performed with ILOG CP Optimizer through the academic initiative of IBM.

Author information

Authors and Affiliations

  1. Université catholique de Louvain, Louvain-la-Neuve, Belgium

    Quentin Cappart & Pierre Schaus

Authors
  1. Quentin Cappart
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pierre Schaus
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Quentin Cappart .

Editor information

Editors and Affiliations

  1. University of Padua, Padua, Italy

    Domenico Salvagnin

  2. University of Bologna, Bologna, Italy

    Michele Lombardi

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Cappart, Q., Schaus, P. (2017). Rescheduling Railway Traffic on Real Time Situations Using Time-Interval Variables. In: Salvagnin, D., Lombardi, M. (eds) Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2017. Lecture Notes in Computer Science(), vol 10335. Springer, Cham. https://doi.org/10.1007/978-3-319-59776-8_26

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-59776-8_26

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-59775-1

  • Online ISBN: 978-3-319-59776-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation