TY - JOUR
T1 - A Variable Neighborhood Search Heuristic for Rolling Stock Rescheduling
AU - Hoogervorst, Rowan
AU - Dollevoet, Twan
AU - Maroti, G
AU - Huisman, Dennis
N1 - Publisher Copyright:
© 2021 Association of European Operational Research Societies (EURO)
PY - 2021/3
Y1 - 2021/3
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85103089362&partnerID=8YFLogxK
U2 - 10.1016/j.ejtl.2021.100032
DO - 10.1016/j.ejtl.2021.100032
M3 - Article
VL - 10
JO - EURO Journal on Transportation and Logistics
JF - EURO Journal on Transportation and Logistics
SN - 2192-4376
M1 - 100032
ER -