Simultaneous assignment of locomotives and cars to passenger trains

The problem of assigning locomotives and cars to trains is a complex task for most railways. In this paper, we propose a multicommodity network flow-based model for assigning locomotives and cars to trains in the context of passenger transportation. The model has a convenient structure that facilitates the introduction of maintenance constraints, car switching penalties, and substitution possibilities. The large integer programming formulation is solved by a branch-and-bound method that relaxes some of the integrality constraints. At each node of the tree, a mixed-integer problem is solved by a Benders decomposition approach in which the LP relaxations of multicommodity network flow problems are optimized either by the simplex algorithm or by Dantzig–Wolfe decomposition. Some computational refinements, such as the generation of Pareto-optimal cuts, are proposed to improve the performance of the algorithm. Computational experiments performed on two sets of data from a railroad show that the approach can be used to produce optimal solutions to complex problems.