Affectation des types d'avions aux vols avec contraintes de maintenance

The interaction between the fleet assignment problem and the aircraft routing problem is studied in this thesis. Given a weekly schedule, the fleet assignment problem assigns an aircraft type - a fleet - to each flight. This assignment must not exceed the number of aircraft available, must respect the flow conservation constraints and aims to maximize the anticipated profits.;During tactical planning, realized six months to one year before the day of operations, the aircraft routing problem is solved to evaluate the feasibility of the fleet assignment. In addition, the aircraft routes are used to solve the crew scheduling problem. The weekly aircraft routing problem is, in general, considered as a cyclic problem in order to be able to reproduce the solution obtained each week of the considered season. For some aircraft type, it is difficult to build feasible aircraft routes because of the conflicting obligations to cover every flight assigned to the aircraft type and to visit a maintenance station at a prescribed frequency.;The work of this thesis aims at integrating maintenance planning in the fleet assignment problem. To achieve this goal, two parts are presented. The first part proposes a multicommodity model for solving the aircraft routing problem. This model is solved by the commercial solver Cplex and builds aircraft routes that respect the maintenance constraints. When it is impossible to do all the required maintenance checks, the model identifies aircraft routes that cover all flights and provides the number of delays on the maintenances.;The second part of this work is devoted to the integration of maintenance constraints in models for the fleet assignment problem. First, using a multicommodity model generally used for this problem, we propose the addition of maintenance constraints that provide a better maintenance management. The additional constraints are of two types. The first type of constraints are generated a priori. The addition of these constraints helps to make a better maintenance planning but they are not sufficient to avoid delays. The second type of constraints is generated as needed in a cutting plane method. The separation algorithm for these constraints uses a column generation algorithm applied to a problem separable by aircraft type.;Once the fleet assignment is known, the aircraft routing problem is solved for each aircraft type. An aircraft route is a sequence of flight legs, connections and waiting periods. Moreover, an aircraft route must contain a maintenance check at a prescribed frequency. In this thesis, the aircraft routing problem is studied on a weekly horizon. Typically, only the type A maintenances that must be performed, in general, each three or four days are considered when solving the aircraft routing problem. Each aircraft must visit a maintenance station at most at every three or four days and stay at the station enough time to perform the maintenance works.;In the literature, a set partitioning model is generally used for the combined problem of the fleet assignment and the aircraft routing problem. Presented by BARNHART ET AL. (1998a), this model is solved using a column generation algorithm included in a branch-and-bound method. This methodology has recently been accelerated by a dynamic constraint aggregation procedure in a different context. Therefore, we tried to apply this procedure for the combined problem. The results are not as good as we expected; the computational time has been reduced of 25% to 50% but the quality of the solutions has also been reduced (less than 0.1%). We provide some reasons that can explain these results.;Finally, recent works on the business process leading to the definition of the aircraft routing problem have brought us to think more about this problem. Until recently, the stochastic aspect of this problem was ignored even if it is obvious that the probability that a planned route will be performed as planned greatly reduces with the length of the route. Thus, some airlines have reviewed their business process in order to plan the aircraft routes differently. This is why we propose a classification of the literature according to three business processes driving the aircraft routing problem. We then compare these processes according to different aspects: solution costs, solution robustness, etc.;In summary, this thesis proposes a new model for the aircraft routing problem, two new solution approaches to solve the combined fleet assignment and the aircraft routing problem and, finally, a classification of the literature on the aircraft routing problem.