Airline Scheduling Background and Literature

Get Complete Project Material File(s) Now! »

Integration of Airline Scheduling Problems

Traditionally, airline scheduling problems have been solved sequentially although all five scheduling problems are interdependent. Among others the following dependencies exist in the sequential solution approach. The schedule design problem determines the set of flights that must be considered by all subsequent problems. But cheaper fleet assignment or crew pairing solutions might exist if the schedule could be altered slightly. In the aircraft routing problem a subset of flights, determined in the fleet assignment problem, is considered. Rules in the crew pairing problem depend on the underlying aircraft routing solution. And finally, the crew pairings are combined to rosters in the crew rostering problem.

Integration of Fleet Assignment and Schedule Design

Early approaches integrating FAM and schedule design work iteratively (see Etschmaier and Mathaisel [1985] for a survey). Demands for a given schedule are evaluated first. Then, FAM is solved and in the resulting schedule flights for addition and deletion are identified. With this new set of flights the demand for the schedule is evaluated again. Rexing et al. [2000] integrate the basic FAM problem and the time window problem with the goal of increasing revenue. Their model uses the time-line network. They discretise the time windows and add copies of flight arcs for each possible departure time. Additional constraints ensure that exactly one copy of each flight is operated. Preprocessing of the network is necessary before the problem can be solved for realistic sized problems.

Integration of Fleet Assignment and Aircraft Routing

A weekly aircraft routing problem is modelled as a set partitioning problem using a string formulation by Barnhart et al. [1998a]. A string is a maintenance feasible sequence of flights that starts and ends at a maintenance base. The set of flights is partitioned by maintenance feasible strings and the aircraft can be of different fleet types. The big-cycle constraint can be modelled similar to sub-tour elimination constraints in the travelling salesman problem. The authors solve the model by branch-and-price. The subproblem is a resource constrained shortest path problem on a connection network with labels for each maintenance type and for each nonlinear cost component.

Integration of Fleet Assignment and Crew Pairing

Barnhart et al. [1998c] partially integrate fleet assignment and crew pairing in a multi-commodity flow formulation. They enhance the basic FAM model by adding an approximation of the crew pairing problem based on a duty period formulation. Not all constraints of the original crew pairing model are considered and costs are underestimated. After this enhanced FAM model is solved crew pairing problems are solved for each fleet type. They report considerable savings in cost caused by making (slightly more expensive) decisions in the fleet assignment problem that enable much cheaper crew pairing solutions.

Model

Given a flight schedule, the crew pairing problem is defined as the problem of assigning generic crews to flights in the schedule such that each flight is operated by exactly one crew. A sequence of flights which can be flown by a crew on one work day is called a duty period. After each duty period a rest period must be assigned to each crew member. An alternating sequence of duty periods and rest periods is called a (crew) pairing or tour of duty. Any crew pairing must start and end at the same crew base and is restricted by a number of rules such as rest time regulations or flying time restrictions (see Section 4.2).

Contents :

• Introduction
• 1 Mathematical Background
  • 1.1 Set Partitioning Problem
  • 1.2 Multi-Commodity Flow Problem
  • 1.3 Column Generation
  • 1.4 Branch-and-Price
  • 1.5 Linear Program Decomposition Principles
    • 1.5.1 Dantzig-Wolfe Decomposition
    • 1.5.2 Benders Decomposition
    • 1.5.3 Lagrangian Relaxation
    • 1.5.4 Comparison of Decomposition Methods
  • 1.6 Multiobjective Optimisation
• 2 Airline Scheduling Background and Literature
  • 2.1 Airline Scheduling Problems
    • 2.1.1 Problem Characteristics
    • 2.1.2 Schedule Design
    • 2.1.3 Fleet Assignment
    • 2.1.4 Aircraft Routing
    • 2.1.5 Crew Pairing
    • 2.1.6 Crew Rostering
  • 2.2 Integration of Airline Scheduling Problems
  • 2.3 Robustness
  • 2.4 Overview of Solution Approaches for Airline Scheduling Problems
• 3 Aircraft Routing Problem
  • 3.1 Model
  • 3.2 Rules
  • 3.3 Solution Methods
    • 3.3.1 Preprocessing
    • 3.3.2 LP-Relaxation
    • 3.3.3 Column Generation
    • 3.3.4 Branch-and-Price
    • 3.3.5 Alternative Set Partitioning Formulation
    • 3.3.6 Decomposition Methods
  • 3.4 Computational Experiments
• 4 Crew Pairing Problem
  • 4.1 Model
  • 4.2 Rules
  • 4.3 Operational Robustness
  • 4.4 Solution Methods
    • 4.4.1 LP-Relaxation
  • 4.4.2 Column Generation
  • 4.4.3 Branch-and-Price
• 5 Robust and Integrated Aircraft Routing and Crew Pairing
  • 5.1 Model
  • 5.2 Solution Methods
    • 5.2.1 Iterative Approach
    • 5.2.2 Dantzig-Wolfe Decomposition Approach
    • 5.2.3 Benders Decomposition Approach
    • 5.2.4 Discussion of Approaches
  • 5.3 Computational Experiments
    • 5.3.1 Iterative Approach for a Single Crew Group
    • 5.3.2 Comparison of Iterative Approach and Optimisation Approaches
    • 5.3.3 Iterative Approach for Multiple Crew Groups
  • 5.4 Simulation
  • 5.5 Visualisation
• 6 Robust and Integrated Aircraft Routing and Crew Pairing with Time Windows
  • 6.1 Model
  • 6.2 Rules
  • 6.3 Solution Methods
    • 6.3.1 Time Window Branching Approach
    • 6.3.2 Re-timing of Flights for Fixed Aircraft Routings and Crew Pairings
  • 6.4 Computational Experiments
• Conclusion
• References

GET THE COMPLETE PROJECT
Robust and Integrated Airline Scheduling