Seite - 112 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 55 With theobjective tominimize thesumofalldelays forall trainsreachingtheirfinaldestination withadelay larger thanthreeminutes, theobjective functioncanbeformulatedas follows,where the parameternj foreachtrain j∈ Jholds thefinaleventof train j : min z f :=∑ j∈J znj (A1) Wealsohave the following threeblocksof constraints. Thefirst block concerns the timingof the events belonging to each train j and its sequence of events, definedby the event listOj ⊆O. Theseconstraintsdefinetherelationbetweenthe initial scheduleandrevisedschedule,asaneffect of thedisturbance. Equation(A7) isusedtocompute thedelayofeacheventexceedingμ timeunits, whereμ is set to threeminutes in thiscontext. xendj,i = x begin j,i+1, i∈Oj, j∈ J : i =nj, j∈ J (A2) xbeginj,i = b static j,i , i∈O : bstaticj,i >0, j∈ J (A3) xendj,i = e static j,i , i∈O : estaticj,i >0, j∈ J (A4) xendj,i ≥ xbeginj,i +dj,i, i∈O, j∈ J (A5) xbeginj,i ≥ binitialj,i , i∈O : psj,i=1, j∈ J (A6) xendj,i −einitialj,i −u≤ zj,i, i∈O, j∈ J (A7) In the following part, N is a large constant. The second block of constraints concerns the permitted interactionbetweentrains,giventhecapacity limitationsof the infrastructure (including safetyrestrictions): ∑ u∈Mm qj,i,u=1, i∈Om,m∈M, j∈ J (A8) qj,i,u+qj′,i′,u−1≤λj,i,j′,i′+γj,i,j′,i′, i, i′ ∈Om,u∈Mm,m∈M : i< i′, j = j′ ∈ J (A9) xbeginj′,i′ −xendj,i ≥Δ Meeting m γj,i,j′,i′ −N ( 1−γj,i,j′,i′ ) , i, i′ ∈Om,m∈M : i< i′,mi′ =mi, j = j′ ∈ J (A10) xbeginj′,i′ −xendj,i ≥Δ Following m γj,i,j′,i′ −N ( 1−γj,i,j′,i′ ) , i, i′ ∈Om,m∈M : i< i′,mi′ =mi j = j′ ∈ J (A11) xbeginj,i −xendj′,i′ ≥Δ Meeting m λj,i,j′,i′ −N ( 1−λj,i,j′,i′ ) , i, i′ ∈Om,m∈M : i< i′,mi′ =mi j = j′ ∈ J (A12) xbeginj,i −xendj′,i′ ≥Δ Following m λj,i,j′,i′−N ( 1−λj,i,j′,i′ ) , i, i′ ∈Om,m∈M : i< i′,mi′ =mi, j = j′ ∈ J (A13) λj,i,j′,i′+γi,i′ ≤1, i, i′ ∈Om,m∈M : i< i′, j = j′ ∈ J (A14) xbeginj,i ,x end j,i ,zj,i≥0, i∈O, j∈ J (A15) γj,i,j′,i′,λj,i,j′,i′ ∈ {0,1}, i′ ∈Om, i∈M : i< i′, j = j′ ∈ J (A16) qj,i,u∈{0,1}, i∈Om,u∈Mm,m∈M, j∈ J (A17) References 1. BostonConsultancyGroup.The2017EuropeanRailwayPerformance Index;BostonConsultancyGroup:Boston, MA,USA,18April2017. 2. EuropeanCommissionDirectorateGeneral forMobilityandTransport.Studyon thePrices andQualityofRail PassengerServices;ReportReference:MOVE/B2/2015-126;EuropeanCommissionDirectorateGeneral for MobilityandTransport: Brussel,Belgium,April2016. 112