School of Aviation

Sequential Optimisation for Airline Scheduling Planning
Sequential Optimisation for Airline Scheduling Planning

Airline schedule planning typically involves four steps from schedule design, fleet assignment, aircraft routing to crew pairing/rostering. At the stage of aircraft routing, schedule planning involves the optimisation of aircraft routing by formulating aircraft routing as integer programming problems such as the work by Arguello et al (1998), Barnhart et al (1998), Luo and Yu (1997), Rexing et al (2000), Teodorovic and Stojkovic (1995) and Yang and Young (1996). Sophisticated optimisation algorithms have been developed to solve complex integer programming problems and satisfactory results can be achieved within reasonable computing times and resources nowadays. In the real practice, aircraft routing problems are hardly solved by a single step. Instead, the routing optimisation and problem solving process may involve intervention from experienced airline schedulers, e.g. manually adjusting routing plans to reflect some operating constraints such as aircraft turnaround times at specific airports and flight punctuality targets of key feeder flights. This ‘fine-tuning’ procedure is widely used by airlines because the current approach in aircraft routing optimisation, e.g. integer programming is not an operation-oriented approach, but more optimisation focused.

Given the current aircraft routing optimisation approach, the robustness and reliability of airline schedules is not well considered against stochastic disruptions in operations. Therefore, experienced airline schedulers may manually adjust the preliminary results of aircraft routing to achieve higher schedule reliability and/or higher punctuality. In addition, this task is usually conducted under certain operational constraints, e.g. limited use of buffer times, airport slot availability, achieving punctuality targets and reducing delay propagation in the network. Regarding the algorithms to optimally adjust airline schedules at this stage of planning, most schedulers rely heavily on individual experience rather than on sound theoretical backgrounds and algorithms.

To solve the schedule fine-tune problem, sequential optimisation algorithms are proposed in this paper. Algorithms are developed to apply sequential optimisation in fine-tuning aircraft routing plans based on the preliminary results of aircraft routing planning. To evaluate the effectiveness of embedded buffer times in draft airline schedules, a simulation model (Wu, 2005) is used to generate the benchmark required to effectively allocate scarce aircraft times.

To demonstrate the effectiveness of the proposed sequential optimisation algorithm on schedule planning, a case study is conducted by using schedule information and punctuality data of an anonymous airline, denoted by ‘Airline X’. A selected fleet with 17 narrow-body aircraft flying to 20 destinations is used in the following case study.

The developed sequential optimisation algorithm is applied to Airline X’s network and the summary results are shown in Figure 1. The usage of buffer times for each rotation (operated individually by one aircraft) is compared with the estimated saving of delay times after sequential optimisation. Additional 260 minutes are used to relax aircraft routing plans according to optimisation criteria given above, and this also generates an estimated saving of 540 minutes delay network wide. If we assume that the monetary cost of one unit buffer time and delay time is $200 per minute, then the estimated impact of the sequential optimisation on the new schedule is equivalent to an extra expenditure for Airline X by $19 million dollars per annum but a delay cost saving by $39 million dollars per annum, resulting in $20 million dollars net saving on operating costs per annum. This estimated cost saving could be significant enough for the study regional fleet and could have a positive impact on the profitability of an airline.

The optimised schedule is tested by the schedule simulator to evaluate how the optimised schedule may react to current operating environment faced by Airline X. Simulation results of the optimised schedule are compared with the inherent delays of the Dream Case (Wu, 2005) and the current delays of the Reality Case in Figure 2 below. Although the delay level of the optimised schedule is only as good as 70% of the expected level, i.e. inherent delays, the optimised schedule effectively controls the overall delays across the network to the required target level. Total departure delays of the original schedule are 1,816 minutes, which is reduced to 1,278 minutes after optimisation. This result also reflects on the increase of average network-wide schedule reliability from 37% to 52% after optimisation.

Notes:

More Articles

More articles containing information about research in the Department of Aviation can be found on the homepage articles web-page.