Airline Network Planning: Mixed-integer non-convex optimization with demand–supply interactions.

Airlines routinely use analytics tools to support flight scheduling, fleet assignment, revenue management, crew scheduling, and many other operational decisions. However, decision support systems are less prevalent to support strategic planning. This paper fills that gap with an original mixed-integer non-convex optimization model, named Airline Network Planning with Supply and Demand interactions (ANPSD). The ANPSD optimizes network planning (including route selection, flight frequencies and fleet composition), while capturing interdependencies between airline supply and passenger demand. We first estimate a demand model as a function of flight frequencies and network configuration, using a two-stage least-squares procedure fitted to historical data, and then formalize the ANPSD by integrating the empirical demand function into an optimization model. The model is formulated as a non-convex mixed-integer program. To solve it, we develop an exact cutting plane algorithm, named 2 α ECP, which iteratively generates hyperplanes to develop an outer approximation of the non-linear demand functions. Computational results show that the 2 α ECP algorithm outperforms state-of-the-art benchmarks and generates tight solution quality guarantees. A case study based on the network of a major European carrier shows that the ANPSD provides much stronger solutions than baselines that ignore – fully or partially – demand–supply interactions. • We propose an optimization model for airline network planning (ANPSD). • ANPSD captures demand-supply interactions with predictive-prescriptive analytics. • We develop an outer approximation scheme for mixed-integer non-convex programming. • The algorithm generates provably near-optimal solutions, outperforming benchmarks. • The solutions outperform baselines that ignore demand-supply interactions. [ABSTRACT FROM AUTHOR]