Page - 110 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 55 beginningof its itineraryandthusmaycauseknock-ondelays if it isdelayed. The less totalprocessing time (DR-6)dispatching rule, tries togivepriority to trainswith less remainingevents to leave the tracksassoonaspossible. Theexperimental resultsdemonstrate that this strategydoesnotworkwell comparedtootherdispatchingrules. The choice of dispatching rule does not affect the computational time, but the number of events in the re-scheduling timewindowand selected sub-networkhas a significant effect on the computational time since the size of the graphG increases quadratically. Figure 5 illustrates the increaseofcomputational timeagainst increaseof the timehorizonandnumberofevents. Boththe sizeofgraphGandthecomputational time increasequadratically. Figure5.Thecomputational time increasesquadratically,basedonthenumberofevents. 6.ConclusionsandFutureWork Thispaperaddresses thereal-timetrain trafficre-schedulingproblem.Amixedgraphisusedfor modeling theproblemasablocking job-shopschedulingproblem.Aheuristicalgorithmisproposed that benefits fromre-timing, re-ordering, and local re-routing. The algorithmbenefits also froma dynamicupdateofdata,whichaccelerates thecomputations. The response time for such a real-time computational scheduling tool is a vital factor. In the proposedsolutionapproach, theproblemfora1htimewindowissolvedin less than10s,andfora 1.5htimewindow, thecomputational timeis less than20s. It isalsounknownwhat timehorizonis necessarytoconsider indifferentsituationsandwhatrole thisuncertaintywouldplay. Interviewswith dispatcherssuggest that itdiffersalotdependingonthesituation,contextandassociatedworkingload. The TFD+3j objective function is a relevant criterion to control the lateness of trains. However, basedon the situationand typeofdisturbance scenario, thedispatchersalsohaveother concernsandobjectives. The investigationofotherobjective functionsanduseful solutionquality metrics is necessary to investigate in future research. ThegraphG is representedbyanadjacency matrix in thecurrent implementation.Usingalternativedatastructuressuchasadjacency lists, canbe anoptionto investigate thepossibility toreducecomputational timefurther. Acknowledgments:Thepresentedresearchworkwasconductedwithin theresearchprojectsFLOAT(FLexibel Omplanering Av Tåglägen i drift) and BLIXTEN (Beslutstöd för trafikLedare: approxImativa och eXakta opTimEraNdemetoder), fundedbytheSwedishTransportAdministration(Trafikverket)withtheKAJT(KApacitet i JärnvägsTrafiken) researchprogramme.Weare thankful for thefinancial support,data,andsignificantguidance providedbyTrafikverket. AuthorContributions:Omidhasdevelopedthegraphmodelandheuristicalgorithms. Thealgorithmicapproach hasbeen implementedinJavabyOmid. Johannahasprovidedall inputdatarequiredtobuildandperformthe experiments,andshe is themaindeveloperof thevisualizationtoolusedforvisual inspectionofre-scheduling solutions. Johannahas alsomanaged the associated researchproject, handled all contactswith the industry partner,Trafikverket,andacquiredtheassociatedresearchfunding.Omidhasgeneratedthedisturbancescenarios, performedtheexperimentswith thealgorithmicapproachandtheassociatedperformanceassessment including 110