Optimisation simultanee des rotations et des blocs mensuels des equipages aeriens

The crew pairing problem has been traditionally solved in the industry by a heuristic three-phase approach that solves sequentially a daily, a weekly, and a monthly problem. This approach prohibits the repetition of the same flight number in a pairing. The first objective in this thesis is to highlight two weaknesses of the three-phase approach and propose an alternative solution approach that exploits flight number repetitions in pairings. First, when the flight schedule is irregular, we show that better quality solutions can be obtained in less computational times if the first two phases are skipped and the monthly problem is solved directly using a rolling horizon approach based on column generation. In fact, this approach has reduced the solution fat by 34%. The solution fat is a quality measure that shows the percentage of time not worked but paid. Second, even if the flight schedule is completely regular, we show that better quality solutions can be derived by skipping the daily problem phase and solving the weekly problem directly. Indeed, the proportion of pairings with such repetitions represents 48.8% causing a mean reduction in the solution fat by 16%.The main drawback of the integrated approach is its computing time which is much higher than the sequential approach. The third part of the thesis thus suggests refinements to reduce the computing time and improve, if possible, the quality of the solution. We propose a heuristic solution approach that consists of aggregating not only the master problem constraints but also the subproblem networks using variable neighborhoods. The use of neighborhoods increases the possibility of generating columns that can provoke a decrease in the objective function value during the column generation process. Each neighborhood is associated with a time slice and any promising group overlapping that time slice is selected. All selected groups are forced to remain aggregated for a number of iterations, while others may be disaggregated at any moment. Computational results showed that the proposed solution method can produce better quality solutions than the traditional sequential two-stage solution approach widely used in the industry. In fact, a mean reduction of 5.85% in the number of pilots has yielded promising savings in the total cost with an average of 4.76%. In addition, the computing time is greatly reduced from a factor of 6.8 to 3.8 in comparison with the sequential approach.In summary, this thesis presents mathematical programming methods to efficiently solve the crew pairing problem and the integrated crew scheduling problem. It highlights the weaknesses of the sequential methods traditionally used for these problems and clearly demonstrates the potential to attack these problems directly. (Abstract shortened by UMI.)In practice, both the crew pairing and crew assignment problems are independently modeled and sequentially solved. The use of a sequential approach considerably reduces the complexity of the global problem but produces solutions that may not be conform with airline desires. The second objective in this thesis is to propose a model that fully integrates the crew pairing and crew assignment problems and solve it in a single step. Due to the large size of this integrated model, we propose a solution method that combines a column generation and a dynamic constraint aggregation method. Since the latter method requires a good initial partition, this partition is provided by a set of pairings found with the sequential approach. A partition is a set of disjoint flight clusters, whose union is the set of all flights in the problem. A cluster is a sequence of flights. Compared to the sequential approach, all tests showed that the integrated approach can yield significant cost savings (on average, 5.54% less pilots yielding a 3.37% total cost reduction). They also showed that allowing pairing concatenation in the crew assignment phase of the sequential approach can improve the quality of the solutions produced, but it is far from sufficient to reach the solution quality achieved by the integrated approach.