Integrated Airline Planning Models

by Johnson, Anne Elizabeth

Technological and industrial advances have resulted in the growth of large enterprises. Optimization models have been developed to increase the efficiency of parts of these systems, but models that optimize entire enterprises are frequently immense and very complex to solve. Sequential solution techniques have resulted, which lead to useful, but not globally optimal, solutions. For example, airlines develop flight schedules based on strategic business objectives, and sequentially plan operational processes to execute the schedule. Proven models that exist for the operational subproblems are solved sequentially, begin with a flight schedule, and allow limited feedback in the planning process. Since small changes to the individual parts have produced millions of dollars in improvement, an overall optimal solution could yield a significant increase in the airline’s profit. We consider a modelling paradigm that moves toward integrated methods for the airline schedule planning phase using surrogate representations of the operational problems. In this context, surrogate models are relatively easy to solve, yet sufficiently representative of the operational problem to reflect its impact on schedule choices. To illustrate, we develop surrogate models of maintenance scheduling, crew scheduling, and revenue generation. We solve the master schedule problem with each surrogate model using well-known decomposition techniques, and then combine the surrogates into a single model that is readily decomposed into multiple subproblems and solved. The model developments include additional considerations in constructing surrogate models. For example, to demonstrate validation of a surrogate’s utility, we compared the feasibility indications from the maintenance subproblem surrogate to 11 those from a larger, exact model of maintenance feasibility. The crew scheduling surrogate model development incorporates disruptions in the master schedule, driving the schedule to account for both crew costs and the impact of random disruptions. Finally, in the revenue management subproblem, we consider random demand that impacts a schedule’s profitability. While surrogate solutions are inherently of little utility operationally, the results are useful for shaping the master schedule towards a global optimum. The paradigm allows for consideration of the subproblems in initial planning, so that solutions obtained from the full models are based on a schedule that may lead to a better overall bottom line. 12