Optimising the Scheduling of Train Unit Cleaning

Scheduling of Train Unit Cleaning is one of the planning processes required at DSB, The Danish Railway Company. In order to ensure an adequate service level to its customers, train cleaning must be planned as efficiently as possible. The presence of several decision variables and even more constraints requires the utilization of a tool to ensure the respect of all the requests while cost of operations is minimized. This thesis project proposes an optimisation model to solve the train cleaning scheduling problem. A mathematical formulation based on a space-time network describing the movement of the rolling stock is presented. A Label Setting Algorithm based on this network can solve to optimality the reduced scheduling problem associated with each train unit. In order to obtain a cleaning operation plan for all the train set, the Label Setting Algorithm generates it in a recursive way and a heuristic approach verifies the respect of further restrictions. The algorithm was tested on real instances from DSB. The main parameters of evaluation were the total time of execution of the cleaning operations and the service level provided. The Label Setting Algorithm with its flexibility has permitted us to implement different assumptions on parameters. In each of these situation the proposed model has generated good results in terms of cost minimization. The use of a greedy heuristic approach in a second stage has demonstrated to be the weakest part of the approach, on which future improvement can be considered.