Seite - 106 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 55 Theproposedstarting timewithconsiderationofheadwaydistancewill changeto: xbeginj′,i′ = ⎧⎪⎨⎪⎩ Max(binitialj′,i′ ,x end j′,i′−1, maxj∈O′m,u ( xendj,i +cm,x begin j,i +hs ) ) if i′−1wasacommercial stop. Max(xendj′,i′−1, maxj∈O′m,u ( xendj,i +cm,x begin j,i +hs ) ) if i′−1wasnotacommercial stop. (5) Arecursive function isused in theupdateData function,whichupdates the release time forall operations thatare reachableby theoperation oj′,i′until od. Therecursive functionstopswhenever the xbeginj′,i′ value does not change. By viewing the headway distance in the updateData function (Equation(5)), it ispossible to ignore theextraarc for theheadwaydistance (seeFigure3).Deletionof thisextraarc,whichwasneededforconsideringtheheadwaytimedistance,alsohelps toreduce the computational time. Beforeaddinganewarc, thealgorithmapplies the solution feasibility function. If, byadding anewarc, a circuit appears in thegraphG, thegenerated solution is not feasible. Acircuit in the graphisasignof infeasible resourceallocation.Acircuit isachainof twoormoreoperations thatare trying toexchange themachineswith thenextoperations (swappingcondition). Toavoidacircuit, the following lemmaisused: Lemma1. Inadirectedacyclicgraph G,byaddinganarc fromvertex a tob, a circuit appears if andonly if a is reachable fromvertexb in thegraph G. If thereachability test confirmsacircuit, thealgorithmconsiders theoppositepriorityandapplies the arc related to theopposite alternative approach (re-ordering). Mostly, by adding theopposite alternativearc,nocircuitappears,but inrarecaseswhenthealgorithmgeneratesanewcircuit, the solutionwouldberejected. 5. ExperimentalApplicationandPerformanceAssessment 5.1. ExperimentalSet-Up For theexperimentalevaluation, theapproachwasapplied toanumberofdisturbancescenarios occurringwithinaselectedsub-network in thesouthofSweden,namely therailwaystretchbetween Karlskronacity toMalmö,viaKristianstadandHässleholm(seeFigure4,below). FromKarlskronato Hässleholm, therailwayline is single-track,andfromHässleholmtoMalmö, the line isdouble-track with a small portion having four tracks between Arlöv and Malmö. This stretch consists of approximately90 segments,witha total of 290block sections. For the regional trains that operate betweenKarlskrona andMalmö (and even further, intoDenmark via theÖresundBridge), there is a travel timeof1hand31minbetweenKarlskronaandKristianstad, anda travel timebetween KristianstadandMalmöof1hand5min. In linewith thecategorizationsuggested in [29], three typesofdisturbancescenariosareused: • Category1 refers to a train suffering froma temporarydelayat oneparticular section,which couldoccurdueto,e.g.,delayedtrainstaff,orcrowdingatplatformsresulting in increasingdwell timesat stations. • Category2refers toa trainhavingapermanentmalfunction, resulting in increasedrunningtimes onall linesections it isplannedtooccupy. • Category 3 refers to an infrastructure failure causing, e.g., a speed reduction on aparticular section,whichresults in increasedrunningtimes forall trainsrunningthroughthatsection. 106