Seite - 109 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 55 Table5.Cont. Scenario TFD+3j ObjectiveFunction ComputationalTime Category: ID Optimal Results DispatchingRules (DR) MIPModel Heuristic Algorithm1 2 3 4 5 6 2:7 0:05:27 00:08:09 00:08:09 00:08:09 00:08:09 00:08:09 00:09:43 00:00:11 00:00:17 2:8 0:21:12 00:44:42 00:48:13 00:48:13 00:44:54 00:44:54 01:08:14 00:00:36 00:00:17 2:9 0:00:00 00:00:00 00:00:00 00:00:00 00:00:13 00:00:13 00:00:00 00:00:07 00:00:10 2:10 0:00:08 00:05:09 00:05:09 00:05:09 00:05:09 00:05:09 00:06:43 00:00:12 00:00:16 3:1 0:00:00 00:00:00 00:22:42 00:00:00 00:00:00 00:00:00 00:46:56 00:00:12 00:00:17 3:2 0:00:00 00:00:17 00:00:17 00:00:17 00:00:36 00:00:36 01:36:46 00:00:11 00:00:14 3:3 0:01:16 00:09:36 00:57:38 01:22:08 00:07:17 00:14:39 02:07:54 00:00:11 00:00:10 3:4 0:16:37 00:31:06 00:32:34 00:32:34 00:23:26 00:23:26 01:10:03 00:00:35 00:00:15 3:5 0:04:44 00:04:58 00:55:43 00:13:08 00:10:16 00:10:16 00:19:59 00:00:10 00:00:09 3:6 0:00:00 00:50:13 00:50:13 00:50:13 00:27:54 00:27:54 01:07:29 00:00:17 00:00:15 3:7 0:00:41 00:06:48 00:15:45 00:15:45 00:15:45 00:15:45 00:17:19 00:00:18 00:00:19 3:8 0:00:00 00:00:00 00:01:22 00:01:22 00:00:00 00:00:00 00:03:58 00:00:11 00:00:17 3:9 0:00:00 00:02:06 00:03:32 00:02:48 00:02:06 00:02:06 00:02:06 00:00:14 00:00:10 3:10 0:00:00 00:08:07 00:08:31 00:07:13 00:01:28 00:01:28 00:03:02 00:00:11 00:00:16 Theminimumrelease timegoesfirst (DR-1)was thebestdispatchingrule, considering the∑TFD+3j objective function. Theaverage∑TFD+3j for theMIPmodelwas259s for the1htimewindowand 332s for the1.5h timewindow. Theaverage∑TFD+3j for theminimumrelease timegoesfirst (DR-1) was597and849s, respectively. Statisticalanalysesof theresultsbelongingtodisturbancescenario type1revealedthat the less real buffer timegoesfirst (DR-3)dispatchingrule,withanaveragedelayof361s fora1htimewindow and314s fora1.5h timewindow,worksbetter than theotherdispatching rules. Additionally, an inefficientsolution isnotable toabsorbthedelays (i.e., thedelaysaftera temporaryrouteblocking mayremain in thesystemuntilmidnight). Theanalysisalsoshowsthat foralldispatchingrules in scenario1, the∑TFD+3j objective functionvaluesof the1.5h timewindoware lower thanthevalues forthe1htimewindow,whichconfirmsthat thealgorithmsuccessfullyattemptstomakethetimetable absorbdelayswhenpossible. Forscenario type2, theminimumrelease timegoesfirst (DR-1), lessprogrammedbuffer timegoesfirst (DR-4),and less total buffer goesfirst (DR-5)workedsomewhat the same, andbetter than theothers. Theaverage∑TFD+3j objectiveswere1056,953,and953s fora1htimewindow,and1547,1581,and 1581 for a 1.5h timewindow. Theoptimalvalues are 568 s for a 1h timewindowand796 s for a 1.5h timewindow. Inscenario type3, theminimumrelease timegoesfirstworkedbetter thantheothers withanaverageof365sdelay,but fora1.5h timewindowthe less total buffergoesfirst (DR-5)withan averageof532swas thebest. Theoptimalvalueswere113and139s, respectively. Withthehelpofavisualizationsoftware, theresulting, revisedtimetablescanbeanalysedbeyond aggregatednumbers. Themore delay goes first (DR-2) dispatching rule gives priority to the trains with the largest tardiness.Weobserved in thevisualizationof thesolutions that,when theconflict isbetween twotardy trains, this strategyworkswell andreduces thedelay.However, for conflicts betweenanon-timetrainandatardytrain, thisdispatchingrulegivespriority tothetardytrain,which causesadelay foranon-timetrain. Inotherwords,whenthe tardytrainreaches thedestination,e.g., KarlskronaorMalmö, this strategycausesadelayfornewtrains thathaverecentlystartedthe journey. Amoreeffectivedecisionwouldpotentiallybe toprioritize theon-timetrain,because the late train is near to itsfinaldestination. The less real buffer time goes first (DR-3) dispatching rule, gives priority to the trainwith least buffer time. Thisstrategyhelps thealgorithmtoreduce thedelay for tardytrains.Whentheconflict is betweentwotardytrains, thispolicy is fair. The lessprogrammedbuffer timegoesfirst (DR-5)considers the sumofbuffer time fora train to itsdestination. Inadisturbancearea, this strategyworkswell. The algorithmgivespriority to a trainwith less programmedbuffer time,which seems to be fair between two tardy trains. However,when a tardy train has a conflictwith anon-time train, this dispatching rulegivespriority to the tardyone,which isnot effective if theon-time train is at the 109