Solving Multi-Criteria Through-Fleet Assignment Models

R. K. Ahuja, J. Liu, J. Goodstein, A. Mukherjee, J. B. Orlin, and D. Sharma. Operations Research in Space and Air, Edited by Tito A. Ciriani, Giorgio Fasano, Stefano Gliozzi, and Robert Tadei, Kluwer Academic Publishers, 233-256, 2003.

The airline industry has been a pioneer in using operations research techniques to solve complex business problems related to the schedule planning of the airline. Given a flight schedule, an airline's schedule planning group needs to decide the itinerary of each aircraft and each crewmember so that the total revenue minus the total operating costs is maximum and all the operational constraints are satisfied. The entire planning problem is too large to be solved to optimality as a single optimization problem using present day technology; hence, these problems are solved sequentially where the optimal solution of one problem becomes the input for the following problem. A sequential approach for solving such problems has an inherent drawback in that the solution at each stage does not take into account the considerations of subsequent stages. The ultimate goal in the optimization of schedule planning is in solving an integrated optimization problem that addresses the planning problem mentioned above as well as other downstream issues that affect the overall schedule quality. Our approach for integrating the models is to include additional objectives that take into account the downstream issues. We describe our efforts to incorporate two criteria in the Combined Through-Fleet Assignment Model in addition to the traditional cost criteria: (i) ground manpower costs, and (ii) crew costs. We use very large-scale neighborhood search techniques to determine good solutions to the multicriteria Combined Through-Fleet Assignment Model. This chapter is based on techniques developed by the authors for the single-criteria Combined Through-Fleet Assignment Model, which in turn is based on earlier work of Talluri. This chapter describes the algorithmic approaches developed and the computational results of these algorithms.