Modeling and Solving the Airline Schedule Generation Problem
Erdmann, Andreas and Nolte, Andreas and Noltemeier, Anja and Schrader, Rainer
Modeling and Solving the Airline Schedule Generation Problem.
Published in: Annals of Operations Research Vol. 107 (1-4). pp. 117-141.
Since opening a new flight connection or closing an existing flight has a great impact on the revenues of an airline, the generation of the flight schedule is one of the fundamental problems in airline planning processes. In this paper we concentrate on a special case of the problem. In contrast to airlines operating on regular schedules, the market for charter airlines is well-known and the schedule is allowed to change completely from period to period. Thus, precise adjustments to the demands of the market have a great potential for minimizing operating costs. We propose a Branch-and-Cut approach to solve the airline schedule generation problem. To tighten the linear relaxation bound, we add cutting planes which adjust the number of aircraft and the spill of passengers to the demand on each itinerary. For real-world problems from a large European charter airline we obtain solutions within a very few percent of optimality with running times in the order of minutes on a customary personal computer for most of the data sets.
|Citations:||3 (Web of Science)|
|Uncontrolled Keywords:||branch-and-cut capacitated network design Dantzig-Wolfe decomposition set packing set partitioning|
|Divisions:||Institute of Computer Science > Computer Science Department - Prof. Dr. Schrader|
|Depositing User:||Rainer Schrader|
|Date Deposited:||26 Jan 2008 00:00|
|Last Modified:||12 Jan 2012 12:33|