TY - JOUR

T1 - Multi-objective approaches to the unit crewing problem in airline crew scheduling

AU - Tam, Bassy

AU - Ryan, David

AU - Ehrgott, Matthias

PY - 2014/12

Y1 - 2014/12

N2 - 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.

AB - 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.

U2 - 10.1002/mcda.1517

DO - 10.1002/mcda.1517

M3 - Journal article

VL - 21

SP - 257

EP - 277

JO - Journal of Multi-Criteria Decision Analysis

JF - Journal of Multi-Criteria Decision Analysis

SN - 1057-9214

IS - 5-6

ER -