Demand-Oriented Integrated Scheduling for Point-to-Point Airlines

Optimizing an airline schedule usually comprises multiple planning stages. These are the choice of flights to offer (schedule design), the assignment of fleets to flight legs (fleet assignment), and the construction of rotations under consideration of maintenance constraints (aircraft maintenance routing). Moreover, the airline must assign crews to all flights (crew scheduling). Traditionally, either these scheduling stages are considered sequentially or an existing schedule is modified to cope with the arising complexity issue. More recently, some authors have developed models that integrate adjacent stages. In this paper, outcomes of a research project with airline information technology provider Lufthansa Systems are presented. We consider the case of a small to medium-sized point-to-point airline with a homogeneous fleet. Hence, fleet assignment is omitted, which offers the possibility to solve schedule design and aircraft maintenance routing simultaneously. Our approach explicitly accounts for passengers’ return flight demand and for marginal revenues declining with increasing seat capacity, hence, anticipating the effects of capacity control in revenue management systems. To solve the arising integrated mixed-integer problem, a branch-and-price approach and a column generation-based heuristic have been developed. An extensive numerical study, using data from a major European airline provided by Lufthansa Systems, shows that the presented approaches yield high-quality solutions to real-world problem instances within a reasonable time.