Rotation Planning for the Continental Service of a European Airline
We consider a version of the aircraft rotation problem where the objective is to minimize delay risks. Given a set of flights to be flown by a subfleet the rotation problem is to find a specific route for each aircraft of the subfleet such that each fligh
- PDF / 2,482,961 Bytes
- 15 Pages / 439.32 x 666.12 pts Page_size
- 95 Downloads / 156 Views
Universitiit zu K61n, Institut fUr Informatik, PohligstraBe 1, 50169 K61n, Germany Technische Universitiit Berlin, Fachbereich Mathematik, StraBe des 17. Juni 136, 10623 Berlin, Germany
Abstract. We consider a version of the aircraft rotation problem where the objective is to minimize delay risks. Given a set of flights to be flown by a subfleet the rotation problem is to find a specific route for each aircraft of the subfleet such that each flight is flown by exactly one aircraft. Additionally, the sequence of flights defining a route must satisfy certain requirements mainly to avoid delays. We present a mathematical model for the problem of minimizing the delay risk according to special requirements of a major airline. An efficient Lagrangian heuristic is proposed that uses subgradient optimization and linear assignments as subproblems. Computational results on real data are given and compared to actual aircraft rotations of that airline.
1
Introduction
The aircraft rotation problem we consider in this article is one of the first steps in the planning process of an airline. Usually, two other problems have to be solved before. First, the airline must decide which flights should be offered. This depends, for instance, on the expected numbers of passengers and profits of the flights. Because an airline has different types of aircraft (subfleets) each with different characteristics like seating capacities, crew size, and operational costs it must also decide which aircraft type should be used to establish a connection. The result of this fleet assignment is a flight schedule for each subfleet which is the input for the rotation planning problem. A flight schedule for a given subfleet consists of different legs (i.e., nonstop flights) each defined by a departure and arrival airport, a date, and departure and arrival times. An example for a leg between Frankfurt and Amsterdam could be (FRA / 15. Aug / 19:20 ---+ AMS / 15. Aug / 20:25) The aircraft rotation problem is to determine routes, i.e., sequences of consecutive legs flown by the same aircraft. In contrast to other problems arising within the planning process of an airline (like the fleet-assignment problem mentioned above or the crewscheduling problem) the aircraft rotation problem has seldomly been a subject W. Jäger et al. (eds.), Mathematics - Key Technology for the Future © Springer-Verlag Berlin Heidelberg 2003
676
M. Junger et al.
in Combinatorial Optimization. Some models, solution methods, and results for the aircraft rotation problem of major U.S. airlines can be found, e.g., in the papers of Clarke et al. ([1997]) and Bohland et al. ([1998]). The main objective of their models is the maximization of the through value. Because airline networks in northern America have a distinctive hub and spoke structure, passengers often have to change airplanes at the hubs during their trip. Airlines try to make their connections attractive by choosing rotations which allow passengers to travel without changing airplanes too often. The trough value is the re
Data Loading...
