Seite - 111 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 55 theanalysisof theresultingdataandconclusions. Johannahas formulatedandimplementedthecorresponding MIPformulation in java,whichwasapplied tosolve thesamedisturbancescenarios inorder toevaluate the level ofoptimalityandefficiencyof thealgorithmicapproach. Both JohannaandOmidcontributedsignificantly to writing themanuscript. Bothauthorshavereadandapprovedthefinalmanuscript. Conflictsof Interest:Theauthorsdeclarenoconflictof interest. AppendixA TheMIPformulation isbasedonthemodeldevelopedbyTörnquistandPersson[13]. Themodel was implemented in JavaandsolvedbyGurobi6.5.1. Let Jbethesetof trains,M thesetof segments, definingtherail infrastructure,andO thesetofevents.Aneventcanbeseenasa timeslot requestby a train foraspecificsegment. The index j isassociatedwithaspecific trainservice,andindexmwitha specific infrastructuresegment,and iwiththeevent.Anevent isconnectedbothtoan infrastructure segmentanda train. ThesetsOj⊆Oareorderedsetsof events foreach train j,whileOm⊆Oare orderedsetsofevents foreachsegmentm. Eacheventhasapointoforigin,mj,i,which isused fordeterminingachange in thedirection of trafficonaspecific track. Further, foreachevent, there isascheduledstart timeandanendtime, denotedbybinitalj,i ande inital j,i ,whicharegivenbytheinitial timetable. Thedisturbanceismodelledusing parametersbstaticj,i and e static j,i ,denotingthepre-assignedstartandendtimeof thealreadyactiveevent. Therearetwotypesofsegments,modelingtheinfrastructurebetweenstationsandwithinstations. Eachsegmentmhasanumberofparallel tracks, indicatedbythesetsMm andeachtrackrequiresa separation in timebetweenitsevents (one train leavingthe trackandthenextenters thesametrack). Theminimumtimeseparationbetweentrainsonasegment isdenotedbyΔMeetingm for trains that travel inoppositedirections,andΔFollowingm for trains that followeachother; theseparation isonlyrequired if the trainsuse thesametrackonthatspecificsegment. Theparameter psj,i indicates if event i includesaplannedstopat theassociatedsegment (i.e., it is thennormallyastation). Theparameterdj,i represents theminimumrunningtime,pre-computed fromthe initial schedule, if event ioccursona linesegmentbetweenstations. Forstationsegments,dj,i corresponds to theminimumdwell timeofcommercial stops,where transfersmaybescheduled. Thevariables in themodelareeitherbinaryorcontinuous. Thecontinuousvariablesdescribe the timingof theeventsandthedelay,andthebinaryvariablesdescribe thediscretedecisions to takeon themodelconcerningtheselectionofa trackonsegmentswithmultiple tracksorplatforms,andthe orderof trains thatwant tooccupythesametrackand/orplatform. Thecontinuous,non-negative, variablesarexbeginj,i ,x end j,i , and zj,i (delayof theevent i, i∈O, exceedingμ timeunits,which is set to threeminuteshere). Thevariablesxendj,i andx begin j,i aremodelling theresourceallocation,wherearesource isaspecific tracksegment. Thearrival timeataspecificsegment isgivenbyxbeginj,i anddeparture fromaspecific segment isgivenbyxendj,i foraspecific train. Thebinaryvariablesaredefinedas: qj,i,u= { 1,if event iuses tracku, i∈Om,u∈Mm,m∈M, j∈ J 0,otherwise γj,i,j′,i′= { 1,if event ioccursbeforeevent i′, i∈Om,m∈M : i< i′, j and j′ ∈ J 0,otherwise λj,i,j′,i′= { 1,if event i is rescheduledtooccurafterevent i′, i∈Om,m∈M : i< i′, j and j′ ∈ J 0,otherwise 111