Seite - 97 - in Algorithms for Scheduling Problems

algorithms Article AHeuristicApproachtoSolvingtheTrainTraffic Re-SchedulingProbleminRealTime OmidGholami*andJohannaTörnquistKrasemann DepartmentofComputerScienceandEngineering,BlekingeInstituteofTechnology,Valhallavägen1, 37179Karlskrona,Sweden; johanna.tornquist.krasemann@bth.se * Correspondence: omid.gholami@bth.se;Tel.:+46-(0)455-385-845 Received: 28February2018;Accepted: 12April2018;Published: 21April2018 Abstract:Effectiveness inmanagingdisturbancesanddisruptions inrailwaytrafficnetworks,when they inevitablydooccur, isasignificantchallenge,both fromapracticalandtheoreticalperspective. In thispaper,weproposeaheuristicapproach for solving thereal-time train traffic re-scheduling problem.Thisproblemishere interpretedasablocking job-shopschedulingproblem,andahybridof themixedgraphandalternativegraphisusedformodelling the infrastructureandtrafficdynamics onamesoscopic level. Aheuristic algorithmisdevelopedandapplied to resolve the conflictsby re-timing, re-ordering, and locally re-routing the trains. Apart of theSouthernSwedish railway network fromKarlskrona centre toMalmö city is considered for an experimental performance assessmentof theapproach. Thenetworkconsists of 290block sections, and for aone-hour time horizonwitharound80active trains, thealgorithmgenerates a solution in less than ten seconds. Abenchmarkwith thecorrespondingmixed-integerprogramformulation, solvedbycommercial state-of-the-art solverGurobi, isalsoconductedtoassess theoptimalityof thegeneratedsolutions. Keywords: railwaytraffic;disturbancemanagement; real-timere-scheduling; job-shopscheduling; optimization;alternativegraph 1. Introduction The definitions of “system performance” and “quality of service” in railway traffic and transportationvary, butmore recent reports, e.g., fromtheBostonConsultancyGroup [1] and the EuropeanCommission[2], indicate thatmanyEuropeancountries facechallengeswithregardto the reliability andpunctuality of rail services. Several different factors contribute to these challenges, where the frequencyandmagnitudeofdisruptionsanddisturbances isonefactor. Theeffectiveness inmanaging thedisturbancesanddisruptions in railway trafficnetworkswhenthey inevitablydo occur isanotheraspect toconsider. In thispaper,wefocusonthe latter, andmorespecifically,onthe problemofreal-timetrain trafficre-scheduling,alsoreferredtoas traindispatching[3]. Ingeneral, theproblemofre-schedulingtrain traffic inreal-timeisknowntobeahardproblem to solvebyexpert trafficdispatchers inpractice, aswell asby state-of-the-art scheduling software. There is thus often a trade-off that needs to bemade regardingpermitted computation time and expectedsolutionquality.Heuristicapproaches,orapproachesbasedon,e.g.,discrete-eventsimulation, are often rather quick, since theywork in a greedymanner, but sometimes they fail to deliver a reasonable solution or even endup indeadlock. Exact approaches, basedon, e.g.,mixed-integer programmingmodelssolvedbybranch-and-cutalgorithmsare,ontheotherhand, lessgreedy,butcan bevery time-consuming,especially if thesearchspace is large,andsuffer fromsignificant redundancy. Anotheraspectconcerns theselected levelofgranularityof the trafficandinfrastructuremodel,and thismayindirectlyaffect thecomputationtimeandthequalityof thesolutionaswell. Over the latest three decades, a variety of algorithms andmethods have been proposed to solve the train trafficre-scheduling(or, traindispatching)problem,see [3–6] formorerecentsurveys. Algorithms 2018,11, 55;doi:10.3390/a11040055 www.mdpi.com/journal/algorithms97