The Duty Allocation Problem at Netherlands Railways

This thesis describes a tabu-search meta-heuristic that is developed and applied to solve the railway duties assignment problem. The problem is part of the rostering process to create rosters for the crew members (train drivers and conductors) of Netherlands Railways (NS). We are given a set of duties and a set of roster groups for a certain crew base. The goal is to assign these duties to the roster groups such that the popular and unpopular is divided as fairly as possible among the different groups. In addition, several labor rules are satisfied. To come up with a good tabu search heuristic, we have tested several parameters in the tabu-search. On three real-world data instances from NS. The results are also compared with the solutions obtained by solving an integer program solver with a commercial solver. The tabu search gives solutions of a reasonable quality in acceptable computation times.