“Een defecte trein blokkeert één van beide sporen." Brengt wiskunde je sneller thuis?
“Een defecte trein blokkeert één van beide sporen”
Brengt wiskunde je sneller thuis?
Als je regelmatig met de trein reist, heb je het vast al eens meegemaakt. Je bent gehaast en net dan is er een storing in de dienstregeling. Een stilgevallen trein op een druk stuk spoor bijvoorbeeld, leidt tot grote vertragingen, afgeschafte treinen, en heel wat ergernis bij reizigers. Momenteel nemen dispatchers bij Infrabel en NMBS beslissingen vooral op basis van ervaring. Wat als we hier eens wiskundige modellen toepassen? Leidt dit tot een betere service?
89,2%. Dat is het percentage treinen dat vorig jaar op tijd reed, minder dan in 2015. Daarnaast werden er over het hele jaar net geen 23.000 treinen afgeschaft. Een groot deel hiervan komt door storingen zoals een seinstoring of een stilgevallen trein. In deze situaties kunnen treinen natuurlijk nog steeds over de andere sporen rijden. Dispatchers beslissen welke treinen er nog mogen rijden, en in welke volgorde ze dat doen. Deze beslissingen hebben een directe impact op hoe laat jij thuiskomt. Je zou dus verwachten dat dispatchers hierbij goed ondersteund worden. De realiteit blijkt voorlopig minder rooskleurig te zijn. Het Traffic Management System (TMS) detecteert enkel of er in de komende 15 minuten een conflict zal optreden tussen twee treinen. De dispatcher beslist op basis van eigen ervaring, zonder informatie over hoe dit conflict best wordt opgelost.
“Elke storing is uniek” (?)
In Nederland, Duitsland en Japan beschikt men over plannen die voorschrijven welke beslissingen dispatchers dienen te nemen tijdens een storing. Niet zo in België, met het idee dat “elke storing uniek is”. Inderdaad, tijdstip en locatie zullen hoogstwaarschijnlijk verschillen. Vraag is of dit ook geldt voor het effect op het treinverkeer en de te nemen beslissingen? Stel dat een trein stilvalt op een stuk met twee sporen, tussen twee wissels. Of dit nu tussen Tienen en Landen, of Beervelde en Gent gebeurt; in essentie blijft de beslissing dezelfde. Welke treinen rijden over het overblijvende spoor, en in welke volgorde? Parameters zoals de afstand tussen de wissels en de maximale snelheid hebben wel een invloed op de beste beslissing. Tenzij je een encyclopedie wilt schrijven, hebben voorgedefinieerde plannen dus niet veel zin. Flexibele, wiskundige tools kunnen daarentegen wel zeer nuttig zijn. In mijn eindwerk worden drie wiskundige modellen van toenemende complexiteit ontwikkeld. Deze zijn toepasbaar op dubbelsporige stukken zonder haltes, mét haltes, en op infrastructuur met meer dan twee sporen.
Het spoornetwerk als machine
Stel je voor: we hebben één machine die een aantal taken dient uit te voeren. De taken hebben ook vereisten: ze hebben een starttijd en een deadline. Wordt die deadline overschreden, dan kost dit geld. Daarnaast kunnen we ook kiezen om taken af te wijzen en een boete te betalen, zodat andere sneller gepland kunnen worden. Het doel: een zo goedkoop mogelijk productieplan opstellen. In de wiskunde heet dit een “één-machineplanningsprobleem”.
Met een beetje creativiteit, toont het probleem van onze dispatcher sterke gelijkenissen. Op een stukje spoor (machine), moeten we verschillende treinen (taken) plannen. Een trein kan echter niet op dit stukje spoor komen voordat hij de reis ernaartoe heeft afgelegd (starttijd). Liefst verlaat de trein deze machine volgens plan (deadline). Soms dreigen vertragingen sterk op te lopen en is het beter een trein af te schaffen (afwijzen). Het wiskundige model moet dan beslissen over de volgorde waarin treinen over het stukje spoor rijden en welke er worden afgeschaft. Een goede service betekent zo weinig mogelijk afgeschafte treinen en vertraging. Daarnaast kunnen we in een machineplanningsprobleem ook andere zaken beschouwen: drukkere treinen krijgen een hogere bestraffing als ze worden vertraagd, er moet een minimum aantal treinen per uur rijden, treinen kunnen worden omgeleid, en ga zo maar door …
Indien er haltes langs het stuk spoor liggen, zouden stoptreinen hier reizigers moeten laten in- en uitstappen. Vaak gaat het echter om veel kleinere aantallen dan de doorgaande reizigers. Tijdens een storing kun je je dus afvragen of het niet beter is een halte over te slaan zodat daaropvolgende treinen minder vertraging oplopen. De bestraffing berekenen we op basis van het aantal in- en uitstappers en hun toename in reistijd. Het is dan aan het model om te beslissen wat de beste strategie is, mits een minimum aantal stops behouden blijft.
Op infrastructuur met meer dan twee sporen wordt het probleem complexer. We moeten namelijk ook beslissen welke trein over welk spoor zal rijden. Dit lijkt eenvoudiger dan het in werkelijkheid is. De wisselstraten aan beide zijden van de storing laten namelijk heel wat verschillende combinaties toe. Het zou kunnen dat een bepaalde beslissing aan de ene zijde van de storing heel goed uitpakt, maar aan de andere zijde leidt tot een conflict en bijkomende vertragingen.
Dispatcher versus wiskunde
De ontwikkelde modellen werden toegepast op realistische en zelfbedachte situaties. Twee algoritmes bootsten de beslissingen van een (onervaren) dispatcher na. De modellen slaagden er in een veel betere afweging te maken welke wachtende trein er eerst mag doorrijden. Ze houden hierbij namelijk rekening met de vertraging voor alle daaropvolgende treinen. Momenteel worden stops zelden overgeslagen omdat men niet weet wat het precieze effect is. In onze resultaten werd dit relatief vaak gedaan om te vermijden dat er later op de dag een trein werd afgeschaft. De modellen bewezen al helemaal hun nut bij de hogere complexiteit indien er meer sporen zijn. We zijn er dus van overtuigd dat onze modellen tot betere resultaten kunnen leiden.
Deze kleinschalige modellen blijken nuttig voor storingen op zowat 50% van de infrastructuur tussen grotere stations. Ze werken echter op een klein gebied, en zeggen niets over de planning voor treinmaterieel en -personeel. In realiteit zou een dispatcher dus best eerst informatie over de storing verzamelen en doorgeven aan het model. Het model neemt de huidige situatie uit het TMS en na korte tijd wordt de best gevonden oplossing voorgesteld aan de dispatcher, die deze aanvaardt of verder bijstelt. Deze aanpak bundelt de kennis van dispatchers enerzijds, en de kracht en flexibiliteit van de modellen anderszijds, om jou sneller thuis te brengen.
Bibliografie
[1] M. Abril, F. Barber, L. Ingolotti, M. A. Salido, P. Tormos, and A. Lova. “An assessment of railway capacity”. In: Transportation Research Part E: Logistics and Transportation Review 44.5 (2008), pp. 774–806.
[2] K. R. Baker, G. D. Scudder, D. Trietsch, and S. T. Webster. Elements of Sequencing and Scheduling. Michigan, USA: University of Michigan, 1995, p. 242.
[3] Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, J. Sgall, and L. Stougie. “Multiprocessor scheduling with rejection”. In: SIAM Journal on Discrete Mathematics 13.1 (2000), pp. 64–78.
[4] J. E. Beasley, M. Krishnamoorthy, Y. M. Sharaiha, and D. Abramson. “Scheduling aircraft landings – the static case”. In: Transportation science 34.2 (2000), pp. 180–197.
[5] J. A. Bennell, M. Mesgarpour, and C. N. Potts. “Airport runway scheduling”. In: A Quarterly Journal of Operations Research, 4OR 9.2 (2011), pp. 115–138.
[6] N. Besinovic, V. Cacchiani, T. Dollevoet, R. M. P. Goverde, D. Huisman, M. P. Kidd, L. G. Kroon, E. Quaglietta, J. Rodriguez, and P. Toth. “Integrated Decision Support Tools for Disruption Management”. In: Proceedings of the 6th International Conference on Railway Operations Modelling and Analysis (IAROR): RailTokyo2015, March 23-26. Narashino, Japan, 2015.
[7] B. Boškovic, M. Ivic, and A. Markovic. “Organizing transportation on a doubletrack line under conditions of major overhaul on one track”. In: Yugoslav Journal of Operations Research 16.1 (2006), pp. 97–105.
[8] O. Brünger and E. Dahlhaus. “Running Time Estimation”. In: Railway Timetabling & Operations: Analysis - Modelling - Optimisation - Simulation - Performance Evaluation. Ed. by I. A. Hansen and J. Pachl. Hamburg, Germany: Eurailpress, 2014, pp. 65–89.
[9] V. Cacchiani, D. Huisman, M. Kidd, L. Kroon, P. Toth, L. Veelenturf, and J. Wagenaar. “An overview of recovery models and algorithms for real-time railway rescheduling”. In: Transportation Research Part B-Methodological 63 (2014), pp. 15–37.
[10] Z.-L. Chen, Q. Lu, and G. Tang. “Single machine scheduling with discretely controllable processing times”. In: Operations Research Letters 21.2 (1997), pp. 69–76.
[11] F. Chu and A. Oetting. “Modeling capacity consumption considering disruption program characteristics and the transition phase to steady operations during disruptions”. In: Journal of Rail Transport Planning & Management 3.3 (2013), pp. 54–67.
[12] F. Corman, A. D’Ariano, and I. A. Hansen. “Disruption handling in large railway networks”. In: WIT Transactions on The Built Environment 114 (2010), pp. 629–640.
[13] F. Corman, A. D’Ariano, I. A. Hansen, D. Pacciarelli, and M. Pranzo. “Dispatching trains during seriously disrupted traffic situations”. In: 2011 IEEE International Conference on Networking, Sensing and Control (ICNSC), April 11-13. Delft, the Netherlands, 2011, pp. 323–328.
[14] F. Corman, A. D’Ariano, D. Pacciarelli, and M. Pranzo. “A tabu search algorithm for rerouting trains during rail operations”. In: Transportation Research Part B: Methodological 44.1 (2010), pp. 175–192.
[15] A. D’Ariano, P. D’Urgolo, D. Pacciarelli, and M. Pranzo. “Optimal sequencing of aircrafts take-off and landing at a busy airport”. In: 2010 13th International IEEE Conference on Intelligent Transportation Systems (ITSC), September 19-22. Madeira Island, Portugal, 2010, pp. 1569–1574.
[16] A. D’Ariano, D. Pacciarelli, and M. Pranzo. “A branch and bound algorithm for scheduling trains in a railway network”. In: European Journal of Operational Research 183.2 (2007), pp. 643–657.
[17] T. Dollevoet, D. Huisman, L. G. Kroon, L. P. Veelenturf, and J. C. Wagenaar. “Application of an iterative framework for real-time railway rescheduling”. In: Computers & Operations Research 78 (2017), pp. 203–217.
[18] W. Eggermont. An Introduction to Belgian Signalling - SNCB, Student Manual, Version 2.0. Brussels, Belgium: NMBS, n.d.
[19] N. Ghaemi and R. M. P. Goverde. “Review of railway disruption management practice and literature”. In: Proceedings of the 6th International Conference on Railway Operations Modelling and Analysis (IAROR): RailTokyo2015, March 23-26. Narashino, Japan, 2015.
[20] M. van Hagen. “Waiting experience at train stations”. PhD thesis. Twente, the Netherlands: Universiteit Twente, 2011.
[21] I. A. Hansen and J. Pachl. Railway Timetabling & Operations: Analysis - Modelling - Optimisation - Simulation - Performance Evaluation. Hamburg, Germany: Eurailpress, 2014, p. 330.
[22] IBM. IBM Knowledge Center - IBM ILOG CPLEX Optimization Studio V12.6.3 documentation. [Last accessed 25/12/2016]. 2015. url: http://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.2/ilog.odms.studio.help/Optimization_Studio/topics/COS_home.html.
[23] IBM. IBM Knowledge Center - MIP emphasis switch. [Last accessed 10/10/2016]. 2016. url: http://www.ibm.com/support/knowledgecenter/SS9UKU_12.4.0/com.ibm.cplex.zos.help/Parameters/topics/MIPEmphasis.html.
[24] Infrabel. Punctuality figures. [Last accessed 17/12/2016]. 2016. url: https://www.infrabel.be/en/about/punctuality-figures.
[25] Infrabel. Safety and Signalling Plans L36, zone Leuven, block 9 (1-FLV-002/99, pp. 14–17). Map. 2012.
[26] Infrabel. The Network Statement - C.4 Technical Map of the Network. [Last accessed 24/12/2016]. Jan. 2016. url: http://www.infrabel.be/en/professionals/rail-operators/network-statement.
[27] J. Jespersen-Groth, D. Potthoff, J. Clausen, D. Huisman, L. Kroon, G. Maróti, and M. N. Nielsen. “Disruption Management in Passenger Railway Transportation”. In: Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems. Ed. by R. K. Ahuja, R. H. Möhring, and C. D. Zaroliagis. Berlin, Germany: Springer, 2009, pp. 399–421.
[28] K. Kerckaert. “Vision and strategic considerations of the current and future transportation plans of SNCB”. In: Presented during the 2nd Railway Operations Research Seminar “Put Passengers First”, May 3. Leuven, Belgium, 2016.
[29] L. Kroon and D. Huisman. Algorithmic Support for Disruption Management at Netherlands Railways. Econometric Institute Research Papers EI 2011-06. Rotterdam, the Netherlands: Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute, 2011. url: http://EconPapers.repec.org/RePEc:ems:eureir:22456.
[30] M. Lambrechts. Visit to Infrabel’s local signal box in Leuven. Visit. Leuven, Belgium, Oct. 2016.
[31] J. Löfberg. “YALMIP : A Toolbox for Modeling and Optimization in MATLAB”. In: Proceedings of the CACSD Conference, September 2-4. Taipei, Taiwan, 2004.
[32] I. Louwerse and D. Huisman. “Adjusting a railway timetable in case of partial or complete blockades”. In: European Journal of Operational Research 235.3 (2014), pp. 583–593.
[33] A. S. Manne. “On the job-shop scheduling problem”. In: Operations Research 8.2 (1960), pp. 219–223.
[34] A. Mascis and D. Pacciarelli. “Job-shop scheduling with blocking and no-wait constraints”. In: European Journal of Operational Research 143.3 (2002), pp. 498–517.
[35] MATLAB version 9.0.0.341360 (R2016a). The Mathworks, Inc. Natick, Massachusetts, 2016.
[36] T. Nakamura, C. Hirai, and Y. Nishioka. “A practical train rescheduling algorithm using three predetermined factors”. In: Proceedings of the 4th International Seminar on Railway Operations Modelling and Analysis (IAROR): RailRome2011, February 16-18. Rome, Italy, 2011.
[37] S. Narayanaswami and N. Rangaraj. “Modelling disruptions and resolving conflicts optimally in a railway schedule”. In: Computers & Industrial Engineering 64.1 (2013), pp. 469–481.
[38] NMBS. Lijnfolders - Lijn 36: Brussel-Zuid - Luik-Guillemins. [Last accessed 05/11/2016]. 2016. url: https://www.belgianrail.be/nl/klantendienst/infodiensten-reistools/lijnfolders.aspx.
[39] NMBS. NMBS Visie en activiteiten 2014. Report. Brussels, Belgium, 2015.
[40] NMBS. Reisplanner. [Last accessed 20/10/2016]. 2016. url: http://www.belgianrail.be/jp/nmbs-routeplanner/query.exe/nn.
[41] T. H. Nogueira, C. R. V. de Carvalho, and M. G. Ravetti. “Analysis of mixed integer programming formulations for single machine scheduling problems with sequence dependent setup times and release dates”. In: Optimization Online (2014).
[42] A. Oetting and F. Chu. “Disruption Programs in Passenger Rail Transport - Ensuring Steady Operations During Disruptions”. In: 13th World Conference on Transport Research (WCTR), July 15-18. Rio de Janeiro, Brazil, 2013.
[43] J. Pachl. “Timetable Design Principles”. In: Railway Timetabling & Operations: Analysis - Modelling - Optimisation - Simulation - Performance Evaluation. Ed. by I. A. Hansen and J. Pachl. Hamburg, Germany: Eurailpress, 2014, pp. 13–46.
[44] W. Passchyn. “Scheduling Locks on Inland Waterways”. PhD thesis. Leuven, Belgium: KU Leuven, 2016.
[45] P. Pellegrini, G. Marlière, and J. Rodriguez. “Optimal train routing and scheduling for managing traffic perturbations in complex junctions”. In: Transportation Research Part B: Methodological 59 (2014), pp. 58–80.
[46] E. Quaglietta, P. Pellegrini, R. M. P. Goverde, T. Albrecht, B. Jaekel, G. Marlière, J. Rodriguez, T. Dollevoet, B. Ambrogio, D. Carcasole, M. Giaroli, and G. Nicholson. “The ON-TIME real-time railway traffic management framework: A proof-of-concept using a scalable standardised data communication architecture”. In: Transportation Research Part C: Emerging Technologies 63 (2016), pp. 23–50.
[47] A. Radtke. “Infrastructure Modelling”. In: Railway Timetabling & Operations: Analysis - Modelling - Optimisation - Simulation - Performance Evaluation. Ed. by I. A. Hansen and J. Pachl. Hamburg, Germany: Eurailpress, 2014, pp. 47–63.
[48] RailNetEurope. Network Statement Glossary. [Last accessed 06/11/2016]. 2016. url: http://www.rne.eu/ns_glossary
[49] P. L. Rocha, M. G. Ravetti, G. R. Mateus, and P. M. Pardalos. “Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times”. In: Computers & Operations Research 35.4 (2008), pp. 1250–1264.
[50] J. Rodriguez, P. Pellegrini, G. Marlière, S. Hu, and S. S. Richard. “Improvement of real-time traffic management by using optimization tools”. In: Procedia - Social and Behavioral Sciences 160 (2014), pp. 465–473.
[51] Y. Segers. “Analyseren en beperken van de impact van tijdelijke snelheidsbeperkingen op het spoorwegnetwerk”. MSc. Thesis. KU Leuven, 2015.
[52] P. Sels, T. Dewilde, D. Cattrysse, and P. Vansteenwegen. “Deriving all passenger flows in a railway network from ticket sales data”. In: Proceedings of the 4th International Seminar on Railway Operations Modelling and Analysis (IAROR): RailRome2011, February 16-18. Rome, Italy, 2011.
[53] Standaardfiche 36 Brussel-Noord Liège-Guillemins 36. [Last accessed 05/12/2016]. 2016. url: http://wayback.archive.org/web/20080516130438/http://users.pandora.be/brail/lijn/lijn36.htm.
[54] J. Törnquist and J. A. Persson. “N-tracked railway traffic re-scheduling during disturbances”. In: Transportation Research Part B: Methodological 41.3 (2007), pp. 342–362.
[55] UIC. UIC Code 406 - Capacity. Tech. rep. Paris, France: Union International des Chemins de Fer, 2004.
[56] S. Van Thielen, S. Burggraeve, and P. Vansteenwegen. “Optimal train rescheduling after conflict detection”. In: Conference on Advanced Systems in Public Transport (CASPT2015), July 19-22. Rotterdam, the Netherlands, 2015.
[57] L. P. Veelenturf, M. P. Kidd, V. Cacchiani, L. G. Kroon, and P. Toth. “A railway timetable rescheduling approach for handling large-scale disruptions”. In: Transportation Science 50.3 (2015), pp. 841–862.
[58] D. van de Velde, C. Nash, A. Smith, F. Mizutani, S. Uranishi, M. Lijesen, and F. Zschoche. EVES–Rail - Economic effects of Vertical Separation in the railway sector. Tech. rep. Amsterdam, the Netherlands: inno-V, 2012.
[59] R. Watson and G. Medeossi. “Simulation”. In: Railway Timetabling & Operations: Analysis - Modelling - Optimisation - Simulation - Performance Evaluation. Ed. by I. A. Hansen and J. Pachl. Hamburg, Germany: Eurailpress, 2014, pp. 191–215.
[60] S. Zhan, L. G. Kroon, J. Zhao, and Q. Peng. “A rolling horizon approach to thehigh speed train rescheduling problem in case of a partial segment blockage”.In: Transportation Research Part E: Logistics and Transportation Review 95 (2016), pp. 32–61.
[61] L. Zhang, L. Lu, and J. Yuan. “Single machine scheduling with release dates and rejection”. In: European Journal of Operational Research 198.3 (2009), pp. 975–978.
