Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 40, Issue 3, Pages 805-814Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2010.11.003
Keywords
Crew pairing problem; Pairings with flight repetitions; Column generation; Rolling horizon approach; Three-phase approach
Ask authors/readers for more resources
A crew pairing is a sequence of flights, connections and rests that starts and ends at a crew base and is assigned to a single crew. The crew pairing problem consists of determining a minimum cost set of feasible crew pairings such that each flight is covered exactly once and side constraints are satisfied. Traditionally, this problem has been solved in the industry by a heuristic three-phase approach that solves sequentially a daily, a weekly, and a monthly problem. This approach prohibits or strongly penalizes the repetition of the same flight number in a pairing. In this paper, we highlight two weaknesses of the three-phase approach and propose alternative solution approaches that exploit flight number repetitions in pairings. First, when the flight schedule is irregular, we show that better quality solutions can be obtained in less computational time if the first two phases are skipped and the monthly problem is solved directly using a rolling horizon approach based on column generation. Second, for completely regular flight schedules, we show that better quality solutions can be derived by skipping the daily problem phase and solving the weekly problem directly. (C) 2010 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available