Reducing the number of shunt movements by rescheduling trains

In the off-peak hours, rolling stock is put on shunting yards. Since the number of used trains increases and the size of the shunting yards remains the same, it becomes harder and harder to find a feasible schedule for the shunting yards. The Dutch Railways (NS) is developing a software package that is capable of finding feasible schedules, but these often contain a high number of shunt movements, which is undesirable. In this paper, we propose a method that can reduce the number of shunt movements in existing feasible schedules by repeatedly rescheduling trains. We repeatedly reschedule one train at a time using the observation that finding a new schedule is equivalent to finding where and when a train will park. We build a model that allows us to find feasible parking locations and time intervals while taking into account the length of the tracks. By carefully looking at the position of the trains on the track, we are also able to avoid a special type of movement, called move-up movements. We apply a variant of a shortest path with time windows algorithm on this model, resulting in a schedule with the smallest number of movements for the rescheduled train. We then extend this approach to reschedule two trains simultaneously. We conclude with experiments on real-world data and a description of other possible use cases for the developed algorithm.