Multi-objective Approaches to the Unit Crewing Problem in Airline Crew Scheduling

摘要

The goal of the crew pairing problem is to partition a flight schedule into sequences of flights called pairings that crew members can operate at minimum cost. It is solved for each crew rank, for example, captains and first officers. In optimised crew pairings, crew often split and join other crew to operate outgoing flights. Because minimum cost pairings contain little buffer time, crew splitting after a delayed flight contributes to the propagation of delay. This effect can be avoided by unit crewing, that is, by keeping crew of different ranks together for as long as possible during a pairing. However, increasing unit crewing increases cost. We investigate sequential and parallel methods for unit crewing, explicitly considering the two objectives of minimising cost and maximising unit crewing. We apply multi-objective techniques in the sequential approach, where the (minimum cost) pairing problem for one crew rank is solved first and both objectives feature when solving for the second crew rank. Because the quality of the pairings obtained by this method is limited by the solution for the first crew rank, we then propose to solve the two crew pairing problems simultaneously, again using multi-objective optimisation methods. We introduce a multi-objective optimisation model for this problem and propose a new heuristic branching technique that favours unit crewed pairings when applied to a scalarised model with an auxiliary objective function. We compare this with a direct approach with management of the number of unit crewing constraints and a Dantzig-Wolfe decomposition approach. Numerical tests on domestic New Zealand data show that the multi-objective approaches considerably increase the level of unit crewing, without much increase in cost, even in the sequential approach. Moreover, we show that the parallel approach is superior in terms of quality of the pairing solution but computationally more expensive. The heuristic branching technique provides good quality solutions in reasonable time, as compared with the Dantzig-Wolfe method.