Page - 111 - in Algorithms for Scheduling Problems
Image of the Page - 111 -
Text of the Page - 111 -
Algorithms 2018,11, 55
theanalysisof theresultingdataandconclusions. Johannahas formulatedandimplementedthecorresponding
MIPformulation in java,whichwasapplied tosolve thesamedisturbancescenarios inorder toevaluate the level
ofoptimalityandefļ¬ciencyof thealgorithmicapproach. Both JohannaandOmidcontributedsigniļ¬cantly to
writing themanuscript. Bothauthorshavereadandapprovedtheļ¬nalmanuscript.
Conļ¬ictsof Interest:Theauthorsdeclarenoconļ¬ictof interest.
AppendixA
TheMIPformulation isbasedonthemodeldevelopedbyTƶrnquistandPersson[13]. Themodel
was implemented in JavaandsolvedbyGurobi6.5.1. Let Jbethesetof trains,M thesetof segments,
deļ¬ningtherail infrastructure,andO thesetofevents.Aneventcanbeseenasa timeslot requestby
a train foraspeciļ¬csegment. The index j isassociatedwithaspeciļ¬c trainservice,andindexmwitha
speciļ¬c 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 trafļ¬conaspeciļ¬c 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 thesametrackonthatspeciļ¬csegment.
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 isaspeciļ¬c
tracksegment. Thearrival timeataspeciļ¬csegment isgivenbyxbeginj,i anddeparture fromaspeciļ¬c
segment isgivenbyxendj,i foraspeciļ¬c train. Thebinaryvariablesaredeļ¬nedas:
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
back to the
book Algorithms for Scheduling Problems"
Algorithms for Scheduling Problems
- Title
- Algorithms for Scheduling Problems
- Authors
- Frank Werner
- Larysa Burtseva
- Yuri Sotskov
- Editor
- MDPI
- Location
- Basel
- Date
- 2018
- Language
- English
- License
- CC BY 4.0
- ISBN
- 978-3-03897-120-7
- Size
- 17.0 x 24.4 cm
- Pages
- 212
- Keywords
- Scheduling Problems in Logistics, Transport, Timetabling, Sports, Healthcare, Engineering, Energy Management
- Categories
- Informatik
- Technik