Integrated Aircraft Routing, Crew Pairing, and Tail Assignment: Branch-and-Price with Many Pricing Problems

Sebastian Ruther (), Natashia Boland (), Faramroze G. Engineer () and Ian Evans ()
Additional contact information
Sebastian Ruther: School of Mathematical and Physical Science, University of Newcastle, Callaghan, NSW 2308, Australia
Natashia Boland: School of Mathematical and Physical Science, University of Newcastle, Callaghan, NSW 2308, Australia; H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Faramroze G. Engineer: SK Innovation, Seoul, South Korea 03188
Ian Evans: Constraint Technologies International, Melbourne, VIC 3000, Australia

Transportation Science, 2017, vol. 51, issue 1, 177-195

Abstract: A significant drawback of the usual sequential airline scheduling approach is the long lead time between solution of the aircraft routing and aircrew planning problems, and the day of operation. We consider a new approach to airline planning, in which aircraft routes and crew pairings are reoptimized close to the day of operations, via solution of an integrated aircraft routing, crew pairing, and tail assignment problem. Instead of scheduling routes for generic aircraft, we generate routes for each, individual, aircraft given its current location, maintenance, and flying history, while also respecting its individual maintenance requirements. New pairings for crews are planned so as to lie within the work periods given in their roster. This allows aircraft routes and pairings to be designed based on more up-to-date information. By solving an integrated problem, the option of increasing robustness of the resulting schedule by keeping crews and aircraft on the same connections when the connection time is not long can be included in the optimization objective. The problem is formulated as a branch-and-price model with a pricing problem (PP) for each aircraft and each group of crews having the same work period availability and base. We develop two strategies to address the challenge of solving the large number of PPs that result. The feasibility of this approach is demonstrated using real airline data from an Australian domestic airline.

Keywords: airline scheduling; aircraft routing; crew pairing; tail assignment; branch-and-price; column generation; superimposed pricing problems (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
https://doi.org/10.1287/trsc.2015.0664 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:51:y:2017:i:1:p:177-195

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().