Maintenance routing for train units: the transition model

Train units need regular preventive maintenance. Given the train units that require maintenance in the forthcoming 1-3 days, the rolling stock schedule must be adjusted so that these urgent units reach the maintenance facility in time. In an earlier paper Maroti and Kroon propose a model that requires a large amount of input data. In this paper we describe a less involved multicommodity flow type model for this maintenance routing problem. We study the complexity of the problem. It turns out that the feasibility problem for a single urgent train unit is polynomially solvable but the optimisation version is NP-hard. Finally, we report our computational experiments on practical instances of NS Reizigers, the main Dutch operator of passenger trains