Planning Drivers for Shunting Yards

Abstract

Throughout the day, trains are parked on shunting yards operated by the NS. While at the shunting yards, trains undergo many jobs such as riding, combining and splitting. These jobs then need to be executed by drivers for which a planning needs to be made. These tasks come with strict starting times or flexible time windows, considering factors like preferred starting times. The necessity for drivers to travel between jobs is addressed by allowing walking or riding along with a train, introducing considerations for minimizing travel time. Some particular pairs of jobs require synchronization and need to be planned to start at the same time. Additionally, buffers are preferred to mitigate delays, particularly for consecutively performed tasks that do not involve the same train. The NS’s current scheduling method, involving heuristics and an Integer Linear Program (ILP), has become too slow. To tackle these issues, we propose a crew scheduling solution using a branch-and-price algorithm that branches on time windows. The branch-and-price algorithm uses Dynamic Programming in a novel way to solve the pricing problem. The proposed algorithm is tested on real-life instances from NS’s shunting yards, solving smaller instances faster while finding a better solution. However, for larger instances, the current scheduling method shows better results.