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

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.