Atasoy, B., Salani, M., and Bierlaire, M. (2013)

A local search heuristic for a mixed integer nonlinear integrated airline schedule planning problem

In this paper we present a local search heuristic method for an integrated airline scheduling, fleeting and pricing model. The integrated model simultaneously optimizes the decisions of schedule design, fleet assignment, seat allocation, pricing and considers passengers’ spill and recapture. The resulting problem is a mixed integer non-convex problem due to the explicit representation of a demand model which guides the revenue management decisions. The local search heuristic tackles the complexity of the problem decomposing the problem into two simplified versions of the integrated model. The first model is a fleet assignment model where the pricing decision is fixed. The fleet assignment sub-model is a mixed integer linear problem. The second model is a revenue management model where the fleet assignment decision, i.e., the transportation capacity, is fixed. This revenue sub-model is a continuous nonlinear problem. These sub-models are solved in an iterative way with intelligent local search mechanisms. Price sampling is used for a local search on price and variable neighborhood search techniques are used for exploring superior fleet assignment decisions. Metaheuristic mechanisms permit to escape from local optima. The local search heuristic is presented in comparison to two other heuristic approaches: a heuristic procedure provided by an open-source generic MINLP solver and a sequential approach which mimic the current practice of airlines. The three approaches are tested on a set of experiments with different problem sizes. The local search heuristic outperforms the two other approaches in terms of the quality of the solution and computational time.