A Lagrangian heuristic for a train-unit assignment problem

We present a fast heuristic for an important NP-hard problem, arising in the planning of a railway passenger system, that calls for the definition of the train units to be assigned to a given set of timetabled trips, each with a given number of passenger seats requested. The heuristic is based on the Lagrangian relaxation of a natural formulation of the problem, whose solution can be found by solving a sequence of assignment problems. With respect to an already existing method, the heuristic we propose turns out to be much faster in practice and still providing solutions of good quality. This makes it suitable for all cases in which the problem either must be solved many times, e.g., when it is integrated with other phases of railway planning, or when it must be solved within short computing time, e.g., within real-time operations.