Seite - 107 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 55 Figure4. Illustrationof thestudiedrailway lineKarlskrona-Kristianstad-Malmö. Source:Trafikverket. All disturbance scenarios occur between 16:00 and 18:00, which is during peak hours. The re-scheduling timehorizons are 1 and1.5 h timewindows, respectively, counting fromwhen the disturbanceoccurs. ThescenariosaredescribedinTable3below.Theexperimentswere testedona laptopwith64-bitWindows10,equippedwithanIntel i7-CPU,2.60GHz,with8GigabytesofRAM. Table 3. Description of the 30× 2 scenarios thatwere used in the experimental study. The first number in thescenario-IDspecifieswhichdisturbancecategory it is. Forcategory2, thedisturbance isapercentage increaseof theruntime,e.g., 40%.Thetworightmostcolumnsspecify thesizeof the problemexpressed inanumberof trainevents thatare tobere-scheduled. Scenario Disturbance ProblemSize: #Events1 Category: ID Location InitiallyDisturbedTrain InitiallyDelay(min) 1hTime Window 1.5hTime Window 1:1 Karlshamn-Ångsågsmossen 1058(Eastbound) 10 1753 2574 1:2 BromöllaSölvesborg 1064(Eastbound) 5 1717 2441 1:3 Kristianstad-Karpalund 1263(Southbound) 8 1421 2100 1:4 Bergåsa-Gullberna 1097 (Westbound) 10 1739 2482 1:5 BräkneHoby-Ronneby 1103(Westbound) 15 1393 2056 1:6 Flackarp-Hjärup 491(Southbound) 5 1467 2122 1:7 Eslöv-Dammstorp 533(Southbound) 10 1759 2578 1:8 Burlöv-Åkarp 544(Northbound) 7 1748 2572 1:9 Burlöv-Åkarp 1378(Northbound) 4 1421 2100 1:10 Höör-Stehag 1381(Southbound) 10 1687 2533 2:1 Karlshamn-Ångsågsmossen 1058(Eastbound) 40% 1753 2574 2:2 BromöllaSölvesborg 1064(Eastbound) 20% 1717 2441 2:3 Kristianstad-Karpalund 1263(Southbound) 20% 1421 2100 2:4 Bergåsa-Gullberna 1097 (Westbound) 40% 1739 2482 2:5 BräkneHoby-Ronneby 1103(Westbound) 100% 1393 2056 2:6 Flackarp-Hjärup 491(Southbound) 100% 1467 2122 2:7 Eslöv-Dammstorp 533(Southbound) 50% 1759 2578 2:8 Burlöv-Åkarp 544(Northbound) 80% 1748 2572 2:9 Burlöv-Åkarp 1378(Northbound) 40% 1421 2100 2:10 Höör-Stehag 1381(Southbound) 40% 1687 2533 3:1 Karlshamn-Ångsågsmossen All trainspassingthrough 4 1753 2574 3:2 BromöllaSölvesborg All trainspassingthrough 2 1717 2441 3:3 Kristianstad-Karpalund All trainspassingthrough 3 1421 2100 3:4 Bergåsa-Gullberna All trainspassingthrough 6 1739 2482 3:5 BräkneHoby-Ronneby All trainspassingthrough 5 1393 2056 3:6 Flackarp-Hjärup All trainspassingthrough 3 1467 2122 3:7 Eslöv-Dammstorp All trainspassingthrough 4 1759 2578 3:8 Burlöv-Åkarp All trainspassingthrough 2 1748 2572 3:9 Burlöv-Åkarp All trainspassingthrough 2 1421 2100 3:10 Höör-Stehag All trainspassingthrough 2 1687 2533 1 Thesizeof thegeneratedgraphG is thesquaredsizeofnumberofevents. 107