Air cargo scheduling: integrated models and solution procedures

摘要

Designing a profitable flight schedule is a highly complex planning problem. Both passenger and cargo airlines usually follow a decomposition approach and break this problem into several subproblems which are then solved consecutively and iteratively using specific but isolated models. At cargo airlines, the four major interdependent decision problems are flight selection, fleet assignment, rotation planning, and cargo routing. In our research, we have developed a planning approach which differs from other OR-based planning approaches in two aspects. The approach is based on integrated models and it is based on the pragmatic planning paradigm to optimally modify an existing schedule. For this purpose, the planner has to identify mandatory and optional flights. Then the planning goal is to identify the best combination of optional flights to be included into the schedule. Our integrated planning models comprise several additional important planning aspects for cargo airlines such as available capacities on external flights (e.g. belly capacities from passenger flights or road-feeder services), cargo handling costs and constraints, and aircraft maintenance regulations. There are two main aspects which we present in this paper. First, we describe the planning problem and the specific planning paradigm, develop a set of complex mixed-integer programs representing the different subproblems, and finally present integrated problem formulations as well as several model extensions. Thereafter, we develop a branch and price and cut approach for solving the mathematical programs and present extensive computational results obtained for a set of generated yet highly practical problem instances for different types of carriers. The results show that our approach is able to find high quality solutions to problem instances of realistic size and complexity within reasonable time.