Affectation de locomotives aux trains avec contraintes d'entretien et de carburant

In this thesis, we consider the problem of assigning locomotives to a large number of trains scheduled over a one-week or a one-month horizon while taking into account maintenance and, possibly, fueling constraints. Since the locomotives are all of the same type, demand for each train is expressed as a minimum number of locomotives. Maintenance and fueling constraints are given as minimum and maximum traveled distances between two consecutive maintenances or fuelings. Availability constraints for the locomotives and the maintenance shops must also be taken into account, as well as locomotive initial conditions. Locomotives can go to maintenance and fueling at all times without violating any constraints even if this requires traveling alight (with an engineer) or in deadhead (without engineer) pulled by one or several other locomotives. The objective consists of minimizing first the total number of locomotives used, second the total operational cost including the distance traveled in light moves and in deadhead, and last delayed maintenances with respect to the minimum distance between two maintenances. Despite similarities between this problem and those studied in the literature, the former requires a different approach because of the large number of trains to cover augmented by the large number of potential light moves, and also because of the constraints for different maintenance types and for fuel. Moreover, to treat the initial conditions of the locomotives, they roust be handled individually.; The problem is modeled by adapting the generic nonlinear multicommodity network flow model proposed in 1998 by Desaulniers, Desrosiers, Ioachim, Solomon and Soumis for tackling a large class of deterministic vehicle routing and crew scheduling problems. Each locomotive represents a commodity and is associated with a timespace network. Instead of developing a generic approach for all locomotive types, we develop a first approach for the problem of assigning electric locomotives and a second one for the problem of assigning diesel locomotives. These last locomotives need fueling about once per day and maintenance less frequently. The first approach works when short time maintenances like fueling is not considered. The second one is an extension of the first which includes a special treatment of the fueling constraints.; Given the size of the instances to solve for the electric locomotives, we propose a solution approach based on several decomposition strategies. Firstly, the planning horizon is discretized into overlapping time slices and a reasonable-sized problem is solved for each slice. Secondly, a small integer linear problem is solved to identify locomotives that need maintenance during the current time slice. These locomotives are said to be critical and the others non-critical. The routing of the critical locomotives is then performed sequentially by solving, for each of these locomotives, a shortest path problem with resource constraints. Finally, the non-critical locomotives are routed simultaneously by solving an integer linear problem. To improve solution quality, we propose two different modifications to this basic approach. The first corrects the greedy aspect of the critical locomotive routing procedure by reconsidering some parts of their routes in the time slice. The second uses the dual information obtained by solving a priori a relaxed version of the problem for better guiding the critical locomotives during their routing. Two other modificatons are also proposed for improving computational times. The first replaces the integer linear model for the non-critical locomotives by an equivalent network flow model. The second reduces the size of the underlying networks by efficiently selecting potential light moves.; When fueling is treated like maintenance, the first approach becomes almost totally greedy because almost all locomotives are critical for fueling in each time slice. To alleviate this difficulty, we propose...