A Variable Neighborhood Search heuristic for rolling stock rescheduling
We present a Variable Neighborhood Search heuristic for the rolling stock rescheduling problem. Rolling stock rescheduling is needed when a disruption leads to cancellations in the timetable. In rolling stock rescheduling, one must then assign duties, i.e., sequences of trips, to the available train...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2021-01-01
|
| Series: | EURO Journal on Transportation and Logistics |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2192437621000042 |
| _version_ | 1818149836341379072 |
|---|---|
| author | Rowan Hoogervorst Twan Dollevoet Gábor Maróti Dennis Huisman |
| author_facet | Rowan Hoogervorst Twan Dollevoet Gábor Maróti Dennis Huisman |
| author_sort | Rowan Hoogervorst |
| collection | DOAJ |
| description | We present a Variable Neighborhood Search heuristic for the rolling stock rescheduling problem. Rolling stock rescheduling is needed when a disruption leads to cancellations in the timetable. In rolling stock rescheduling, one must then assign duties, i.e., sequences of trips, to the available train units in such a way that both passenger comfort and operational performance are taken into account. For our heuristic, we introduce three neighborhoods, which focus on swapping duties between train units, on improving the individual duties and on changing the shunting that occurs between trips, respectively. These neighborhoods are used for both a Variable Neighborhood Descent local search procedure and for perturbing the current solution in order to escape from local optima. Moreover, we show that the heuristic can be extended to the setting of flexible rolling stock turnings at ending stations by introducing a fourth neighborhood. We apply our heuristic to instances of Netherlands Railways (NS). The results show that the heuristic is able to find high-quality solutions within 1 min of solving time. This allows rolling stock dispatchers to use our heuristic in real-time rescheduling. |
| first_indexed | 2024-12-11T13:13:22Z |
| format | Article |
| id | doaj.art-cf8c3cfda6cc40f5af6df1301975912e |
| institution | Directory Open Access Journal |
| issn | 2192-4384 |
| language | English |
| last_indexed | 2024-12-11T13:13:22Z |
| publishDate | 2021-01-01 |
| publisher | Elsevier |
| record_format | Article |
| series | EURO Journal on Transportation and Logistics |
| spelling | doaj.art-cf8c3cfda6cc40f5af6df1301975912e2022-12-22T01:06:07ZengElsevierEURO Journal on Transportation and Logistics2192-43842021-01-0110100032A Variable Neighborhood Search heuristic for rolling stock reschedulingRowan Hoogervorst0Twan Dollevoet1Gábor Maróti2Dennis Huisman3Econometric Institute and ECOPT, Erasmus University Rotterdam, 3000 DR, Rotterdam, the Netherlands; Corresponding author.Econometric Institute and ECOPT, Erasmus University Rotterdam, 3000 DR, Rotterdam, the NetherlandsSchool of Business and Economics, VU University Amsterdam, 1081 HV, Amsterdam, the Netherlands; Process quality and Innovation, Netherlands Railways, 3500 HA, Utrecht, the NetherlandsEconometric Institute and ECOPT, Erasmus University Rotterdam, 3000 DR, Rotterdam, the Netherlands; Process quality and Innovation, Netherlands Railways, 3500 HA, Utrecht, the NetherlandsWe present a Variable Neighborhood Search heuristic for the rolling stock rescheduling problem. Rolling stock rescheduling is needed when a disruption leads to cancellations in the timetable. In rolling stock rescheduling, one must then assign duties, i.e., sequences of trips, to the available train units in such a way that both passenger comfort and operational performance are taken into account. For our heuristic, we introduce three neighborhoods, which focus on swapping duties between train units, on improving the individual duties and on changing the shunting that occurs between trips, respectively. These neighborhoods are used for both a Variable Neighborhood Descent local search procedure and for perturbing the current solution in order to escape from local optima. Moreover, we show that the heuristic can be extended to the setting of flexible rolling stock turnings at ending stations by introducing a fourth neighborhood. We apply our heuristic to instances of Netherlands Railways (NS). The results show that the heuristic is able to find high-quality solutions within 1 min of solving time. This allows rolling stock dispatchers to use our heuristic in real-time rescheduling.http://www.sciencedirect.com/science/article/pii/S2192437621000042Disruption managementRolling stock reschedulingVariable neighborhood search |
| spellingShingle | Rowan Hoogervorst Twan Dollevoet Gábor Maróti Dennis Huisman A Variable Neighborhood Search heuristic for rolling stock rescheduling EURO Journal on Transportation and Logistics Disruption management Rolling stock rescheduling Variable neighborhood search |
| title | A Variable Neighborhood Search heuristic for rolling stock rescheduling |
| title_full | A Variable Neighborhood Search heuristic for rolling stock rescheduling |
| title_fullStr | A Variable Neighborhood Search heuristic for rolling stock rescheduling |
| title_full_unstemmed | A Variable Neighborhood Search heuristic for rolling stock rescheduling |
| title_short | A Variable Neighborhood Search heuristic for rolling stock rescheduling |
| title_sort | variable neighborhood search heuristic for rolling stock rescheduling |
| topic | Disruption management Rolling stock rescheduling Variable neighborhood search |
| url | http://www.sciencedirect.com/science/article/pii/S2192437621000042 |
| work_keys_str_mv | AT rowanhoogervorst avariableneighborhoodsearchheuristicforrollingstockrescheduling AT twandollevoet avariableneighborhoodsearchheuristicforrollingstockrescheduling AT gabormaroti avariableneighborhoodsearchheuristicforrollingstockrescheduling AT dennishuisman avariableneighborhoodsearchheuristicforrollingstockrescheduling AT rowanhoogervorst variableneighborhoodsearchheuristicforrollingstockrescheduling AT twandollevoet variableneighborhoodsearchheuristicforrollingstockrescheduling AT gabormaroti variableneighborhoodsearchheuristicforrollingstockrescheduling AT dennishuisman variableneighborhoodsearchheuristicforrollingstockrescheduling |