Affectation des locomotives et des wagons aux trains de passagers

This dissertation addresses the problem of assigning locomotives and cars to trains in the special context of passenger transportation. Given a train schedule and a set of available equipment units, the problem is to provide each train with a sufficient number of compatible locomotives and cars while satisfying supplementary constraints pertaining to train operations and rolling stock characteristics. Despite the similarities between this problem and that of assigning engines to freight trains, the former requires a different approach because of the nature of the interactions that exist between the different types of equipment.; To solve the locomotive and car assignment problem, we propose a number of different approaches based on multi-commodity network flow models with additional constraints and variables. In these models, the flow represents units of equipment or groups of units that are used together on the same train. Because the assignment of the different types of equipment cannot be made individually and independently, the role of the additional variables and constraints is to reflect the numerous interactions that link the locomotives and cars assigned to each train. An important portion of the dissertation is devoted to the development of decomposition approaches that facilitate the efficient treatment of these interactions.; We propose three approaches for solving this problem. The first approach is based on a very complete model including a large array of possibilities and constraints that are necessary in a practical application. This model was developed according to the specific needs of a Canadian railway but can however be customized to deal with various situations. Besides maintenance constraints and substitution possibilities between equipment types, the formulation incorporates penalties for switching cars during a connection between two successive train services.; We next present an alternative model that is simpler but possesses a very flexible structure. This model addresses the fundamental difficulties of the problem that arise when combining equipment units of different types, but does not incorporate more complex features such as maintenance constraints or substitution possibilities. The formulation differs from the previous one and is well suited for a variable decomposition approach. We thus propose a solution approach based on Benders decomposition which, with the help of some refinements that yield a significant speed improvement in the algorithm, turns out to be quite effective.; The last part of the dissertation presents extensions to the simplified model that make it more appropriate for real-life applications. We thus describe an extended formulation incorporating maintenance constraints, substitution possibilities and penalties for car switching. Maintenance constraints are introduced by replacing the network flow problem for each type of equipment by a multi-commodity network flow problem. In addition, the generation of Pareto-optimal cuts produces a considerable speed improvement when solving certain instances. To solve larger instances, the multi-commodity network flow models are solved with a Dantzig-Wolfe decomposition. This last approach thus combines Benders decomposition and Dantzig-Wolfe decomposition within a branch-and-bound method. (Abstract shortened by UMI.)...