An Effective Peak Period Heuristic for Railway Rolling Stock Planning

In this work we tackle a real-world application of railway rolling stock planning, known as the train unit assignment problem (TUAP), arising for a regional train operator in the North of Italy. Given a set of timetabled train trips, each with a demand of passenger seats, as well as a set of train units, each with a cost and a number of available passenger seats, the goal is to determine the minimum cost daily assignment of the train units to the trips, satisfying a set of operational constraints. The context we focus on is that of a competitive bid process whereby a train operator competes to win a contract for providing rolling stock circulation in a regional railway network. From a theoretical perspective, we prove that even a relaxation of the TUAP is NP-hard. To solve the TUAP, we propose a heuristic algorithm based on the optimal solution of the restricted problem associated with a peak period (i.e., a period of the day in which many trips overlapping in time must be performed). The heuristic algorithm is tested on real-world instances provided by the regional train operator and on larger realistic instances of TUAP. The obtained results are compared with those of previously developed methods, showing the effectiveness of the new algorithm that finds optimal or near-optimal solutions and outperforms, for what concerns both the solution quality and the computing time, the considered methods from the literature.