[Dept. of Computer Science]

Experimentation Project ACS


Title A smart greedy algorithm for shunting passenger trains
Student Vacancy
Supervisor Marjan van den Akker
ECTS 7.5
Related Course(s) Scheduling and Timetabling, Algorithms and Networks
Description The NS (Dutch Railways) takes care of the transport of passengers by train. When a train arrives at a station, it either continues unchanged, or one or more units (possibly the entire train) remain at the station;
if necessary it has to be moved to clear the track. The units remaining at the station are put at the so-called shunting-yard and later used for a departing train.
We have to match arriving and departing train units and to schedule the movements to realize this matching; this is called the shunting problem.
The goal is to find a feasible shunting that minimizes the number of shunt movements.

The purpose of this project is to develop a greedy heuristic including smart look-ahead rules and rules used by operational planners. The Dutch Railways NS have provided us with test data from Alkmaar station.

Special Note This was one of the problems studied by the `Study Group Mathematics with Industry'.