Solving the Locomotive Assignment Problem for a European rail-passenger and rail-cargo company

This thesis considers a large real-life application of the Locomotive Assignment Problem. Due to the large size of the problem instance, many of the existing solution methods are unlikely to find a good quality solution within reason- able computation time. In this thesis, we define two different multi-commodity flow formulations, where the commodities correspond to locomotive types and consists, respectively. The formulation based on locomotive types provides the optimal solution, while the consist based formulation is unlikely to reach optimality. Next to the two formulations, two different heuristics are investigated. The first heuristic is a relax-and-fix heuristic, which aims to solve the locomotive based formulation iteratively by decomposing the set of arcs into subsets based on starting time. The second heuristic is a greedy heuristic extended with a local search heuristic. This approach schedules every activity such that the additional cost for this activity is minimized. Afterwards, the solution is improved by investigating neighbouring solutions. Especially the relax-and-fix heuristic is able to provide good quality results within reasonable computation time for the real size dataset.