Planning Drivers for Shunting Yards
Summary
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.