Document [original]

Increasing Stability of Aircraft and Crew

Schedules

Viktor Dück

Der Fakultät für Wirtschaftswissenschaften der

Universität Paderborn

zur Erlangung des akademischen Grades

Doktor der Wirtschaftswissenschaften

- Doctor rerum politicarum -

vorgelegte Dissertation von

Dipl. Wirt.-Inform. Viktor Dück

July 2010

für meine Eltern

Acknowledgements

This thesis is a result of the research that I conducted as member of the Decision

Support & Operations Research Lab (DSOR) at the University of Paderborn. I

would like to start by thanking Prof. Dr. Leena Suhl for giving me the oppor-

tunity to work in her research group and to write this thesis. Her support, and

ever-friendly nature were a great motivation for me. I am very grateful to my

supervisor Prof. Dr. Natalia Kliewer for her unwavering support and for her

great guidance.

I would like to thank Ingmar Steinzen for great mentoring and continued en-

couragement, which gave me the necessary knowledge and confidence for writing

this thesis. I thank Ralf Borndörfer from ZIB and Ivo Nowak from Lufthansa

Systems for many fruitful discussions.

I thoroughly enjoyed the friendly atmosphere and stimulating working environ-

ment at the DSOR. I would like to thank Bastian and Boris Amberg, Valentina

Avrutova, Stefan Bunte, Jens-Peter Kempkes, Stefan Kramkowski, Franz Wes-

selmann and Jörg Wiese for their support and many fruitful discussions. In

particular, I wish to thank Lucian Ionescu and Torben Schramme for their great

help in implementing the optimization system.

This work is dedicated to my parents. You have always supported me and

believed in me. I owe you much more than words can ever express.

Viktor Dück

Paderborn, July 2010

Contents

1. Introduction 1

2. Airline Scheduling Background 5

2.1. Tactical Planning Process at the Airline Industry ......... 6

2.2. Operations in the Airline Industry ................. 13

2.3. Robust Scheduling .......................... 22

3. State Of The Art: Aircraft Assignment and Crew Pairing 25

3.1. Mathematical Background ...................... 25

3.2. Aircraft Assignment ......................... 32

3.3. Crew Pairing Optimization ..................... 34

3.4. Robust Scheduling of Aircraft and Crew Pairings ......... 38

4. Required Work 43

5. A Branch-and-Price-and-Cut Framework 47

5.1. The Formulation of the Crew Pairing Problem .......... 47

5.2. Pairing Generation .......................... 52

5.3. Finding Integer Solutions ...................... 58

5.4. Subset Row Inequalities ....................... 61

5.5. Application of the Framework to the Aircraft Assignment Problem 64

5.6. Computational Experiments ..................... 66

6. A Stochastic Optimisation Approach to Crew Pairing and Aircraft

Scheduling 75

6.1. Formulation of the Integrated Stochastic Problem ......... 75

6.2. Decomposition Strategy for the Recourse Model .......... 78

6.3. Corresponding Deterministic Indicators .............. 83

vii

Contents

6.4. Computational Experiments ..................... 86

7. Evaluation of indicators for Stability 89

7.1. Assumptions and Empirical Data .................. 90

7.2. Simulation of Airline Aircraft and Crew Schedules ........ 95

7.3. Simulation Experiments ....................... 99

8. Simultaneous Rescheduling of Aircraft and Crew Pairings 109

8.1. Integrated Formulation for Aircraft and Crew Rescheduling . . . 109

8.2. The Iterative Solution Approach .................. 111

8.3. Simulation Experiments ....................... 112

9. Summary and Conclusions 115

A. European Regulations on Crew Work-Time 121

B. Standard IATA Delay Codes 133

C. Distributions for Primary Delays 139

Glossary 145

Acronyms 149

List of Figures 151

List of Tables 153

List of Algorithms 155

Bibliography 157

viii

1. Introduction

Airline scheduling problems are highly complex and have for several decades now

been successfully solved by Operations Research methods. Commercial airlines

have to schedule huge numbers of resources like aircraft, airport gates and staff,

leading to huge potential for cost savings. At the same time the huge size and

the large number of dependencies of the scheduling problems at commercial air-

lines make it very difficult to generate feasible and cost-efficient schedules. For

these reasons, these problems have received much attention from researchers and

commercial software vendors leading to many sophisticated planning methods.

Today most major commercial airlines use software systems with optimization

methods to support their planning tasks.

With the introduction of software systems and sophisticated optimization me-

thods for scheduling tasks airlines are now able to shorten their planning cycles

and react faster to changing conditions during the planning phase as well as on

the day of operations. Rescheduling in case of disruptions, however, often cannot

prevent delays, because it is too expensive or simply no longer possible at that

time. In such cases delays lead to additional costs of compensating customers and

also possibly to additional delays due to complex dependencies between different

airline resources. It is common practice today to schedule reserve resources and

to place slack between flights in order to avoid delays or to have more possibili-

ties for rescheduling. Both methods, however, are very expensive and cannot be

performed extensively. Accordingly, the consideration of disruptions during the

planning of schedules has recently been given more attention by the research com-

munity. The goal is to schedule slack between flights as well as reserve resources

more intelligently in order efficiently to reduce the consequences of disruption.

In this work we focus on the problem of scheduling aircraft and crews under

consideration of disruption. Both schedules can be easily disrupted leading to

disruptions of aircraft maintenance schedules and working time regulations of

1. Introduction

crews. These disruptions are hard to recover and often lead to additional delays.

Moreover, the two problems are closely interdependent due to crews changing

aircraft on the day of operations. Such aircraft changes can lead to additional

propagation of delays between aircraft, i.e. following the crew from one to another

aircraft.

Both scheduling problems, aircraft and crew, are highly complex and difficult

to solve and are therefore often solved sequentially. The literature to date shows

that simultaneous consideration of these problems, however, can greatly reduce

costs as well as delay propagation. The approaches to simultaneous scheduling

of aircraft and crews in the literature only consider very simplified models for

delay propagation. But an effective reduction of delay propagation is the most

promising factor to achieve stability of airline schedules. Moreover, there is

no framework within which to evaluate and compare different approaches for

airline scheduling under consideration of disruptions, although there are many

simulation models for airline schedules. In order to compare different scheduling

approaches, however, we need a method to measure the quality of a scheduling

approach which also considers effects of disruption. To summarize, the aim of this

work is to research methods of evaluation of robust scheduling approaches and

to develop more exact stability indicators based on delay propagation between

aircraft and crews.

In this work we examine methods for simultaneously scheduling aircraft and

crews under uncertainty. We present two methods to consider the delay propa-

gation during scheduling of aircraft and crews. The first approach increases the

scheduled time for aircraft changes without measuring the actual delay propaga-

tion. The second approach distributes slack over the whole schedule according

to a measure of total delay propagation. The second approach involves additio-

nal complexity for the scheduling method, but promises a better measure of the

delay propagation and therefore better distribution of slack. The comparison of

the two methods is based on the evaluation of the operational performance of

schedules, which usually involves many aspects like punctuality, recovery effort

and negative effects on other resource schedules on the day of operations. We

perform an extensive simulation study to evaluate the developed scheduling ap-

proaches. The study is based on a simulation model which estimates the number

of additional delays and the effort of recovery and uses historical data of a major

European airline.

The consideration of uncertainty during scheduling introduces additional com-

plexity leading to even more complex problems. Thus an important aspect of

this work is the development of efficient methods for solving these scheduling

problems. We build on well-known optimization methods from the literature

and extend them in order to cope with uncertainty. As an additional result the

new techniques proposed can also be used to improve solution methods for clas-

sical scheduling problems without uncertainty. On the experience with planning

under uncertainty we additionally propose a method for rescheduling of aircraft

and crews due to disruptions on the day of operations.

The remainder of this work is organized as follows. The next Chapter presents

background knowledge on planning processes and daily operations of commercial

airlines. In Chapter 3we discuss recent approaches to consideration of disrup-

tions during scheduling. In Chapter 4we describe the goal of this work in detail

based on the conclusions from the previous chapter. In Chapter 5we present a

new method of efficiently scheduling aircraft and crews. In Chapter 6we develop

two approaches to consideration of disruptions during scheduling and compare

them in Chapter 7based on the evaluation of the operational performance of

airline schedules. In Chapter 8we present an additional result of this work, an

approach to rescheduling aircraft and crews on the day of operations. A summary

of this work and conclusions are given in Chapter 9.

2. Airline Scheduling Background

The topic of this work is the scheduling of crews and aircraft in the airline indus-

try during long-term planning considering uncertainty as well as on the day of

operations when irregular events lead to disruptions of schedules. The planning

problems relevant to this work can be divided into three groups: strategic plan-

ning problems,tactical planning problems and operational problems. Solution to

strategic planning problems requires general decisions about origin-destination

connections, size and composition of the airline fleet as well as the location of

the crew and maintenance bases (network design problem).

The tactical planning process starts several months before the day of ope-

rations with the objective of maximising the expected profit by meeting the

demand of customers and minimising the costs by using the own resources effi-

ciently. The following five planning problems are normally regarded as matters

of tactical planning. The schedule design problem determines which connections

between airports at which time are offered considering a forecast on the demand

of customers. For each flight an aircraft type has to be selected considering the

demand forecast as well as the availability of aircraft. This is obtained by sol-

ving the fleet assignment problem. Based on the resulting fleet assignment the

aircraft assignment problem is solved to obtain maintenance schedules for air-

craft as well as individual aircraft routes which cover all flights. Similarly, the

crew pairing problem is solved to determine cost-minimal itineraries for crews

covering all flights and satisfying general work-time regulations. In the next step

(the crew rostering or crew assignment problem) these itineraries are assigned to

individual crew members, satisfying individual work-time regulations. The dif-

ferent scheduling tasks are often performed by different organizational units of

the airline, although the tactical planning problems are closely interdependent.

Thus the scheduling tasks mainly consist of communicating with other units and

repeatedly adjusting the schedules.

2. Airline Scheduling Background

Operational problems are those solved on the day of operations, when the

planned schedules are executed. Irregular events, like aircraft damage or airport

congestion, make it necessary to change the schedules. The mathematical models

for the rescheduling tasks are often similar to their planning counterparts but

must be solved much faster. In contrast to long-term planning, the objective is

not to maximise profit but instead to reduce the impact of the delays on the

daily work.

In the remainder of this chapter we describe in Section 2.1 the tactical planning

process of a commercial airline and emphasize on the interdependencies of the

crew scheduling and the aircraft assignment problem. In Section 2.2 we briefly

describe the daily operations of commercial airlines and focus especially on irre-

gular operations including reasons for disruptions and possibilities to cope with

those.

2.1. Tactical Planning Process at the Airline Industry

The tactical airline scheduling process is often decomposed into several planning

problems in order to handle complexity of the different problems. Thus flight, air-

craft and crew schedules are created one after another over several months prior

to the day of operations. In practice, this is not a purely sequential process,

compare Figure 2.1, but instead the schedules are repeatedly adjusted during

the planning process in order to achieve good profitability and operational feasi-

bility, because all five tactical planning problems are closely interdependent. For

example, the actual departure and arrival times restrict the possibilities for itine-

raries for aircraft and crews, especially when considering maintenance restrictions

and work-time regulations. The fleet assignment also restricts the possibilities

for the aircraft assignment problem and crew scheduling, because members of the

flight crew are normally allowed to fly one aircraft type only. The crew pairing

problem depends on the aircraft assignment problem, because the robustness of

the schedules can be affected when a crew changes the aircraft during a work

duty. More precisely, a possible delay of a flight immediately before a scheduled

aircraft change of crew affects two other flights in the schedule, the next flight of

the crew itinerary due to missing crew as well as the next flight of the aircraft

itinerary due to missing aircraft.

2.1. Tactical Planning Process at the Airline Industry

Tactical Planning Operations

3 Y 1 Y 6 M 8 W 4 W 2 W 0

Schedule Design

Fleet Assignment

Aircraft Routing

Pairing Optimization

Crew Rostering

Aircraft Rescheduling

Crew Rescheduling

Flight Schedule

Crew Schedule

Operational Schedule

Figure 2.1.: Tactical and Operational Problems in the Airline Industry

The possibilities of manual adjustment to the schedules are limited by the com-

plexity of the overall problem. Thus a lot of research is devoted to formulating

integrated planning models and solving the scheduling problems simultaneously

with the goal of creating schedules that are more profitable and of better quality.

In practice, the integration of the planning process is very difficult, mainly for

two reasons. Firstly, the individual planning problems are highly complex and

difficult to solve, even with specially developed methods. The integration of those

problems often leads to a disproportionate increase in complexity and makes it

difficult to solve the problems. Secondly, today the individual planning steps

are often performed by different organization units of one airline company. A

partial or full integration requires substantial changes to the company processes,

performance indicators and objective functions currently used by the individual

units.

Nevertheless, significant decreases in costs and increases in schedule quality

are possible by considering some or all problems simultaneously. For example

small changes in the fleet assignment solution can lead to different crew pairings

2. Airline Scheduling Background

and therefore to significantly different crew costs, even if the objective of the fleet

assignment solution does not change. Much research is devoted to full or partial

integration of several or all planning problems with the goal of improving the

total costs and schedule quality.

In the remainder of this section we follow the classical decomposition of the

tactical planning process and briefly introduce each scheduling problem. Chapter

3discusses possibilities of integrating the solution methods of the individual

problems.

2.1.1. Schedule Design

The schedule design problem is highly interdependent with strategical decisions

on market selection and route development. Decisions on flight frequency and

timing are updated frequently to match experience gained with past schedules

and new forecasts on customer demand. The objective of this planning step is

considering the airline strategy, to reach as many customers as possible. Large

airline companies today mostly operate on hub-and-spoke networks, i.e. most

airports in the network have direct flights only to few airports (hubs), whereas

those hub airports have direct flights to most other airports (spokes). Travel

between airports that do not have a direct flight connection is possible by flying

to the hub airport and from there to the destination. Flight frequency and timing

have therefore also to satisfy the needs of customers who have to transfer from one

flight to another at hub airports (optimisation of the hub bank structure). The

schedule design problem is not focus of this work, see Etschmaier and Mathaisel

[1985] and Teodorovic and Krcmar-Nozic [1989] for an overview of literature.

The decision on departure times of flights is often integrated into other tactical

planning problems. In this case a flight schedule is given and only small deviations

in the departure times, usually at some interval around the originally scheduled

time, are allowed (Klabjan et al. [2002]). These integrated tactical problems have

the appendix with flight retiming or with time windows to the name.

2.1.2. Fleet Assignment

The fleet assignment problem is that of assigning an aircraft type to each flight

according to the passenger capacity, range and availability of the aircraft type.

2.1. Tactical Planning Process at the Airline Industry

The objective of this planning problem is often to maximize the number of pas-

sengers transported according to an expected demand and therefore to maximize

the expected profit. A correct fleet assignment has to respect the conservation

flow, i.e. each aircraft arriving at a station has to depart from the same station

later. Klabjan [2005] has lately given an overview on mathematical models for

the fleet assignment problem.

2.1.3. Aircraft Assignment

The aircraft assignment problem is that of assigning individual aircraft to flights

in the schedule considering the maintenance requirements of the aircraft and

other constraints. The aircraft assignment is performed for each fleet separa-

tely. The maintenance constraints may be classified into two main categories:

long-term planned maintenance stops and minor maintenance. The long-term

maintenance checks can last from several days to several weeks, where the air-

craft is unavailable for flights, and must be performed at special maintenance

bases, where certain technical equipment and staff are available. The long-term

maintenance stops are planned for all aircraft in advance, since they must be re-

gularly performed on each aircraft and the capacity of the maintenance facilities

is restricted.

Minor maintenance checks must also be performed at interval, normally defined

as the maximum number of flying hours. However, minor maintenance checks

usually last several hours only and can be performed at night. They can be

performed at more airports and are not as restricted by capacity of technical

facilities as the long-term maintenance checks.

The aircraft assignment can also be restricted by connection and flight restric-

tion constraints. The former describe which pairs of flights can be flown by one

aircraft in succession. This constraint is mainly given by the time at the airport

needed to unload all passengers, to clean and prepare the aircraft and to embark

the passengers for the next flight. The minimal time for those activities is called

minimal turn time and it usually differs with type of the aircraft, the departure

and destination airports and even gates and terminals.

The flight restriction constraints forbid certain aircraft from flying to certain

destinations, e.g. because the certain aircraft are too noisy or lack an entertain-

2. Airline Scheduling Background

ment system required for long flights. It is to be noted that this restrictions are

based on properties of individual aircraft as opposed to properties of types of

aircraft, which are considered in the fleet assignment problem.

The optimization criteria for the aircraft assignment problem are often related

to some quality indicators rather than real monetary costs, because the operatio-

nal costs are equal for all aircraft of the same fleet. Common quality indicators

consider the robustness of the solution. An example is to maximize the number

of standby connections, which are connections between successive flights longer

than some limit, for example two or three hours. The motive is that during long

length connections the aircraft can be used for other activities, e.g. to perform

other tasks in case of schedule disruptions. Therefore the objective is to penalize

medium length connections between successive flights and reward short and long

connections. Another example is to minimize the number of aircraft changes

performed by crews or to distribute slack in aircraft routes according to some

strategy, in order to reduce the impact of delays on the day of operations.

The models and objectives of the aircraft assignment problem differ greatly

between airlines. Some airlines plan aircraft assignments right after fleet assign-

ment and before crew scheduling focusing on planning the maintenance stops. In

such cases the problem is often also called maintenance routing. Other airlines,

which are able to schedule the maintenance stops more flexibly, often plan ac-

tual aircraft assignments close before the day of operations after crew scheduling

and focus on generating feasible aircraft routes or maximizing some objective

function (aircraft routing). Lately, the name tail assignment was proposed for

the aircraft assignment problem, where individual flight restriction constraints

as well as general maintenance and connection constraints are considered.

2.1.4. Crew Scheduling

The crew scheduling problem is that of assigning crew members to flights. Crew

scheduling at commercial airlines faces two kinds of restrictions. Firstly, general

restrictions on working and flying time which apply to all crew members; se-

condly, restrictions applying to individual crew members or certain flights, e.g.

special language requirements on certain flights or unavailability of certain crew

due to vacations or training. The crew scheduling problem is then often decom-

2.1. Tactical Planning Process at the Airline Industry

posed into two planning problems based on this classification of restrictions. In

the first step, that of crew pairing, anonymous crew crew pairings are generated.

Crew crew pairings are sequences of flights a crew flies starting and ending at

the same crew base.Crew bases are airports in the network, where crews start

and end their work duties, and often correspond to the airline hubs. The basic

restrictions of the problem are of course the conservation flow and the mini-

mal connection time between two consecutive flights in a pairing. The minimal

connection time between two flights is called minimal sit time and correspond to

the minimal turn time of the aircraft if the crew stays on the aircraft. In the case

of an aircraft change the minimal sit time is usually higher, because the crew

eventually has to transfer from one gate to another and to perform additional

checks on the aircraft.

The crew pairing problem also includes constraints concerning general work-

time regulations. The actual constraints and the objective function of the pro-

blem depend on the guidelines of governing agencies, the agreements with labor

organizations, the cost-structure of the airline and the scope of the optimiza-

tion. In this work we use rules and objectives which are common to European

airlines1. For rules and objectives usually used by airlines in North-America see

e.g. Barnhart et al. [2003]. A crew crew pairing basically consists of several daily

duties and night rests between them, see also Figure 2.2. Additionally, following

rules for crew crew pairings,duties and rests apply:

•Each crew pairing starts at one crew base with a briefing of 60 minutes and

ends at the same crew base with a de-briefing of 30 minutes.

•The duration of the crew pairing corresponds to the time away from home

for each crew member and is restricted to 96 hours at maximum.

•The minimum duration of a night rest is 10 hours.

•The maximal number of flying hours in a duty is 8.

•The maximum duration of a duty with flying tasks is 10 hours.

1Appendix Ais an excerpt from the regulations on flight, duty and rest requirements published

by the European Parliament.

2. Airline Scheduling Background

crew base

A B CC B

crew duty I crew duty II

crew pairing

rest periodsit time

time

B C

flight from airport B to C(de-) briefing

Figure 2.2.: Structure of a Crew Pairing

•The maximum duration of a duty can be increased to 12 hours, when the

following rest period is longer than 12 hours.

•The maximum duration of a duty can be increased to 14 hours when the

following rest period is longer than 14 hours and the intersection of the

duty with night hours between 1am and 7am is less than 2.

•The maximum duration of a duty can be increased to 13 hours when the

following rest period is longer than 14 hours and the intersection of the

duty with night hours between 1am and 7am is less than 4.

The objective of crew scheduling is basically to minimize the crew salaries and

other crew costs. Depending on the airline, crew salaries can be based on flying

time, total work time and time away from home. In the European Union crew

salaries are often fixed and therefore the strategic objective is to minimize their

number and the tactical objective is equally to distribute the work between all

members of the staff and to generate favorable work schedules. Other possible

crew costs consists e.g. of ground transport, accommodation and deadheading.

Deadheading describes a transfer of crew as passengers on regular flights. This

can be necessary to return the crew to the crew base or to transfer the crew to the

next flight at another airport. In this work we use the objective of minimizing the

2.2. Operations in the Airline Industry

number of daily duties, independently of the length of those duties. In particular,

we do not consider costs of accommodation nor do we plan deadheading. Besides

crew costs the objective function for the crew pairing problem often also considers

indicators for schedule quality. Common quality measures consider regularity of

daily schedules (see e.g. Klabjan et al. [2001a]) and robustness of schedules.

Many indicators for robust crew schedules are discussed in the literature. Si-

milarly to the aircraft assignment problem the goal could be to minimize the

number of aircraft changes performed by crews or to redistribute slack in crew

pairings to minimize effects of delays. Other indicators for robustness consider

the possibility of rescheduling some tasks of a crew to another crew on the day

of operations.

In the second step, the crew assignment problem, the generated pairings are

assigned to individual crew members, such that every pairing is covered by mul-

tiple crew members with the required qualification. The final crew work schedules

also contain tasks other than flight duties, e.g. training or reserve duties. The

objective of the crew assignment problem is to satisfy crew requests rather than

to minimize costs (see Barnhart et al. [2003]). There are different approaches to

finding a solution - the bidline and the personalized rostering approaches. The

bidline approach is usually used in North-America and carried out in two phases.

Firstly, a set of generic rosters covering all pairings is constructed. Then in the

second step crew members can bid for their preferred work schedules. The per-

sonalized rostering approach, often used outside of North-America, describes the

direct generation of rosters trying to maximize the individual preferences of all

crew members (Kohl and Karisch [2004]).

2.2. Operations in the Airline Industry

On the day of operations many operational tasks are performed to execute the

planned schedules, e.g. preparing, flying and maintaining the aircraft, boarding

and deboarding passengers and loading and unloading baggage, and preparing

and coordinate the airport facilities. Unforeseen events during the execution of

those tasks as well as congestion at airports and airspace lead to delays in those

tasks.

2. Airline Scheduling Background

Delays may be categorized in a variety of ways. Passengers mainly distinguish

between departure delay of a flight, which can cause impatience, arrival delay

of the last flight in the itinerary, which can be unpleasant due to personal time

restrictions at the destination, and arrival delay of any other flight in the itinerary,

which can be severe if the passenger misses the next flight.

In this work three categorization systems are important. Firstly, the length of

the total delay of a flight; secondly, the concept of primary delay and reactionary

delay; and thirdly, the categorization according to the delay cause.

The first categorization is the on-time performance of a schedule in operations.

An arrival or departure is on time if it is within xminutes of the originally

scheduled time of arrival or departure from a gate. The on-time performance is

usually measured for xbeing 0, 5, 15 and 60 minutes.

Aprimary delay is an immediate consequence of an unforeseen event, e.g. de-

crease in the landing capacity at an airport, difficulties during passenger boarding

or damage to aircraft. Primary delays can lead to disrupted airline schedules,

which cannot be performed as planned, due e.g. to unavailability of aircraft or

crew. A common strategy to resolve those disruptions is the intentional delay

of additional tasks, e.g. waiting for aircraft or crew. This intentional delay is

called reactionary delay or secondary delay.Reactionary delays can lead to new

disruptions of airline schedules. Delay analysis always starts with a primary de-

lay either of a flight tasks or a task during ground operations. For example, the

maintenance task of an aircraft may be delayed due to damage of the aircraft,

or the passenger boarding task due to late passengers. In both cases these pri-

mary delays of non-flight tasks can lead to disruptions of the ground operations

schedules and to a reactionary delay of the flight departure.

The distinction between primary and reactionary delay mainly depends on

the system boundaries, e.g. scope of the planning or rescheduling problem. For

example, during scheduling of crews and aircraft the ground processes between

two flight are aggregated to one task for aircraft and one for crew. Thus primary

delays occurring during the ground processes are also aggregated to primary

delays of those tasks. In a more detailed scope, i.e. considering individual tasks at

airports, the same delays can be decomposed into original delays and reactionary

delays. The distinction used by European Organisation for the Safety of Air

Navigation (EUROCONTROL) as well as in this work is based on flights. The

2.2. Operations in the Airline Industry

first delay to a flight is called primary delay, subsequent delays caused by the

unavailability of crews or aircraft are called reactionary delays. Thus a delayed

departure of a flight due to difficulties during the ground process is also a primary

delay.

Analyses of delay statistics carried out by airlines and air traffic control orga-

nizations are usually categorized according to the delay cause. See also EURO-

CONTROL [2007] for a good introduction by the EUROCONTROL. Figure 2.3

shows the relative frequency of delays in 2008 in Europe, where primary delays

are grouped by accountability. Over 40% of all delays are reactionary and cau-

sed by the recovery actions performed by the airline to achieve their operational

objectives. Half of all primary delays are airline-related and include initial de-

lays caused by ground and flight operations, passengers, loading and unloading

of baggage and cargo as well as damage to aircraft and other technical matters.

Airport-related delays mainly occur due to congestion of the airspace and par-

king areas, leading to arrival and departure delay. En-route delays are caused by

a lack of en-route airspace capacity, due e.g. to high demand or lack of air traffic

control staff. Weather delays account only for 10% of all delays. Weather delays

occur en-route as well as at departure and detination airports. At departure

airports weather can lead to difficulties to move around the airport as well as to

additional ground operations, like de-icing of the aircraft. At destination airports

weather can lead to reduced landing rates, due to high winds or low visibility.

Aircraft are actually rarely delayed en-route or on arrival at an airport: rather

the departure of those aircraft which are scheduled to fly to affected airports or

through affected airspace is delayed by the air traffic control. For purposes of

analysis and closer comparability most airlines record detailed information on

delay causes according to the International Air Transport Association (IATA)

delay code system2.

The majority of delay causes discussed here can also be categorized into three

groups: delays that are related to ground operations at airports, those caused by

air traffic control and reactionary delays caused by recovery actions.

2See Appendix Bfor the full list of IATA delay codes

2. Airline Scheduling Background

Primary

60%

Reactionary

40%

Airline

54%

Airport

17%

Weather

10%

Miscellane

ous

Security

En-Route

13%

Figure 2.3.: Departure Delay Causes in Europe, 2008, EUROCONTROL [2009]

In the remainder of this section we discuss the fundamentals of airline opera-

tions related to each of those delay groups: ground operations performed at the

airports, air traffic control and airline recovery processes on the day of operations.

2.2.1. Airport Ground Operations

The process of unloading the aircraft, preparing it for the next flight and loading

it is called airport turnaround process. The movement of the aircraft from the

runway to the gates is called taxi-in and the movement from the gates to the

runway after push-back is called taxi-out. The airport turnaround process takes

place between taxi-in and taxi-out. Figure 2.4 shows an overview of this process,

see also Boeing [2005] for a detailed example on duration and sequence of the

turnaround process. The whole process can be subdivided into two parts related

to the arrival and the departure of the aircraft:

After landing and the taxi-in to the parking position, the following tasks are

performed:

Docking is the arrival at the exact location at the gate or parking position,

where the ground tasks are performed.

2.2. Operations in the Airline Industry

On Block Off Block

Taxi IN Taxi OUT

Deboard

Passengers Board

Passenger

Crew

Check

Deboard

Crew Board

Crew

Cleaning and Catering

Fueling

Unload Baggage Load BaggageUnload Cargo Load Cargo

Water and Lavatory Services

Routine and Nonroutine Maintenance

De-icing

Figure 2.4.: Airport Turnaround Process of an Aircraft

Deboarding of passengers and crew starts with placing a boarding bridge or

stairs at the aircraft. Additional personnel and buses are needed to guide

the passengers.

Baggage and cargo unloading usually starts immediately after docking and can

be concurrently performed with the deboarding of passengers and crew. In

some cases cargo is unloaded at a special areas afterwards, whereas baggage

is always unloaded at stand.

Security checks are eventually performed on arrival when passengers from certain

countries are on board.

Immediately before the taxi-out to the runway and the take-off of the aircraft

following tasks are performed:

Cleaning of the interior of the aircraft before passengers board.

Fuelling is performed with pump or tank vehicles during cleaning and catering.

Catering delivers food to the aircraft. Some airlines consider special wishes

of passengers (like vegetarian meals), which requires additional planning

before the turnaround process.

Baggage and cargo loading is performed concurrently with passenger and crew

boarding. Like cargo unloading, in some cases cargo loading is performed

in special cargo areas.

2. Airline Scheduling Background

Passenger boarding right before the departure of the aircraft to prevent long

waiting times for passengers inside the aircraft.

Security checks of all passengers and their luggage at the gate are common at

some airports. In the case the security check is performed at a central area

of the airport it is not included in the turnaround process.

Aircraft checks are performed by the crew before each flight.

Deicing is the process of removing frozen contaminant, snow and ice, from the

aircraft. De-icing is performed immediately before departure of the air-

craft.

Pushback is the process of pushing back the aircraft from the gate and starting

the movement to the runway after all tasks of the turnaround process are

finished.

The tasks of the airport turnaround process are preformed concurrently, as

shown in Figure 2.4. The minimal time needed to complete this process is called

minimal turn time and usually depends on two critical paths of tasks. Firstly,

the time needed to unload and load baggage and cargo; and secondly, the time

needed to deboard passengers, clean the cabin and board passengers. The time

for both paths depends on the aircraft type as well as airport facilities, i.e. the

size of the aircraft, the number of entrance points and the number of available

boarding bridges. In the case that the crew changes the new crew usually perform

additional aircraft checks, which can lead to a longer minimal turn time.

Most of airline-related delays can be allocated to certain tasks in this process.

IATA delay codes 11 – 69 describe such delays, like, those caused by missing or

late passengers, errors during catering, fuelling, cleaning or cargo handling as

well as breakdown of technical equipment or aircraft and missing or late staff.

Even the damage to aircraft during flight operations is expressed as a nonroutine

maintenance task at the arrival airport. Delay codes 75 – 77 deal with weather

delays, like de-icing as well as of airport facilities or other delays of the airport

turnaround process due to adverse weather conditions.

2.2.2. Air Traffic Control

Air traffic control (ATC) can be described as the service of directing aircraft on

the ground and in the air to prevent collision, providing information and support

2.2. Operations in the Airline Industry

+4,5%

+8,8%

+13,3%

+19,3%

+19,9%

22.000

24.000

26.000

28.000

30.000

2004

2005

2006

2007

2008

Average Daily Traffic Trends and Variation Since 2003

Figure 2.5.: Traffic Variation in Europe

Since 2003, Source: EU-

ROCONTROL [2008]

1,7

1,9

2,1

2,3

0,0

1,0

2,0

3,0

2004

2005

2006

2007

2008

Total ATFM delay

En-Route delay

Airport delay

Figure 2.6.: Evolution of the Average

ATFM Delay Per Flight,

Source: EUROCONTROL

[2008]

for pilots and controlling the overall flow of traffic in order to deal with or prevent

congestion. The last task is also called air traffic flow management (ATFM). In

Europe the ATFM service is centrally provided by the EUROCONTROL Central

Flow Management Unit (CFMU). For a good overview of the tasks and of the

organization see Leal de Matos and Ormerod [2000]. The goal of ATFM is to limit

the impact of delays due to congested airports or airspace. Accordingly, on the

day of operations the CFMU can delay the depart of flights to affected airports

or airspace or reroute flights to avoid congested airspace. Moreover, additional

planning activities together with aircraft operators (airlines), flow managers, air

traffic controllers and national governments up to six months before a flight are

performed to achieve a more balanced distribution of traffic in European airspace

and to avoid delays on the day of operations.

One important measure is the average delay induced by ATFM,IATA codes

81 – 84. In 2008 the average delay per flight in Europe was 2.3 minutes – 1.6

minutes en-route and 0.7 minutes at an airport. The average ATFM delay has

increased constantly over the last years in Europe; see Figure 2.6. The main

explanation lies in the increase of the average number of daily flights in Europe.

In 2008, 27.818 daily flights took place on average, that is 19,9% more than in

2003; see Figure 2.5.

Figure 2.7 shows a comparison of total traffic and flights delayed over 15 mi-

nutes due to ATFM restrictions. We can observe a slight seasonal effect on the

total traffic as well as a large effect on the number of flight delays.

2. Airline Scheduling Background

10.000

20.000

30.000

40.000

50.000

60.000

70.000

80.000

90.000

100.000

200.000

300.000

400.000

500.000

600.000

700.000

800.000

900.000

1.000.000

Jan

Feb

Mar

Apr

May

Jun

Jul

Aug

Sep

Oct

Nov

Dec

Flights Delayed > 15 min

Total Traffic

Figure 2.7.: Comparison of Total Traffic and Flights Delayed > 15 min due to

ATFM Restrictions in 2008, Source: EUROCONTROL [2009]

2.2.3. Recovery of Disruptions

Up to two weeks before the day of operations the tactical schedules are handed

over to the operation control center (OCC) of the airline, which is then respon-

sible for the operation of the schedules. The OCC analyses all irregular events,

communicates with the ATFM, identifies disruptions to the schedules and per-

forms recovery actions to assure seamless operation of the planned schedules.

The OCC has to deal with all resources, especially airport gate assignment, pas-

senger connections as well as aircraft and crew schedules. Irregular events and

delays can lead to the following disruptions of aircraft and crew schedules; see

also Abdelghany et al. [2008]:

Aircraft or crew connect rule disruption occurs when an aircraft or crew mem-

ber arrives late from the previous flight delaying the next flight. The mi-

nimal turn time for aircraft and minimal sit time for crews have to be

considered. For crews this disruption is defined during duties only.

Crew rest disruption occurs when a crew member gets a rest period that is less

than the required minimal rest duration. This happens because of the

late arrival at the end of the preceding duty. The consequence is that the

2.2. Operations in the Airline Industry

affected crew member cannot fly the first flight of the next duty because

she/he must get her/his legal rest before starting the next duty.

Crew duty limit disruption occurs when the actual working time or flying time

during a duty of a crew member exceeds or would exceed the corresponding

limits, because of one or more delays during this duty. In this case the crew

member cannot fly the remaining flights of the duty nor, start a flight when

it is obvious that this disruption is going to happen during this flight.

Aircraft or crew open position disruption occurs when an aircraft or crew mem-

ber does not show up for the flight. In the case of aircraft the reasons could

be technical damage, nonroutine maintenance or cancellation of the pre-

ceding flight. In the case of crews the reasons could also be personal, e.g.

illness, or operational, e.g. flight cancellation.

To resolve these aircraft and crew-related disruptions the OCC can perform a

combination of following recovery actions:

Calling standby/reserve resource. Standby crews are located at main airports,

where they can be quickly assigned to new tasks. Reserve crews are nor-

mally at home and therefore need longer preparation time before they can

be assigned to tasks. If the resource disruption occurs at an airport without

standby/reserve crews, the crew need to deadhead from another airport.

There are rarely pure reserve or standby aircraft, due to high purchasing

costs. But in some cases an unused aircraft is available, e.g. because current

use of the fleet is lower than usual.

Swapping resources means that another crew or aircraft is assigned to the task

currently disrupted and the currently unavailable resource is assigned to

the tasks of the swapped resource, which are schedules for later discharge.

Sometimes multiple swaps between several resources are needed to resolve

these disruptions.

Reactionary delay means that the departure time of one or more flights is resche-

duled in order to accommodate waiting for aircraft, crew members, airport

facilities or passengers or load from other flights. Reactionary delays can

2. Airline Scheduling Background

of course lead to additional disruptions regarding own resources as well as

passengers. Reactionary delays are described by IATA codes 91 – 96.

Cancellation of one or more flights is performed when no other recovery option

is found. In this case passengers need to be rebooked to other flights and

the aircraft and crew routings must be modified to prevent open position

disruptions in future.

Today the recovery process at airlines is usually conducted manually on a

flight-by-flight basis rather than by developing one integrated plan for all flights.

Furthermore, different people are often responsible for recovery of different re-

sources, i.e. there are aircraft routers, crew schedulers, airport gate assigner,

ATFM coordinators and persons responsible for passenger connections. All re-

covery actions need to be coordinated by at least several of these people. The

difficulty here is that the recovery actions suitable for one resource, like small de-

lay to wait for the aircraft, can lead to disruptions at other resources, like crew

duty limit disruption due to the additional delay. Therefore in practice com-

plicated recovery actions are hardly performed: instead mainly standby/reserve

resources and reactionary delays are used, leading to almost as many reactionary

as primary delays.

In this work we refer to the overall process of adapting all schedules of the

airline to the new situation as recovery. The recovery process includes using

mathematical methods, such as optimization and simulation, as well as manual

adjustments to the schedules especially in combination with communication bet-

ween staff. Whereas rescheduling describes the adaption of one schedule to the

new situation with the aim of performing as few changes to the schedule as pos-

sible, usually several rescheduling steps with differing schedules are performed

during the recovery process.

2.3. Robust Scheduling

Besides disruption management on the day of operations the possibility of dis-

ruptions can be also considered during the schedule construction. This is called

robust scheduling. The goal of robust scheduling is to construct schedules which

2.3. Robust Scheduling

remain feasible and near cost optimal under different variations of the operating

environment.

The important question is how to measure robustness of a schedule. Scholl

[2001] distinguishes two aspects of robustness: stability and flexibility. Whereas

stable schedules are likely to remain feasible and near-cost optimal in a changing

operating environment, flexible schedules can be efficiently adapted to changing

operating environment. Robust schedules can also be stable and flexible at the

same time. In the airline field this means that a schedule is stable as long as it

remains feasible at justifiable costs without any manual changes to the schedules.

A schedule is flexible if in case of disruption recovery actions are possible in order

to restore the operational feasibility of the schedule without significantly increa-

sing costs. In the case of crew and aircraft schedules reactionary delays can be

considered as a manual recovery action as well as an automatic consequence if

no manual recovery is performed. Thus the number and duration of reactionary

delays is a main measure of the stability and flexibility of airline schedules. Addi-

tional measures of the stability of a schedule are the number of disruptions which

cannot be automatically resolved by reactionary delay. Additional measures for

the flexibility of a schedule are the costs of recovery as well as effects on other

schedules.

Figure 2.8 summarizes this chapter showing the interrelation of disruptions

for aircraft and crew schedules. If this scope is extended, additional sources of

primary delays and additional recovery actions need to be considered, but the

general interrelation remains.

Realistic measures of stability and flexibility of a schedule can be often compu-

ted by simulating the schedule-generating delays and using recovery actions. For

the purpose of constructing robust schedules, however, these computations are

far too complex for the application of optimization methods to minimize costs

and maximize robustness. Thus one challenge of robust scheduling is to find more

abstract indicators for robustness which are able to predict the robustness mea-

sure as well as lead to solvable mathematical representations of the scheduling

tasks.

An example of an indicators for stability is the minimization of aircraft changes

by crews when there is not enough slack to prevent propagation of delays to seve-

ral aircraft. An example of an indicators for flexibility is the number of theoretical

2. Airline Scheduling Background

disruptions

reactionary delays

airport processes

air traffic control

additional ressources

changes to schedules

crew schedules

aircraft schedules

primary delaysrecovery actions

scope

Stability Measures

Flexibility Measures

Figure 2.8.: Interrelation of Disruptions

possibilities for swapping crews in the current schedule. A high number indicates

that on the day of operations more efficient crew recovery is possible. Further

examples are given in Chapter 3. As in the case of those examples, most indica-

tors primarily support one measure for stability or flexibility. A second challenge

of robust scheduling is therefore to find indicators or sets of indicators to support

all main measures for stability and flexibility in order to obtain robust schedules.

3. State Of The Art: Aircraft

Assignment and Crew Pairing

In this chapter we discuss the planning problems and methods of aircraft and crew

scheduling in the airline industry in detail. In addition to scheduling methods

for both problems, we also discuss the integration of those planing problems, the

rescheduling on the day of operation and recent approaches to robust scheduling.

Other planning problems are also very important in the airline industry and often

difficult to solve, but not relevant for this work. For recent surveys on airline

scheduling problems we refer to Gopalan and Talluri [1998b], Klabjan [2005] and

Weide [2009].

The next section deals only with the mathematical background of the relevant

planning problems and methods and can therefore be omitted by readers with

experience in mathematical programming.

3.1. Mathematical Background

The airline planning problems addressed in this work are often formulated as ma-

thematical optimization models. In particular, the set partitioning and resource

constrained shortest path problems are widely used to model the problems in this

work. We therefore provide the necessary background to these two mathematical

problems as well as relevant optimization techniques. For extensive surveys of

combinatorial optimization we refer to Wolsey [1998].

3.1.1. Set Partitioning Problem

The set partitioning problem (SPP) is that of partitioning the rows of a m×n

zero-one matrix by a subset of columns at the minimal cost, see Wolsey [1998].

A column j∈Nis a subset of rows from M. The element aij is set to 1if column

3. State Of The Art: Aircraft Assignment and Crew Pairing

jcovers row iand to 0otherwise. xjis a binary variable that equals 1if column

j∈Nis part of the solution and 0otherwise. cjis the cost associated with the

corresponding column j. The SPP can be formulated as follows:

j∈N

cjxj→min SPP (3.1)

j∈N

aijxj= 1 ∀i∈M(3.2)

xj∈ {0,1} ∀j∈N. (3.3)

The objective (3.1) minimizes the costs of the selected columns and equations

(3.2) and (3.3) describe that each row must be covered by exactly one column

and no fractional selection of columns is allowed.

The set covering problem (SCP) is a relaxation of the SPP that requires to

cover each row by at least one column rather than exactly one column. The SCP

is formulated with a greater or equals sign "≥" in equation (3.2). The optimal

solution of the SCP is a lower bound of the corresponding SPP.

3.1.2. Resource-Constrained Shortest Path Problem and Dynamic

Programming

The resource-constrained shortest path problem (RCSP) is that of finding the

minimum cost path between a source node sand a sink node twhile respecting

constraints on resource consumption. Let G= (N, A)be a directed graph with

a set of nodes Nand a set of directed arcs A. A binary variable xij is set to 1,

if the directed arc (i, j)∈A, which is part of the solution and 0otherwise. cij is

the traversal cost and dr

ij ≥0is the resource consumption of resource r∈Rat

arc (i, j). A solution is resource feasible if and only if the consumption of each

3.1. Mathematical Background

resource r∈Ris greater or equal to the lower bound lrand less or equal to the

upper bound ur. The RCSP is formulated as follows:

(i,j)∈A

cijxij →min RCSP (3.4)

{j:(i,j)∈A}

xij −X

{j:(j,i)∈A}

xji =









−1

for i=s

for i∈N\ {s, t}

for i=t

(3.5)

lr≤X

(i,j)∈A

ijxij ≤ur∀r∈R(3.6)

xij ∈ {0,1} ∀(i, j)∈A. (3.7)

Note that cost and resource consumption at nodes can be easily transformed

to arcs. In this work the RCSP is efficiently solved using a dynamic program-

ming method by iteratively constructing all feasible paths from source sto sink

t. Paths are encoded by labels at nodes, thus Lk

npdescribes a label at node

np∈Ncorresponding to path Pk

np= (s, . . . , np−1, np), which is linked with its

predecessor label Ll

np−1at node np−1. The labels also store information about

cost c(Pk

n)and resource consumption (d1(Pk

n), . . . , d|R|(Pk

n)) of the represented

path. A basic pulling dynamic programming algorithm constructs (pulls) labels

from all predecessor nodes to a node by updating cost and resource consumption.

Thus a new label lat node jpulled from label kat node iis given by

j= (Lk

i, c(Pk

i) + cij, d1(Pk

i) + d1

ij, . . . , d|R|(Pk

i) + d|R|

ij )(3.8)

A new label is only created if the resource consumption does not exceed the

upper bound for all resources, i.e. ∀r∈R:dr(Pl

j)≤ur. In order to improve the

efficiency of the algorithm, only labels that are not dominated by already existing

labels are stored. A label is dominated by every label at the same node with less

or equal cost and resource consumption, i.e. Ln

idominates Lk

iif c(Pn

i)≤c(Pk

and ∀r∈R:dr(Pn

i)≤dr(Pk

i).

The performance of the algorithm mainly depends on the implementation of

the dominance tests, but can be further improved using preprocessing techniques

and problem-specific acceleration techniques. Irnich and Desaulniers [2005] give

3. State Of The Art: Aircraft Assignment and Crew Pairing

Algorithm 3.1: Basic label setting algorithm for the RCSP

Set Ls={(nil, 0,...,0)}

Set Lt=∅

foreach node j∈N\ {s}do

foreach predecessor node iof jdo

foreach label lat node ido

if ∃r∈R:dr(l) + dr

ij > urthen

next l

Set Lm

j= (l, c(l) + cij, d1(l) + d1

ij, . . . , d|R|(l) + d|R|

ij )

Add Lm

jto active labels at node j

Remove dominated labels at node j

an extensive overview on the formulations of the RCSP as well as the solution me-

thods. Hassin [1992] discuss polynomial approximation schemes for the restricted

shortest path problem with one resource. Lately Steinzen [2007] presented acce-

leration techniques for the restricted shortest path problem solved by a labeling

algorithm.

3.1.3. Branch-and-Bound

Branch-and-Bound is an exact solution method for combinatorial problems that

repeatedly divides the problem into smaller subproblems and solves these sub-

problems recursively. The method begins with solving a relaxation of the original

problem, usually a linear relaxation. If the solution of the relaxed problem is not

feasible in the original problem, the relaxed problem is divided into two or more

subproblems by fixing alternatives aspects of the solution. This process is called

branching, i.e. two or more alternative branches of the solution space are created,

called nodes. Through repeated branching a set of connected nodes is created,

also called the branch-and-bound tree. Besides the creation of smaller problems,

another aim of branching is to eliminate the current infeasible solution.

Feasible solutions are found during the process, because either the solution of

a relaxation of the problem is, fortunately, feasible or the solution space only

contains a feasible solution after repeated branching. The main idea of branch-

and-bound is to prevent unnecessary exploration of the solution space through

eliminating nodes, which certainly cannot contain an optimal solution. This step

3.1. Mathematical Background

Algorithm 3.2: Branch-and-Bound

Initialize the set of unprocessed nodes Nwith the original problem

Set upper bound Z∗= inf

while N6=∅do

Select next node n∈Nand delete it from N

Solve the linear relaxation of the problem in node nand store dual

bound b

Zand solution b

if b

xis empty then

Prune node nby infeasibility.

else if b

Z≥Z∗then

Prune node nby bound.

else if b

xis integer then

Set Z∗=b

Zand x∗=b

Prune node nby optimality.

else /* Perform Branching */

Create two subproblems n1and n2that cut off the current fractional

solution

Add both problems to N

Terminate with solution x∗and objective Z∗

is called bounding. Thus the objective value of infeasible solutions represents a

bound to the optimal feasible objective value in this node. For minimization

problems this is the lower bound. A node cannot contain a better solution, if the

lower bound of this node is greater or equal to the best known objective value of

a feasible solution.

Algorithm 3.2 shows the outline of the method. After solving the relaxation

of the problem basically three steps are evaluated. Firstly, if no solution could

be found, the node is pruned due to infeasibility. Secondly, if the solution of the

relaxed problem is feasible, this node does not need to be explored further and

is therefore pruned due to optimality. If the objective value is better than the

best known objective value, it is stored for bounding and as a possible optimal

solution. In the usual case that the solution is not feasible, however, branching

is performed and two or more new nodes are added to the tree. As long as

unprocessed nodes exist the algorithm continues with the next node.

3. State Of The Art: Aircraft Assignment and Crew Pairing

The performance of the algorithm is mainly determined by the strategies for

branching as well as selection of the next node. For both strategies there is

extensive research and a lot of problem-specific approaches. In this work we

discuss strategies for crew scheduling and aircraft routing in Chapter 5and 8.

The algorithm can be extended in a variety of ways. A well-known generic

approach is to strengthen the relaxation of the problems solved during branch-

and-bound with valid inequalities (cuts), giving rise to the name branch-and-

cut. If a column generation method is used to solve the linear relaxation of the

problems during branch-and-bound, the whole algorithm is usually called branch-

and-price. If both concepts, valid inequalities as well as column generation, are

applied, the method is called branch-and-price-and-cut.

3.1.4. Column Generation

Column generation is a method of solving linear programs with a large number

of variables. The main idea of column generation is to solve two smaller linear

programs iteratively until an optimal solution to the original problem is found.

Consider the following linear program

j∈N

cjxj→min Master Problem (3.9)

j∈N

aijxj=di∀i∈M(3.10)

xj∈R∀j∈N. (3.11)

We assume that |N|is huge, such that it is impossible or impractical to solve

the master problem directly. The idea of column generation is to solve several

restricted master problems (RMPs) each with a small subset of all columns.

Algorithm 3.3 shows the outline of the column generation algorithm. Firstly, the

RMP is solved with an initial set of columns N0that contains a feasible solution.

The dual solution of the RMP is used to select new columns, which can improve

the solution of the current RMP. New columns are often obtained by solving

another linear program, the pricing problem. The goal of the pricing problem is

to find columns with negative reduced costs, i.e. columns that can improve the

3.1. Mathematical Background

objective value of the current RMP. Thus the pricing problem is often formulated

as that of finding the column with the smallest reduced costs:

c∗min{cj−X

i∈M1

aijπi:j∈N}(3.12)

If the found column has negative reduced costs it is added to the RMP and the

problem is solved again with the new set of columns. If no column with negative

reduced costs can be found, the column generation algorithm terminates with

the solution of the current RMP as an optimal solution to the original problem.

In order to improve the performance of the algorithm often several columns

with negative reduced costs are added in each iteration of column generation

(multiple pricing). Especially for degenerated, large-scale problems the value of

the reduced costs is a rough indicator of the improvement of the objective value

only. Thus the pricing step is often not solved to optimality in each iteration of

column generation, but instead only a sufficient number of columns with negative

reduced costs is selected. At the end of column generation, however, the pricing

problem needs to be solved to optimality to prove that no further columns with

negative reduced costs exist.

For scheduling problems such as those considered in this work, the pricing

problem is often formulated as a resource-constrained shortest path problem

and solved with dynamic programming methods. In order to solve integer pro-

grams with many variables such as the already-mentioned scheduling problems,

a column generation algorithm is often integrated with a branch-and-bound al-

gorithm. In this solution approach, often called branch-and-price, a column

generation algorithm is used to solve the linear relaxation of the master problem

in each node of the branch-and-bound tree.

We refer to Wolsey [1998] for a general discussion on column generation and to

Barnhart et al. [1998] for a discussion on column generation for integer programs.

Recent surveys on column generation methods are given by Desrosiers and Lüb-

becke [2005], Lübbecke and Desrosiers [2005] and Desaulniers et al. [2001].

3. State Of The Art: Aircraft Assignment and Crew Pairing

Algorithm 3.3: Column Generation Algorithm

Initialize N0

Set t= 0 and Nnew =N0

while |Nnew| 6= 0 do

Solve restricted master problem with Ntand store dual solution πt

Solve pricing problem with πtand obtain columns Nnew

Set Nt+1 =Nnew ∪Ntand t=t+ 1

3.2. Aircraft Assignment

The aircraft assignment problem differs between airlines and research publica-

tions; compare Grönkvist [2005] and Chapter 2. The aircraft assignment step is

sometimes performed before and sometimes after crew scheduling. In most pu-

blications maintenance constraints are considered; in some connection and flight

restriction constraints also. There are many different objectives used for aircraft

assignment, ranging from pure feasibility problems to different robustness crite-

ria. The numerous variations of the aircraft assignment problem lead to many

different solution approaches proposed in the literature.

Clarke et al. [2003] describe a mathematical formulation for the daily aircraft

assignment problem with maintenance checks required every three or four days.

One additional constraint is that each aircraft must fly all flights in the schedule

within a certain time window. This constraint is called big-cycle constraint and

is equivalent to finding a Euler-tour in the flight network. The objective of the

problem is to maximize the through revenue. Through revenue describes the be-

nefit to the customers if two flights are operated by the same aircraft in sequence.

The benefit arises if customers booked both flights and can therefore stay on the

aircraft between these. The problem is formulated as an asymmetric travelling

salesman problem with additional constraints. In the first step of the solution

method the sub-tour elimination constraints and maintenance constraints are re-

laxed in a Lagrangian way. The relaxed problem is then solved iteratively and

the violated relaxed constraints are added again to the problem. The proce-

dure is embedded in a branch-and-bound method to prove optimality. Gopalan

and Talluri [1998a] propose a two-step method for solving this problem. In the

first step, several daily routes of aircraft, which span several airports, are fixed

3.2. Aircraft Assignment

by applying simple heuristics. The resulting routes end in so-called overnight-

airports and lead to a reduced network with one arc for each fixed daily route.

The overnight-airports can have maintenance capabilities; maintenance then is

performed at night. Thus in the second step the maintenance problem is solved

on the reduced network requiring the three-day maintenance constraint. Sriram

and Haghani [2003] provide a multi-commodity network flow problem formula-

tion for the weekly aircraft assignment problem with maintenance constraints.

The model requires routings for each day as input and is solved by a heuristic

local search.

Grönkvist [2005] consider individual aircraft for the aircraft assignment pro-

blem resulting in a set partitioning formulation, where the columns represent

aircraft routes and constraints ensure that each flight is covered by exactly one

aircraft. The formulation is solved by column generation with a heuristic fixing

process in order to integer solutions. Constraint programming is used in a pre-

processing step to reduce the size of the flight network in the pricing subpro-

blem. Sarac et al. [2006] extend the set partitioning formulation with additional

constraints to ensure sufficient capacity at maintenance bases. The solution

method is also based on column generation which is embedded into a branch-

and-price algorithm. The branching strategy is a combination of follow-on and

aircraft-flight pair branching (see Section 5.3). The pricing subproblem is a

constrained shortest path problem with one resource and is solved by dynamic

programming.

Several authors propose integration of the aircraft assignment and the fleet as-

signment problems. Barnhart et al. [1998] consider the integrated problem with

maintenance requirements and general connection restrictions. The problem is

formulated as a set partitioning problem where the columns are strings repre-

senting a feasible sequence of flights that starts and ends at a maintenance base.

The set partitioning constraint requires that each flight is covered by exactly

one maintenance string. The problem is solved by branch-and-price with a re-

source constrained shortest path problem for generation of maintenance strings.

Ioachim et al. [1999] propose a multi-commodity flow formulation for the inte-

grated fleet and aircraft assignment with time windows. Additional constraints

are added to synchronize departure times of flights on different days. The pro-

blem is also solved by branch-and-price. Desaulniers et al. [1997] propose two

3. State Of The Art: Aircraft Assignment and Crew Pairing

formulations, a multi-commodity flow and a set partitioning formulation, for the

integrated fleet and aircraft assignment with time windows. Both formulations

are solved with column generation and branch-and-bound.

Clausen et al. [2009] have recently provided a comprehensive review of concepts

and models used for recovery of airline resources. Many solution approaches to

aircraft rerouting are based on the original planning methods and incorporate

flight cancellations and retiming. See Jarrah et al. [1993], Rakshit et al. [1996],

Yan and Yang [1996], Cao and Kanafani [1997a] and Cao and Kanafani [1997b]

for publications on methods based on network-flow algorithms. Several authors

propose column generation algorithms for a set partitioning formulation of the

aircraft recovery problem, see i.e. Rosenberger et al. [2003] and Andersson and

Värbrand [2004].

3.3. Crew Pairing Optimization

The crew pairing problem is usually restricted by complicated feasibility and

cost rules for the pairings. A very large number of feasible pairings exist, such

that their enumeration is often impossible. Until the 1990s many heuristic local

search methods were proposed to solve the problem. Today the problem is usually

solved by mathematical optimization methods because these can provide better

solutions as well as a bound on the quality of the solutions. In most cases column

generation methods are used to avoid the enumeration of all feasible pairings.

The RMP is in most cases a set partitioning or set covering problem ensuring

that each flight is covered by exactly or at least one crew pairing. Feasible

crew pairings are generated in the pricing subproblem. In this work we describe

some of the most important formulations and solution methods based on column

generation. For a comprehensive overview of state-of-the-art solution methods

we refer to Barnhart et al. [2003] and Gopalakrishnan and Johnson [2005].

There are two main types of network to model the pricing subproblem. Vance

et al. [1997] describe both, the flight-based and the duty-based network. In a

flight-based network all flights from the schedule are connected by arcs. In the

duty-based network possible duties are connected by arcs. Thus using the duty-

based network either all duties have to be enumerated at the beginning or the

pairing generation becomes a two-step process: in the first step promising duties

3.3. Crew Pairing Optimization

are generated and in the second promising pairings are created. The two-step

process limits the solution space of the pricing subproblem, because only a subset

of all possible duties is used to build the network for pairing generation. The

implicit consideration of duties in the flight-based network has no such limitation.

Further, the duty-based network has more arcs because there are usually more

duties than flights, but also the advantage that all duty rules can be built into

the network. In contrast, if a flight-based network is used, duty and crew pairing

rules have both to be checked by the algorithm.

Both types of network, flight-based and duty-based, can be designed as a time-

space or as a connection-based network. In a connection-based network flights

or duties are represented by nodes. Arcs represent possible connections between

flights or duties. Each pair of flights or duties that can occur in succession in a

crew pairing is connected by an arc. A time-space network uses arcs for flights

and duties and nodes for start and end of each flight or duty. Additional arcs

connect pairs of chronologically consecutive nodes at one airport and represent

a ground waiting timespan at this airport. Thus possible connections between

flights or duties are represented implicitly through one or more ground waiting

arcs. Desaulniers et al. [1999] describe both network structures for the flight-

based network type. The time-space network has fewer arcs in comparison to

the connection-based network, but requires an explicit check of the night rest

and sit-time rules by a search algorithm. In the context of branch-and-price,

branching decisions on flight connections can be represented by simply removing

arcs from the connection-based network. In contrast, the time-space network

requires branching decisions to be enforced by the search algorithm.

In all possible networks a path represents a crew pairing. Pairings with ne-

gative reduced costs can improve the solution of the current restricted master

problem. There are several approaches to finding crew pairings with negative

reduced costs. A resource constrained shortest path problem can be solved by

dynamic programming, where non-linear feasibility and cost rules are represented

by resources as in Vance et al. [1997], Desaulniers et al. [1997]. Anbil et al. [1998]

use a depth-first-search enumeration of the pairings. Klabjan et al. [2001b] use

a random depth search algorithm where the probability of a connection to be

selected is decreased with the duration of connection time. Galia and Hjorring

[2004] solve a k-shortest path problem until a path with negative reduced cost

3. State Of The Art: Aircraft Assignment and Crew Pairing

is found. Fahle et al. [2002] propose a constraint programming approach for a

column generation method used to solve the crew assignment problem.

To obtain integer feasible solutions the column generation method is often

combined with a branch-and-bound method or variable fixing heuristics. If pai-

rings are generated during the branch-and-bound or fixing heuristic, the method

is called branch-and-price or fix-and-price respectively. Ryan and Foster [1981]

propose a constraint branching rule to solve scheduling problems which are for-

mulated as set partitioning or covering problems. Vance et al. [1997] extends

this rule to the follow-on branching rule which is better suited for branch-and-

price methods. The follow-on branching rule requires that a pair of two flights

is either covered by one pairing in sequence or not covered by a same pairing.

This rule is also used in Desaulniers et al. [1999]. Klabjan et al. [2001b] proposes

the time-line branching rule which requires that in one branch the connection

time in the solution between two particular flights is below a threshold and in

the other branch it must be above the threshold.

Desaulniers et al. [1997] present a nonlinear multi-commodity network flow

formulation and apply the Dantzig-Wolfe decomposition resulting in a set parti-

tioning formulation for the RMP and several resource constrained shortest path

subproblems for generation of feasible crew pairings. The problem is then solved

by branch-and-price.

Vance et al. [1997] propose an alternative formulation for the crew pairing

problem. The problem is decomposed into two stages. In the first stage a set

of daily duties that covers all flights in the schedule is selected. In the second

stage crew pairings are built based on the selected daily duties. A Dantzig-Wolfe

decomposition is used to solve the problem with column generation resulting

in two subproblems, one for pairing generation and one duty set subproblem

ensuring that each flight is covered by exactly one duty. The formulation yields

a better LP-bound, but is harder to solve.

The minimal sit time between two flights (crew connection) is usually higher

than the minimal turn time between the same two flights (aircraft connection).

In the case that the crew stays on the aircraft between two flights, however,

the minimal turn time applies to both connections. Thus the feasible solution

space during crew scheduling is limited by the aircraft schedule and can lead to

suboptimal solutions. This limitation can lead to suboptimal solutions and is

3.3. Crew Pairing Optimization

therefore the main motive for integrating aircraft assignment and crew pairing

problems.

Cordeau et al. [2001] use Benders decomposition and branch-and-price to solve

an integrated model for aircraft assignment and crew pairing. They model the

aircraft routing problem as the master problem where optimality information

from the crew pairing subproblem is transfered to the master problem. Cohn

and Barnhart [2003], on the other hand, extend the crew pairing problem by

representing aircraft assignment solutions as additional variables in the problem.

Constraints ensure that only one variable representing an aircraft assignment

solution is selected. The problems is solved by branch-and-price with two pricing

problems, one for crew pairings and one for aircraft assignment solutions.

Mercier et al. [2005] consider an integrated model and use Benders decom-

position and branch-and-price to solve it. The master problems is in this case

the crew pairing problem and only feasibility information is transferred from the

aircraft assignment problem. Mercier et al. [2005] report that their approach can

solve larger problems in less computation time than the approaches proposed by

Cordeau et al. [2001] and Cohn and Barnhart [2003].

Klabjan et al. [2002] partially integrate aircraft assignment and crew pairing

problems. The two problems are solved sequentially, but with the crew pairing

problem first. Plane count constraints in the crew pairing problem formulation

ensure that a feasible aircraft assignment exists for the current crew pairing

solution. The times for flight departure are varied within certain time windows

in order to increase the number of feasible pairings and therefore to decrease

crew costs. The crew pairing formulation is solved by branch-and-bound with

column generation in the root node only.

Mercier and Soumis [2007] extend the integrated model for aircraft assignment

and crew pairing of Mercier et al. [2005] with time windows for flight departure.

Binary variables indicate the selected departure times and counting constraints

ensure that same departure times are for the aircraft assignment as well as crew

pairing. The problem is solved by Benders decomposition.

According to Clausen et al. [2009] most formulations for the crew recovery

problem in the literature assume that the flight schedule is recovered before.

Examples for such approaches are those of Stojković et al. [1998], Guo [2005],

Nissen and Haase [2006] and Medard and Sawhney [2007]. The approaches of

3. State Of The Art: Aircraft Assignment and Crew Pairing

Johnson et al. [1994], Lettovský et al. [2000] and Yu and Qi [2004] add the

possibility of cancelling flights during crew rescheduling. Finally, Stojković and

Soumis [2001], Stojković and Soumis [2005], Abdelghany et al. [2004] and Zhao

et al. [2007] explicitly model departure delays in crew rescheduling.

Lettovsky [1997] presented the first approach of true integrated recovery of

aircraft, crew and passengers. The integrated problem is decomposed into three

subproblems (one for each resource) which are synchronized by a master problem.

This master problem determines flight cancellations and delays. The problem

is solved by applying Benders decomposition. In Abdelghany et al. [2008] a

proactive recovery tool named DSTAR is used for integrated recovery of aircraft,

cockpit crew and cabin crew based on disruption forecast of a simulation model.

A rolling horizon over the schedule is used for recovery in multiple stages. At

every stage the problem is solved to optimality considering only a small subset

of flights.

3.4. Robust Scheduling of Aircraft and Crew Pairings

Regarding the robust aircraft assignment problem Ageeva [2000] propose increa-

sing the flexibility of schedules by maximizing aircraft swap opportunities. On

the flight string models for aircraft fleeting and routing by Barnhart et al. [1998],

they generate aircraft schedules where flight-strings meet each other as often

as possible in order to provide opportunities to swap sub-strings if disruptions

occur. By contrast, Lan et al. [2006] improve the stability of schedules by consi-

dering how changes in aircraft routes may reduce potential delay propagation

by aircraft connections. They use historical data about delay information and

increase the stability of aircraft routes by using slack in the schedule to absorb

possible disruptions. The proposed robust aircraft assignment model is solved

by a Dantzig-Wolfe decomposition. Wu [2006] changes a given aircraft assign-

ment solution by retiming flights in order to enlarge buffer times for flights with

higher delay probability. Whereas most authors use indicators to measure the

robustness of schedules, Fuhr [2007] proposes an analytic approach to evaluate

the propagation of delays in aircraft routes. The approach considers aircraft

routes only without crews and is computed approximately.

3.4. Robust Scheduling of Aircraft and Crew Pairings

Burke et al. [2010] are the first to consider stability and flexibility of aircraft

schedules simultaneously. The stability indicators (called reliability in the paper)

describes the probability of propagation of delays between flights. The flexibility

indicator is defined in terms of the number of aircraft swap opportunities. A

multi-objective memetic algorithm is proposed to improve stability as well as

flexibility of aircraft schedules simultaneously by re-routing aircraft and retiming

flights. A simulation study with real world schedules is performed to explore the

effects of the robustness objectives on the operational performance of schedules.

For the experiments a simulation model developed at KLM Royal Dutch Airlines

is used which includes a recovery module for aircraft (see Jacobs et al. [2005]).

The results show that the influence of the stability objective is dominant on the

operational performance of aircraft schedules. This study, however, does not

consider the interdependencies of aircraft and crews.

Regarding the crew scheduling problem, Shebalov and Klabjan [2006] propose

an indicator for flexibility based on task swaps as a recovery option for crew

schedules. This means that a crew whose arrival is delayed next flies a flight

with a later departure time than its originally assigned flight. A different crew,

called the move-up crew, then covers the flight of the disrupted crew. The paper

presents an optimization procedure to select a set of crew pairings with many

opportunities for crew swapping in addition to capture the crew cost. The au-

thors propose a new solution method based on Lagrangian relaxation and column

generation for the computationally difficult problem.

Several publications consider the stability of crew schedules. Ehrgott and Ryan

[2002] describe an indicator for stability of crew schedules, which considers the

difference between the slack duration and the expected duration of a delay bet-

ween each pair of flights. The stability indicator for a daily crew duty is then the

sum of those values for each flight pair in the duty. The daily crew pairing pro-

blem is formulated as a bicriteria problem with crew costs and stability indicator

as opposite optimization criteria. The problem is solved using the -constraint

approach. Thus the optimal crew costs are computed first and then in a second

step the stability of a schedule is maximized allowing an increase of % of the

crew costs in comparison to the optimal costs. The approach does not consider

interdepencies of pairings and aicraft nor does it consider the propagation of

delays.

3. State Of The Art: Aircraft Assignment and Crew Pairing

Schaefer et al. [2005] propose a stochastic extension to the deterministic crew

scheduling problem. A classical Dantzig-Wolfe decomposition of the crew pairing

optimization problem into a crew pairing generation problem and a crew pairing

selection problem is used, but for each crew pairing the expected cost is estimated

through simulation. Additionally to classical costs the crew pairings are penalized

according to an estimate of the delay propagation. The simulation software used

is described in Rosenberger et al. [2002]. One main assumption is that crews

never wait for late aircraft. Thus no interdependency between aircraft due to

crews changing aircraft is captured. Consequently, no interdependency between

crew pairings using the same aircraft is captured either. The solution times are

comparable with deterministic problems, only a constant effort for simulating

each crew pairing once is added.

Yen and Birge [2006] are the first to consider interdependencies of crew pai-

rings and aircraft. They model the crew pairing selection problem as a two-stage

stochastic programming problem. The first stage corresponds to the deterministic

crew pairing optimization problem. The second stage computes the propagation

of delays caused by interdependencies between aircraft routes and crew pairings.

The proposed branch-and-bound method starts with a given set of feasible crew

pairings and branches on flight pairs with high delay propagation. During the

solution process, however, an integer set partitioning subproblem must be sol-

ved frequently. These aspects lead to very high solution times, thus only small

problem instances can be solved.

Mercier et al. [2005] propose an integrated aircraft assignment and crew sche-

duling problem incorporating an indicator for stability based on the available

ground time for crews during an aircraft change. Aircraft changes with ground

time below a threshold are called restricted. Schedules with less restricted air-

craft changes are assumed to be more stable; therefore a penalty value for such

aircraft changes is used. Two Benders decomposition methods combined with

branch-and-price are proposed to solve the integrated model. Both methods

lead to very high solution times. The proposed indicator for stability does not

consider any recovery actions nor explicit delay propagation; thus only a local

evaluation of the aircraft changes is carried out.

AhmedBeygi et al. [2008] redistribute slack in an existing aircraft and crew

schedule in order to reduce propagation of delays by retiming flights. An optimi-

3.4. Robust Scheduling of Aircraft and Crew Pairings

zation model is therefore formulated which considers the propagation of delays

and minimizes their probability. The computational results show opportunities

for improvement of robustness without increasing planned costs.

Weide et al. [2009] propose to solve the integrated aircraft assignment and

crew scheduling model heuristically by solving the two problems iteratively using

a shared objective function. A stability indicator is used to penalize restricted

aircraft changes according to the duration of slack during such an aircraft change.

The solution time can be dramatically reduced unlike on the integrated model of

Mercier et al. [2005]. The iterative approach leads to a set of aircraft and crew

schedules with different relation between planned costs and an indicator value

for schedule stability. The authors highlight that it is easier for a decision maker

to select a solution with the preferred relation afterwards instead of assigning

monetary costs to the stability indicator. The proposed indicator for stability,

however, is very difficult for a decision maker to interpret, because it does not

measure delay propagation nor does it use historical data. The authors compare

the iterative approach with several optimization methods and extend the model

with flexible departure times. They do not, however, evaluate and compare

the proposed indicator for schedule stability with other approaches to increasing

robustness.

4. Required Work

Study of the literature on improving robustness of crew and aircraft schedules

highlights several important aspects. Several authors use simulation studies to

evaluate the quality of approaches for robust scheduling, but still there is no fra-

mework for evaluation and comparison of approaches. Many authors highlight

the importance of interdependencies between crews and aircraft for the robust-

ness of both schedules, but a full integrated formulation for both scheduling tasks

is very difficult to solve, see Mercier and Soumis [2007]. Most approaches to in-

corporating historical data during scheduling only consider a simplified model of

delay propagation between aircraft and crews in order to reduce the complexity

of the scheduling problem. Yen and Birge [2006] propose an exact model for

delay propagation, which can be solved for small problem instances only. There

are no approaches in the literature which focus on stability of crew duties, al-

though disruptions of crew duty rules can lead to major disruptions of airline

schedules. There are only a few publications on flexibility of airline schedules

and only one which explores the trade-off between stability and flexibility of air-

line schedules. To summarise, research is required into methods of evaluation of

robust scheduling approaches, more exact indicators based on delay propagation

between aircraft and crews, stability of crew duties, and additional approaches

for increasing flexibility of airline schedules.

From this study of the state-of-the-art literature we select three objectives

for this research. Firstly, we propose to develop a new more exact approach

to measuring delay propagation during simultaneous scheduling of aircraft and

crews. Secondly, we need a method to compare the new approach with existing

approaches for robust scheduling. And thirdly, we shall show in this chapter that

we need to improve the existing scheduling methods in order to cope with addi-

tional complexity induced by the consideration of uncertainty in the scheduling

problems.

4. Required Work

The main idea for the new approach to measuring delay propagation more

exactly during scheduling of aircraft and crews is to solve an integrated stochastic

crew and aircraft scheduling problem by decomposing this problem into separate

problems of crew and aircraft scheduling. An analogous approach proposed by

Weide et al. [2009] for a deterministic robust aircraft and crew scheduling leads

to promising results. The additional complexity induced by the consideration of

historical data cab be managed by improving well-known scheduling methods.

An additional advantage of extending known scheduling methods is that the new

approach can than be compared with existing approaches more easily.

Such a comparison of different approaches needs to consider two main aspects.

Firstly, the evaluation of the operational quality of the planned schedules, which

involves punctuality and recovery effort. A simulation model can be used to

estimate the quality of airline schedules and has the advantage that possible

aircraft and crew schedules created with different approaches can be evaluated

using different assumptions about the reality, e.g. winter and summer conditions.

The second aspect is the comparison of the approaches based on their predic-

tability and efficiency. In this work we focus on stability of aircraft and crew

schedules and therefore need a framework for evaluation of different approaches

for stability, where the recovery effort is roughly estimated rather than computed

exactly.

The resulting stochastic problems for crew and aircraft scheduling need to be

solved fast in order to be able to solve integrated problems of practical size in

an acceptable time. Thus we propose to solve the resulting stochastic problems

heuristically using a state-of-the-art branch-and-price method. The concepts for

such methods are well described in literature, but an efficient implementation

is still highly significant for the quality of results. Moreover, main concepts of

these methods need to be modified and extended to solve the stochastic problems

efficiently. The extension of well-founded optimization methods for our purposes

has the huge advantage that our research results can be adapted by a large

research community as well as commercial software vendors.

The remainder of this work is organized as follows. In Chapter 5we present

the concept of the branch-and-price solution method with our extensions and

modifications as well as results of extensive computational experiments. Based

on this framework an approach to stochastic optimization of aircraft and crew

schedules is developed in Chapter 6. Chapter 7presents a concept of the evalua-

tion of the approaches for robust scheduling as well as results of comprehensive

simulation experiments. In Chapter 8we present an approach to rescheduling

aircraft and crews together with results of a simulation study. In Chapter 9we

give a summary and conclusions of this work.

5. A Branch-and-Price-and-Cut

Framework

In this chapter we introduce a column generation based solution method for set-

partitioning problems in the airline industry. We introduce several extensions to

the state-of-the-art methods, which are crucial to achieving high solution quality

in short solution time. Finally, extended computational experiments are perfor-

med to analyse the effects of all extensions on the results. All solution methods

for integrated robust scheduling and integrated rescheduling on the day of ope-

rations presented in this work are based on this solution framework. The main

motive for the method, however, is efficiently to solve crew pairing optimisation

problems. Thus the extended computational experiments are performed for the

crew scheduling problem only.

This chapter is organized as follows. The first section presents the set partitio-

ning formulations of the tactical and the operational crew scheduling problem as

well as an outline of the solution method based column generation. The second

section presents the formulation of the subproblem for pairing generation and

the corresponding solution method. The third section presents the branching

strategies and the fourth presents the valid inequalities used in the proposed

branch-and-bound-and-cut method. Section 5.5 describes the application of the

solution method presented in this chapter to a set partitioning formulation of the

aircraft assignment problem. The last section presents extensive computational

results of the new method for the tactical crew scheduling problem.

5.1. The Formulation of the Crew Pairing Problem

The airline crew pairing problem is originally formulated as an integer, nonlinear

multi-commodity network flow problem (see Desaulniers et al. [1997]). Normally

5. A Branch-and-Price-and-Cut Framework

a Dantzig-Wolfe decomposition is applied to avoid the nonlinear constraints re-

sulting in a set partitioning formulation, where a cost-optimal set of legal pairings

has to be selected to partition all available flights.

Equations (5.1) – (5.3) represent the set partitioning formulation of the crew

pairing problem, where a set of flights must be partitioned by a set of crew

pairings represented by the binary variables xp. Let Fbe the set of all flights

and Pbe the set of possible crew pairing variables, then P(f)describes the set

of crew pairings covering flight f. Constraints (5.2) model the requirement that

each flight be covered by exactly one crew pairing.

p∈P

cpxp→min crew pairing problem (5.1)

p∈P(f)

xp= 1 ∀f∈F(5.2)

xp∈ {0,1} ∀p∈P(5.3)

The formulation of the crew recovery problem differs from the planning formu-

lation due to restrictions on the availability of crews. At the time recovery begins

the scheduled crews as well as standby crews are all at certain airports and have

already consumed part of their resources relevant for work-time regulations, like

duty working time and flying time. Moreover, we need to reschedule the existing

and new crews in such a way, that all existing pairings after the recovery period

are continued by same crew considering all work-time regulations. These addi-

tional restrictions can be formulated by adding availability and flow constraints

to the formulation above. Let SPbe the set of available crew starting positions

(earliest time and airport) and EPthe set of available ending positions (latest

time and airport) at the end of the recovery horizon, then P(a)(P(e)) is the set

of all pairings, which start at the starting position s(end at the ending position

e). The crew availability constraints (5.4) then model that each starting position

is allowed to be covered once at most and the crew flow constraints (5.5) model

5.1. The Formulation of the Crew Pairing Problem

Number of

night hours

in the duty

Maximum

duration of the

duty

≤2 14h

≤4 13h

>4 12h

Actual

duration of

the duty

Minimum

duration of the

night rest

≥12h 14h

≥10h 12h

<10h 10h

Table 5.1.: Crew Scheduling Rules

the requirement that crews must be available at certain airports at the end of

the recovery horizon.

r∈P(s)

xp≤1∀s∈SP(5.4)

r∈P(e)

xp≥1∀e∈EP(5.5)

For simplicity all starting and ending positions are enumerated, but it is of

course also possible to aggregate them and to increase the right-hand side of the

corresponding constraints. The requirement that a certain crew must end at a

certain ending position at the end of the recovery horizon can be modelled by

forbidding in the pricing algorithm the generation of pairings with non-matching

starting and ending positions.

Each crew pairing has to start and end at the same crew base. A crew pairing

consists of several daily duties and night rests between them. During a duty

a minimal connection time between each consecutive pair of flights is needed

represented by the minimal sit time. The minimal sit time is needed for the crew

to prepare the aircraft for the next flight and eventually to change the aircraft.

The minimum duration of the night rest depends on the actual duration of the

previous duty. The maximum duration of a duty depends on the intersection of

the duty with the night. The actual values of the rules used in this work are

shown in Table 5.1.

The objective of the crew pairing problem is to minimize the number of daily

duties, independently of the duration of those duties. The formulation presen-

ted here is often solved by a column generation based method, where a linear

5. A Branch-and-Price-and-Cut Framework

relaxation of problem (5.1) – (5.3) is the RMP and legal crew pairings are ge-

nerated using resource constrained shortest path subproblems (see Desaulniers

et al. [1997]). Let µ∈Rbe the dual variable associated with the partitioning

constraint (5.2), cpthe cost for crew pairing p, and F(p)the set of flights covered

by pairing p. Then, the reduced cost of the crew pairing pare defined as follows

cp=cp−X

f∈F(p)

µf−σs(p)−θe(p),(5.6)

where σs(p)and θe(p)are the dual variables associated with the rescheduling

constraints (5.4) and (5.5). If those constraints are not part of the problem, the

corresponding duals are omitted in the computation of the reduced costs.

Each crew pairing with negative reduced cost may improve the current solution

of the RMP. This means all crew pairings in the RMP have non-negative reduced

cost. The goal of the pricing subproblem is to generate new crew pairings with

negative reduced costs. A crew pairing generation network is used to represent

all possible crew pairings implicitly, where each valid path is a valid crew pairing.

By solving a resource constrained shortest path problem based on the network

several crew pairings with negative reduced costs are found and added to the

RMP. If no crew pairings with negative reduced costs can be found, the column

generation algorithm terminates.

The RMP is usually solved using the primal or dual simplex algorithm or the

interior point method (IPM). One important implication for the choice of the

solution method is the presence of multiple dual optimal solutions due to high

degeneracy of linear relaxations of the set partitioning problem. If the RMP is

solved by a simplex method, an essentially random vertex of the face of optimal

dual solutions is selected, whereas the IPM returns the relative interior point

of this face. Bixby et al. [1992] and Barnhart et al. [1998] note that the IPM

may lead to a better convergence of the column generation method because the

interior dual solution may give a better representation of the optimal dual face.

This note is supported by Jans and Degraeve [2004] who determine that a high

number of columns added to the RMP actually do not change its objective value

if a simplex method is used. The disadvantage of the IPM is that it cannot be res-

tarted using the solution from the last column generation iteration. Bixby et al.

5.1. The Formulation of the Crew Pairing Problem

Branching

Node Selection

Lower Bound Computation

Generate Columns

Solve the Restricted Master

Problem

Manage Inequalities

Fixation

Figure 5.1.: Branch-and-Price-and-Cut Framework

[1992] present a hybrid method where an IPM is used for the first five iterations

of column generation and a primal simplex method is used for the remaining

iterations. Bixby et al. [1992] report substantially reduced and more predictable

total computation time. Moreover, the state-of-the-art implementations of the

IPM available today make use of multiple processors and are therefore often dra-

matically faster on modern multi-core computers. For this reason we use the

IPM to solve the RMP instead of a hybrid strategy.

Our solution approach to the crew pairing problem is a combination of column

and row generation for the linear relaxation of the problem (5.1)-(5.3) embedded

in a branch-and-bound method with a constraint branching strategy. Figure 5.1

shows an overview of the method. The important parts of this method are

presented in the following sections of this work, which is organized as follows. In

Section 5.2 we describe various possibilities to model the pricing subproblem as

a network. We solve the pricing subproblem by a label setting algorithm with

a new backtracking scheme. The constraint branching strategy and the new

search strategy used in our algorithm are presented in Section 5.3. In Section 5.4

we describe the separation of subset-row inequalities and the generation of new

pairings considering such inequalities. In section 5.5 we describe the application

of the solution framework developed in this chapter to the aircraft assignment

problem. Finally in Section 5.6 we present results of extensive computational

experiments based on the crew pairing optimization problem.

5. A Branch-and-Price-and-Cut Framework

5.2. Pairing Generation

The quality of the overall results as well as the total solution time is highly

dependent on the implementation of the pricing subproblem. In most cases the

generation of new pairings consumes the most time due to complicated rules

and the high number of calls to the pricing subproblem. Further, the selection

of the columns may dramatically improve the convergence of the whole column

generation process. Known improvement techniques are multiple pricing, where

several columns are generated within each call to the subproblem, and random

pricing, where a part of returned columns is selected randomly. The motive for

the random selection is to generate more diverse columns. A higher diversification

of columns may improve the convergence of column generation by cutting off more

solutions at the same time and by indicating new search directions.

The aim of the pricing subproblem is to find the crew pairing with the lowest

reduced costs. This can be modelled as a RCSP. For an extensive survey on

RCSP and corresponding solution approaches we refer to Irnich and Desaulniers

[2005]. Three fundamental approaches are used in the literature to solve the

RCSP. The Lagrangian relaxation methods for the RCSP assume that only the

resource consumption of a whole path is constrained. Constraint programming,

on the other hand, may be used to model a wide range of complex constraints.

The dynamic programming method is widely used to solve RCSP in a column

generation context and many improvement techniques to speed up the solution

process are already known (see i.e. Irnich and Desaulniers [2005]). Additionally,

all crew rules described in this work can be modelled as resource restrictions

thus; we choose a label setting algorithm as a solution method for the pricing

subproblem.

5.2.1. Modelling the Pricing Subproblem

In our application possible connections between flights depend on the duration

of the previous duty. An explicit representation of connections in the network

would anyway require validation steps and possess many more arcs than the

implicit representation. Thus we choose a time-space flight-based network to

model the pricing subproblem (see Section 3.3 or Desaulniers et al. [1999]). The

implicit consideration of duties allows the algorithm to increase the search space

5.2. Pairing Generation

crewbase

airport A

airport B

time

source

sink

flight start

flight end

sign-on

sign-off

flight arc

waiting arc

Figure 5.2.: Flight-based Time-Space Network for Pairing Generation

dynamically, dependent on the number of good pairings found. Moreover, the

implicit consideration of all duties allows better methods for diversification of

generated pairings. Most resource restrictions in our application are based on

time. Thus if a path cannot be propagated to a node because of a violated

resource restriction that is based on time, nor can this path be propagated to

any other node that is later in time either. The time-space network models

this relation implicitly, whereas using the connection-based network this relation

must be considered by the search algorithm.

The graph is modelled as a directed acyclic network H= (N, A)with source

sand sink t. Each flight is represented by an arc (i, j)∈Aand two nodes, one

flight start node i∈Nand one flight end node j∈N. Each node is characterized

by a corresponding time (arrival or departure) and an airport. Each node has

at most one outgoing waiting arc to the next node in time at the same airport.

We create different networks for each crew base. Thus only one airport at each

network is the crew base. Each flight start node at the crew base is connected to

the network source node, and each flight end node at the crew base is connected

to the network sink node. Each path from the network source node s to the

network sink node t is a potential crew pairing satisfying the rule that each crew

pairing must start and end at the same crew base. The network structure also

guarantees that there is no path connecting two flights with different arrival and

departure airports. Night rests as well as duty breaks are represented by one

or more waiting arcs at one airport. Figure 5.2 shows an example of the used

time-space network.

5. A Branch-and-Price-and-Cut Framework

The additional rescheduling constraints in the RMP require additional star-

ting and ending arcs, which are very similar to the sign-on and sign-off arcs. The

flights that may be performed by each crew as the first flight in the recovery

period can be enumerated. Each flight from this enumeration is connected to

the source node by a starting arc. All starting arcs from this set are associated

with the same constraint in the RMP. Analogously, the ending arcs connect the

possible last flights of an ending position to the sink node. The sign-on and

sign-off arcs represent reserve/standby crews only. The pricing subproblem is

organized in one network per crew base with the possibility of generating pai-

rings for existing crews (following the starting arcs) as well as new reserve crews

(following the sign-on arcs). Both types of pairings can finish with an ending arc

as well as a sign-off arc. I.e. an existing crew can perform an unscheduled sign-off

during the recovery period, and a reserve crew can be scheduled to continue a

pairing after the recovery period. The validation of pairing rules after the reco-

very period can be performed locally in the pricing subproblem when generating

new columns. Moreover, it is easy to penalize variables which schedule crews to

other than original pairings after the recovery period during pairing generation,

by associating each ending arc with its original crew.

5.2.2. New Label Setting Algorithm with Backtracking

To find a set of pairings with negative reduced costs we use a label setting

algorithm that basically iterates over arcs and constructs paths from source s

until sink tis reached. The outline of this method is described in Algorithm 5.1.

Feasible paths from source sto each node are represented by labels. Each label

lk∈Ljat node jrepresents a feasible path p= (s, . . . , i, j)and is linked with

its predecessor label lf∈Liat node i. Besides the linking each label also stores

the information about the reduced costs and the consumption of each relevant

resource r∈R. The consumption of resources by any feasible path is bounded by

maximal and minimal values. A label can only be propagated to the next node

if the consumption of any resource at the label and the additional consumption

by the arc are less than a given maximal value. The minimal waiting times

must be reached before a label can be propagated over a flight arc. A label is

propagated over an arc by creating a new label at the target node with a link

5.2. Pairing Generation

Algorithm 5.1: Label Setting Algorithm for Pairing Generation

Data: N;/* list of nodes */

NV={0};/* set of nodes to start search */

/* search space extension loop */

2while NV6=∅and not enough labels at sink node do

n= max(NV);

NV=NV{n};

if nhas processed labels then

propagate success status of labels to predecessor labels ;

if nhas unprocessed labels then

/* network search loop */

8foreach c∈N≥ndo

if shas new labels then

NV=NV∪ {s};

DominanceTest(s) ;

12 SortLabels(s) ;

/* label setting loop */

foreach outgoing arc in sdo

t= target node of arc ;

15 foreach non-dominated label in sdo

16 if thas memory for new label then

mark label as processed ;

if label can be propagated then

19 propagate label to target node ;

to the predecessor. The resource consumption of the new label at the target

node is the sum of the resource consumption in the last label and at the current

arc. Since duties and legal connections are implicitly represented in this network,

several resources are only relevant to parts of a full crew pairing: the resource

waiting time is set to zero at new labels at each flight arc, and all resources

relevant for duties are set to zero after the waiting time exceeds the maximal sit

time. In the case of crew rescheduling the consumption of all resources also needs

to be considered at the starting and ending arcs, which represent the resource

consumption of the pairings and duties before and after the recovery period. An

5. A Branch-and-Price-and-Cut Framework

Resource Relevant Rules Checked at

Waiting time since last flight min / max sit time, flight, waiting

min / max rest time and ending

Number of duties max number of duties flight and

in the pairing ending arcs

Flying hours of max flying hours flight and

the current duty in duties ending arcs

Flying hours of max flying hours flight and

the pairing in pairings ending arcs

Duration of the max duration of duties, all arcs

current duty max rest time

Duration of the pairing max duration of pairings all arcs

Table 5.2.: Relevant Resources

overview over relevant resources, the relevant rules and the arcs where these rules

are checked is given in table 5.2.

Lines 8 – 19 of algorithm 5.1 describe the core of the label setting algorithm.

The algorithm basically iterates through all nodes in Nin a topological order,

starting at node n, and propagates selected labels to all successor nodes. The

propagation of all labels is very time and memory consuming and prohibitive

therefore already for small problem instances. A well-known way of avoiding

the propagation of all labels and to find the shortest path anyway is the use

of dominance tests. A label liis dominated by another label lkif the reduced

cost and consumption of each resource at label liare greater than at label lk

or equal. The procedure DominanceTest(s) tests all labels for dominance and

marks dominated labels. Only non-dominated labels are propagated to successor

nodes (see line 15).

We restrict the number of labels at each node to handle memory consumption

of our algorithm. Thus the total number of possible labels LTis defined. Given

the actual number of labels |L|the maximal number of labels for the node nis

|Ln|=LT− |L|/N≥n. This number is evaluated during the algorithm (see

line 16). Since only a subset of labels is propagated we sort the labels at each

5.2. Pairing Generation

node through procedure SortLabels(in s) to propagate only the most promising

labels (see line 12). We test two sorting strategies. The first sorts the labels

according to the reduced cost, and thus the columns with least reduced cost are

propagated first. The second strategy first categorizes the labels according to the

last two flights in the path and then propagates the least reduced cost columns

from each category. The motive for the second strategy is to generate more

diverse columns with negative reduced cost and thus to improve the convergence

of the whole column generation method.

To improve the speed of the algorithm, it is possible to consider only a subset

of all resources in the dominance tests. With such non-exact dominance tests

the pricing problem is solved heuristically, because actual valid shortest paths

could be marked as dominated. But we need the actual shortest paths only at

the end of column generation to show that no columns with negative reduced

costs exist. In the context of column generation it is more important quickly to

generate many different columns with negative reduced costs. To reach this goal

we propose a backtracking search algorithm. At the beginning a classical search

is performed with non-exact dominance tests and relatively small total number

of possible labels LT. In case only few columns with negative reduced costs are

found the algorithm continues using the labels not propagated yet (loop in line

2). Therefore during the search each label that is considered for propagation is

marked as processed. After the network search (loop in line 8) terminates the

nodes of the network are visited in the reverse topological order and for each

label the success status is propagated back to predecessor labels.

The success status of a label indicates whether this label was extended to a crew

pairing with negative reduced costs successfully. At the first node with unproces-

sed labels the network search starts again. But this time exact dominance tests

are performed comparing the already propagated labels with the unprocessed

labels at this node. Remember that only non-dominated labels were propagated

in the first search using non-exact dominance tests. This time unprocessed labels

are discarded if they are exactly dominated by an already propagated label with

false success status. After backtracking, the maximal number of labels per node

is considered again, but the labels from previous network search runs can be

reused, except at the sink node of course. In this way several backtracking steps

can be performed until enough columns are found or the complete search space

5. A Branch-and-Price-and-Cut Framework

is visited. For larger problem instances additional termination criteria should be

used to avoid excessive running time.

5.3. Finding Integer Solutions

Column generation is suitable to solving a relaxation of the problem (5.1)–(5.3)

and obtain a lower bound on the optimal objective value. Besides the fractional

solution, the main problem is that the generated columns may not be sufficient

to finding an optimal or even feasible solution for the original problem. Thus

column generation must be embedded in other methods. One common method

for this purpose is branch-and-bound, where column generation is used to solve

the relaxation of the problem in each node. The whole method is then called

branch and price. Barnhart et al. [1998], Desaulniers et al. [1997] and Vance

et al. [1997] apply branch and price methods to the crew pairing problem.

After computing a lower bound using the column and row generation frame-

work a branching decision is performed for the current solution of the RMP.

The resulting nodes are described by the indexes of all relevant columns, the

dual optimal solution and branch-and-bound path-specific termination criteria.

In this framework the lower bound is not computed exactly, to avoid the tailing

off effect of column generation. The computation of the lower bound terminates

when the lower bound stabilizes, thus not significantly changing for six iterations

of column generation. It is to be noted that this turns any search strategy into

a heuristic.

The proposed framework incorporates branching strategies based on follow-on

decisions. Thus after the termination of the column generation method for each

follow-on (r, s)the score is defined as follows

score(r, s) = X

p∈P(r)∩P(s)

xp.(5.7)

For branching we select a follow-on with a score near the target score stand

within the minimum and maximum values smin and smax:

(r, s) = argmin

(r,s)∈F×F

|st−score(r, s)|,s.t. smin < score(r, s)< smax (5.8)

5.3. Finding Integer Solutions

The values for st, smin and smax describe the branching strategy. The bran-

ching decisions can be easily realized. In the resulting 1-branch all columns which

cover ror s, but not both flights in succession, are deleted. In the 0-branch all

columns which cover rand sin succession are deleted.

In the case of crew rescheduling an additional branching strategy based on the

assignment of a crew to certain flights is possible. It is to be noted the problem

can be solved by assigning each flight to a crew, i.e. any fractional solution

contains a flight fand a starting position swith following score

0< score(f, s) = X

p∈P(f)∩P(s)

xp<1(5.9)

A branching decision is then performed on the condition, that flight fmust be

covered by the crew starting at position sby deleting all columns with flight f

but without starting position sin the 1-branch and deleting all columns covering

flight fand starting position sin the 0-branch. Additionally, the generation

of such columns in the pricing subproblem is forbidden. This can be easily

realized by storing the starting position for each label and checking this constraint

when visiting a flight-arc. Branching is performed based on the score score(f, s),

analogously to the follow-on branching strategy. It is possible to combine this

branching strategy with follow-on branching, i.e. to compute the scores for the

flight and starting position combinations as well as for the follow-ons at the same

time and then to select the branching strategy as well as the actual branching

decision on the score. We achieve good results with the strategy of performing

several branching decisions on most fractional combinations of flights and starting

positions at the beginning of the method and then to switch to the least fractional

follow-on branching.

During the algorithm additional information about forbidden and fixed flight

pairs is saved in the resulting node. When selecting a new node for exploration

the pricing module is updated with the branching history of this node. Each label

in the label setting algorithm additionally stores the last flight of the path, if this

flight is part of any follow-on in the branching history. An additional feasibility

check is then performed at each flight arc, indicating whether the current flight

5. A Branch-and-Price-and-Cut Framework

and the last flight of the path are allowed in succession. We define two default

branching strategies in our framework:

•Most fractional: st= 0.5,smin = 0.4and smax = 0.65

•Least fractional: st= 0.8,smin = 0.7and smax = 0.9

According to these two branching strategies we present two different search

strategies:

•branch-and-price: Always branch on most fractional follow-on.

•dive-and-price: At nodes with a depth smaller than five perform branching

on the most fractional follow-on. At deeper nodes always fix the least

fractional follow-on.

After branching is performed the resulting nodes are added to the active node

list. The next node to search is selected from this list with a delayed best bound

strategy. This means the current 1-branch is selected if the lower bound of this

branch is not greater than d= 5% than the best bound of all other nodes in the

active node list. New columns are only generated if the lower bound increases,

independently of the branching strategy.

Vance et al. [1997] suggest fixing follow-ons with score 1.0. We extend this

suggestion to the History Fixing strategy. Thus a follow-on is fixed if it has a

score of 1.0 in ten consecutive iterations of column generation. The information

about the follow-on scores is inherited to the child nodes during branching. This

means in particular that this strategy considers the development of the scores

for each path in the branch-and-bound tree.

We prune nodes if their lower bound is greater than a newly-found upper

bound. This kind of pruning turns the branch-and-price method into a heuristic,

because we do not generate all possible columns when exploring a node, but

terminate when the lower bound does not change for several iterations.

When no follow-ons for branching can be found, a minimum number of columns

or a maximum depth of the node is reached, the node is added to the final

leaves list. A fixed number of leaves is solved using a standard mixed integer

programming (MIP) solver. We solve a leaf if after a branching or fixing decision

the final leaf has the best lower bound of all active nodes and other leaves.

5.4. Subset Row Inequalities

Additionally, further leaves are solved until the desired number of explored leaves

is reached or all leaves are cut off after the branch-and-bound terminates.

5.4. Subset Row Inequalities

Valid inequalities can be used to strengthen the formulation of the relaxation

solved by column generation. Pure cutting-plane methods try to find the convex

hull of the problem by generating valid inequalities iteratively. More promising is

the combination of branch-and-bound and generation of valid inequalities. Valid

inequalities can help to prune nodes in the branch-and-bound tree by improving

bounds. They can also lead to better branching decisions by cutting off fractional

solutions.

Jepsen et al. [2008] describe a branch-and-cut-and-price algorithm for the

vehicle-routing problem. The authors successfully combine row and column ge-

neration for a set partitioning formulation of the problem. They introduce the

Subset-Row (SR) inequalities, which are Chvátal-Gomory rank-1 cuts inspired

by clique and odd hole inequalities for the set packing problem. SR inequalities

are specifically linked to the rows of the set packing problem and given by

j∈J$1

i∈S

aij%≤|S|

k,∀S⊆I, 2≤k≤ |S|(5.10)

where Sis a subset of all rows I.Jepsen et al. [2008] focus on inequalities defined

by exactly three rows that are given by

j∈J(S)

xj≤1,∀S⊆Iand |S|= 3 (5.11)

where J(S)⊆Jis the subset of columns covering at least two rows in S. The

class of inequalities defined by (5.11) is clearly a subclass of the clique inequalities.

We call this class of inequalities SR3.

In the pricing subproblem the dual variable µq≤0of the cut qdefined by

three rows Sq={r1, r2, r3}must be added to any path covering two of the rows

in Sq. This can be easily done by computing the number of visited rows for each

5. A Branch-and-Price-and-Cut Framework

cut during the generation of the path. A large number of SR inequalities can

slow down the pricing subproblem.

In this work we consider the class of inequalities described in (5.11) with the

additional requirement that any subset of rows contain both rows of a follow-on

with fractional score. Thus only a small number of possible inequalities need

be enumerated by the separation algorithm and considered during the pricing

subproblem. The separation of SR3inequalities is incorporated into the column

generation method, rather than the branch-and-bound method. Basically, in-

equalities are separated for each new solution of the RMP. In the root node,

however, the separation of inequalities is started after the lower bound stabilizes.

5.4.1. Inequality Separation

The separation algorithm is actually an enumeration of all combinations of frac-

tional follow-ons with a third row. Thus for each follow-on (r, s)with a score

0< Arsx < 1there exists a set of inequalities defined by





X

j∈J(S)

xj≤1, S ={r, s, p} | ∀p > s >



.(5.12)

From this set we select at most one inequality using the following quality mea-

sures. We select only inequalities with a violation v(C)>0, which is given

v(C) = X

j∈C

xj−1,(5.13)

where C is the set of columns covered by the inequality. The violation simply is

the amount by which the left-hand side of the inequality exceeds the right-hand

side. If there are several inequalities with positive violation for a follow-on, the

inequality with the greatest Euclidean distance between the hyper-plane defined

by the inequality and the LP solution is selected. This distance is given by

δ(C) = v(C)

p|C|(5.14)

5.4. Subset Row Inequalities

It is easy to see that the violation is normalized by considering the number of

columns covered by the inequality.

Especially, we also consider existing SR3inequalities as a third row for new

SR3inequalities. After the separation of new inequalities all inequalities from

previous iterations with non-negative duals that are not part of any other in-

equality are deleted.

5.4.2. Generating new Pairings with SR3Inequalities

For the consideration of SR3inequalities in the pricing subproblem we introduce

two additional resources at the labels. The first additional resource is an array

CPdescribing the inequalities where one of the three rows is already part of the

path represented by the label. The second resource is an array CFdescribing

the inequalities that are finally covered by the path at the current label. The

resource CPis propagated to new labels and updated at flight arcs. The resource

CFis not propagated to new labels. Instead this resource is checked during the

column creation at the end of the pricing method and covered inequalities are

added to the new column.

Assume we have a function SR(r)specifying for a row r(a flight or a SR3

inequality) which SR3inequalities contain this row. Then at each flight-arc new

potential and final SR3inequalities for the current path are computed using

the procedure described in Algorithm 5.2. Basically, the algorithm checks for

each inequality associated with the corresponding row of the current flight arc,

whether it is already a potential inequality for this path, i.e. part of the resource

CP. In this case the inequality is removed from the potential list CPof the

target label, the associated duals are added to the reduced costs of the target

label and the list CFof found inequalities is updated. If the inequality is not

yet a potential inequality, it becomes one at the target label. This procedure has

to be repeated for each found inequality, considering further SR3inequalities

containing the found inequality as the third row (lines 12 – 21).

5. A Branch-and-Price-and-Cut Framework

Algorithm 5.2: Considering SR3Inequalities in Pairing Generation

Data: CP;/* potential SR3inequalities at current label */

Data: CF

new ;/* covered SR3inequalities at target label */

Data: CP

new ;/* potential SR3inequalities at target label */

Data: Ctmp ;/* temporary queue of SR3inequalities */

Data: f;/* corresponding flight of current arc */

foreach c∈SR(f)do

if c∈CPthen

Add(CF

new, c);

Add µcto reduced cost of target label ;

Push(Ctmp, c) ;

else

Add(CP

new, c);

/* Consider SR3inequalities covering found inequality */

12 while Ctmp 6=∅do

r = Pop(Ctmp) ;

foreach c∈SR(r)do

if c∈CP

new then

Remove(CP

new, c);

Add(CF

new, c);

Add µcto reduced cost of target label ;

Push(Ctmp, c) ;

else

21 Add(CP

new, c);

5.5. Application of the Framework to the Aircraft

Assignment Problem

The aircraft assignment problem and that of aircraft recovery can be formulated

as multi commodity flow problems or, analogous to the crew recovery problem,

as set partitioning problems. Usually greater success is achieved with the multi

commodity flow problem formulation in combination with a commercial state-of-

the-art solver. But the set partitioning formulation posses greater possibilities

for consideration of path-based restrictions. We present in this section how such

a set partitioning formulation for aircraft assigning and recovery can be solved

5.5. Application of the Framework to the Aircraft Assignment Problem

with the branch-and-price-and-cut framework. We do not consider maintenance

constraints, although it is straight forward to represent them in the pricing sub-

problem. The objective of the aircraft assignment problem in this work is always

to minimize the sum of aircraft route costs. The actual costs of the aircraft

routes depend on the purpose of the optimization, either recovery on the day

of operations or robust scheduling during tactical planning, but can always be

computed in the pricing subproblem for each variable individually.

Equations (5.15) – (5.19) represent the set partitioning formulation of the

aircraft assignment problem, where a set of flights must be partitioned by a set

of aircraft routes represented by the binary variables yr.R(f)describes the set

of aircraft routoes covering flight f. Constraints (5.16) model the requirement

that each flight must be covered by exactly one aircraft route. Let SRbe the set

of available aircraft starting positions (earliest time and airport) and ERthe set

of available ending positions (latest time and airport) at the end of the planing

or recovery horizon, then R(a)(R(e)) is the set of all aircraft, which start at

the starting position s(end at the ending position e). The aircraft availability

constraints (5.17) then model that each starting position is allowed to be covered

at most once and the aircraft flow constraints (5.18) model the requirement that

aircraft be available at certain airports at the end of the planing or recovery

horizon.

r∈R

cryr→min aircraft assignment problem (5.15)

i∈I(f)X

r∈R(f)

yr= 1 ∀f∈F(5.16)

r∈R(s)

yr≤1∀s∈SR(5.17)

r∈R(e)

yr≥1∀e∈ER(5.18)

yr∈ {0,1} ∀r∈R(5.19)

Both branching strategies, the follow-on branching as well as the assignment

of flights to aircraft, are applicable to solving this problem. Moreover, all other

5. A Branch-and-Price-and-Cut Framework

aspects of the method, like the consideration of inequalities and fixing strategies,

are based on the set-partitioning constraints (5.16) and can be reused without

modification.

The pricing subproblem is also modelled as one flight-based time-space network

and solved by the same dynamic programming method. For the problem of

aircraft routing, however, the pricing subproblem corresponds to a shortest path

problem, because there are no resource constraints. Our label setting algorithm

is capable of solving the problem in polynomial time. The dominance tests are

only based on reduced costs and therefore at each node only one label needs to

be propagated. Due to the nature of the problem, the used network is always

acyclic and the nodes can be ordered in a topological order. Thus we need to

visit each node in the network only once in a topological order and to propagate

the shortest path label. This dynamic programming algorithm is called reaching

algorithm and is described in [Ahuja et al.,1993, pp. 107]. We extend the

algorithm, however, by propagating more than one label at each node in order

to generate multiple columns in each iteration.

5.6. Computational Experiments

The method presented in this chapter is tested for the crew scheduling problem

only. We use domestic flight schedules of a European airline. The schedules

available for the tests are organized in two sets. The first set consists of ten

small schedules, each of 220 - 272 flights. The second test set consists of ten

schedules of medium size, each of 401 - 539 flights. The planning scope of all

schedules in each test set is between three and seven days1.

The framework is implemented in .net c#. All tests are performed on a stan-

dard PC with a 64 bit dual core Intel R

Core2 2.4 GHz CPU, 8 GB RAM and

Windows XP x64. We use the IPM of the solver MOPS 92for the master problem

and the solver Cplex 113for the integer problems.

1The test set with small problems consists of five schedules of three days, two schedules of

five days and three schedules of seven days. The test set with medium problems consists of

three schedules of three days, three schedules of five days and four schedules of seven days.

2Product of MOPS Optimierungssysteme GmbH & Co. KG [2009]

3Product of IBM ILOG [2009]

5.6. Computational Experiments

0,0%

0,2%

0,4%

0,6%

0,8%

1,0%

1,2%

1,4%

1,6%

1,8%

2,0%

Average solution time (minutes)

Average gap to best solution

Average solution time (minutes)

Figure 5.3.: Comparison of Different Solution Strategies for Small Problems

Figure 5.3 shows the average solution time and average gap to the best known

solution value for the small problems for all tested solution strategies. In addition

to strategies branch-and-price and dive-and-price, which are described in Section

5.3 in detail, we also test the strategy root-price, where columns are generated in

the root node only. The generated columns are then used to formulate an integer

problem, which is solved by the commercial solver IBM ILOG Cplex 11. Each

strategy is combined with the improvement techniques SR3Inequalities, Label

Categorizing and History Fixing. The improvement technique Label Categori-

zing is an alternative sorting procedure for labels in the label setting algorithm

and is described in Section 5.2. With the strategy root-price the improvement

techniques are only applied during the solution process of the root node because

a commercial solver is used to solve the integer problem.

Same tests including all solution strategies were performed for the test set with

medium problems. However, in several medium problems the branch-and-price

and root-price strategies did not find any feasible solution within 24 hours. In

many other cases the results were significantly worse than those of the solutions

found by the dive-and-price strategies. Thus for medium problems we only show

results for the dive-and-price strategies. Figure 5.4 summarizes those results.

5. A Branch-and-Price-and-Cut Framework

100

200

300

400

500

600

700

0,0%

1,0%

2,0%

3,0%

4,0%

5,0%

6,0%

7,0%

Average solution time (minutes)

Average gap to best solution

Average solution time (minutes)

Average gap to best solution

Figure 5.4.: Comparison of Different Solution Strategies for Medium Problems

For the medium problems, Figure 5.5 also shows the running times for different

parts of the framework cumulated to the total solution time as well as the total

number of iterations for column generation in all branch-and-bound nodes.

The solution strategies in Figures 5.3 and 5.4 are sorted according to the

average gap to the best known solution value. One important result for small

problems is that the dive-and-price strategy with Cut Generation and Label Ca-

tegorizing often leads to better results than the corresponding branch-and-price

strategy. This is possible because of the heuristic nature of the presented fra-

mework. The main termination criterion of the used column generation solver is

the convergence rate of the lower bound. Thus in most cases the column gene-

ration is terminated, although more columns could be generated and therefore

the optimality of the value of the lower bound is not proven. Additionally, leaves

in the branch-and-bound tree with a small number of columns are declared as

final leaves and solved to optimality by a commercial branch-and-bound solver

without generating additional columns. The global search algorithm terminates

when a maximal number of such final leaves is explored. The allowed maximal

number of such final leaves for the branch-and-price strategies is three times hi-

5.6. Computational Experiments

2.000

4.000

6.000

8.000

10.000

12.000

14.000

100

200

300

400

500

600

700

Average total number of iterations

Cumulated average solution time (min)

Master Solver

Pricing Solver

Inequality Separation

Final Leaves Solver

Iterations

Figure 5.5.: Cumulated Average Solution Times for Different Solution Strategies

for Medium Problems

gher than with the dive-and-price strategies, but nevertheless this termination

criterion leads to an incomplete exploration of the branch-and-bound tree.

The results in this work show that the integration of column generation and

global search for the integer solution is crucial to finding solutions of very good

quality and that this integration does not unavoidably lead to higher solution

times. However, an accurate comparison of the solution times of the root-price

strategies with other strategies in this work is not possible, because another

branch-and-bound solver is used in the root-price strategies. We implement the

root-price strategy using a commercial branch-and-bound solver to show the

possible improvement of solution quality as well as solution time, which can be

achieved by making the effort to implement a problem-specific branch-and-bound

solver.

According to the average results a positive effect of all improvement techniques

on solution quality or solution time can be observed. Moreover, it seems that

certain combinations of improvement techniques especially are superior in solu-

tion quality and solution time. The following detailed analysis of those effects is

5. A Branch-and-Price-and-Cut Framework

0,0%

5,0%

10,0%

15,0%

20,0%

Dive-Price-Cut-Fix

Dive-Price-Cut-LC-Fix

0,0%

5,0%

10,0%

15,0%

Dive-Price

Dive-Price-LC

0,0%

5,0%

10,0%

15,0%

Dive-Price-Cut

Dive-Price-Cut-LC

0,0%

5,0%

10,0%

15,0%

Dive-Price-Fix

Dive-Price-LC-Fix

Figure 5.6.: Effect of the Improvement Technique Label Categorizing on the So-

lution Quality for All Medium Problems

carried out by comparing the gap to the best known solution value for all medium

problems for each possible combination of two solution strategies.

5.6.1. Label Categorizing

One obvious result of the improvement technique Label Categorizing is the very

high solution time without History Fixing; compare Figure 5.5. There are several

5.6. Computational Experiments

reasons for this effect. The additional sorting and categorizing algorithms lead

to higher solution times of the pricing problem. Additionally, the technique

Label Categorizing leads to the effect that many less promising labels are also

propagated during the label setting algorithm. Thus in comparison with the

classical sorting of labels according to reduced costs, on average more labels

need to be propagated to generate an equal number of columns. Moreover, due

to the strong diversification of the generated columns fewer of them improve the

lower bound solution, leading to a slower convergence of the column generation

algorithm. In our tests on average up to 30% more iterations of the column

generation algorithm are performed, although fewer branch-and-bound nodes

are explored in total. Another important observation is that with this technique

on average up to 35% more columns are generated in each iteration. This leads

to higher solution times for the RMP. The higher number of generated columns

can be explained by the restricted label storage in the pricing algorithm. After

exploring the search space with a restricted number of propagated labels, the

algorithm terminates if a required minimal number of columns was found or

otherwise continues the search with the remaining labels. In the second case the

algorithm completely explores the additional search space and returns all columns

found so far or again continues the search until all labels are propagated. With

the technique Label Categorizing more less promising labels are propagated in

the first step and therefore it is more likely that after the first step not enough

columns are found and the search has to be continued. Then, after extendeding

the search more columns are often found than in the default sorting strategy

where usually fewer extensions of the search are required.

The goal of the improvement technique Label Categorizing is to generate more

diverse columns and therefore to improve the search for the optimal dual solu-

tion and also to use a more diversified column base during the global search.

Figure 5.6 shows the effects of this improvement technique together with each of

the other strategies. The result is that in only 1 of 40 cases does this technique

lead to a worse solution. In all other cases an equally good and often a much

better solution can be found when using Label Categorizing. Moreover, the com-

bination with SR3Inequalities is crucial to achieving constantly good solution

quality for all instances. On the other hand, this improvement technique leads

to extraordinarily high solution times, as discussed above. However, together

5. A Branch-and-Price-and-Cut Framework

0,0%

5,0%

10,0%

15,0%

Dive-Price-LC-Fix

Dive-Price-Cut-LC-Fix

0,0%

5,0%

10,0%

15,0%

Dive-Price

Dive-Price-Cut

0,0%

5,0%

10,0%

15,0%

Dive-Price-LC

Dive-Price-Cut-LC

0,0%

5,0%

10,0%

15,0%

20,0%

Dive-Price-Fix

Dive-Price-Cut-Fix

Figure 5.7.: Effect of the Improvement Technique SR3Inequalities on the Solu-

tion Quality for All Medium Problems

with the technique History Fixing a good compromise between solution time and

solution quality can be achieved.

5.6.2. SR3Inequalities

The consideration of SR3Inequalities requires additional solution time; compare

Figure 5.5. In addition to the separation of inequalities and their consideration

5.6. Computational Experiments

in the pricing problem, solution time increases due also to additional rows in the

RMP. The potential to cut off nodes in the branch-and-bound tree is very low for

the problems considered due to a normally small gap between lower and upper

bound. The consequence is an increased total solution time for most problem

cases. Especially in combination with the Label Categorizing technique the total

solution time is noticeably increased because of the increased number of iterations

in the column generation algorithm.

Figure 5.7 shows the effects of SR3Inequalities on solution quality. If used

as the only improvement technique, SR3Inequalities improve the results and

speed up the method. In combination with other techniques the consideration

of SR3Inequalities does not generally lead to better solutions. However, the

combination of SR3Inequalities with Label Categorizing is the only strategy to

find near-optimal solutions for all considered schedules. In combination with SR3

Inequalities and History Fixing the solution quality seems to be more stable with

fewer outliers, although average results are equal. It seems that the improvement

technique SR3Inequalities is more advantageous for small problems, see Figure

5.3, than for medium problems.

5.6.3. History Fixing

The motive for the History Fixing techniques is to reduce the search space and

speed up the solution process. Especially in combination with other improvement

techniques this goal can be reached without dramatic reduction in solution qua-

lity. Even strategies based on branch-and-price lead, in combination with History

Fixing, to acceptable solution times for small problems. Figure 5.8 shows the

effects of History Fixing in combination with each of the other strategies on solu-

tion quality of medium problems. Especially in combination with the technique

Label Categorizing the solution time can be improved dramatically with only

relatively small changes in solution quality. In combination with both techniques

SR3Inequalities as well as Label Categorizing good stability of solution quality

with little outliers can be obtained.

5. A Branch-and-Price-and-Cut Framework

0,0%

2,0%

4,0%

6,0%

8,0%

Dive-Price-Cut-LC

Dive-Price-Cut-LC-Fix

0,0%

5,0%

10,0%

15,0%

Dive-Price

Dive-Price-Fix

0,0%

5,0%

10,0%

15,0%

20,0%

Dive-Price-Cut

Dive-Price-Cut-Fix

0,0%

5,0%

10,0%

15,0%

Dive-Price-LC

Dive-Price-LC-Fix

Figure 5.8.: Effect of the Improvement Technique History Fixing on the Solution

Quality for All Medium Problems

6. A Stochastic Optimisation Approach

to Crew Pairing and Aircraft

Scheduling

The application of stochastic programming to crew and aircraft scheduling leads

to the possibility of considering more detailed measures for stability in contrast to

abstract indicators used with deterministic scheduling. Especially in combination

with simultaneous scheduling of crews and aircraft new potential can be iden-

tified. The consideration of uncertainty through explicit scenarios in stochastic

optimization, however, adds additional complexity to the scheduling problems.

The first step in this chapter is the formulation of an integrated stochastic crew

scheduling and aircraft assignment model which considers propagation of delays

due to aircraft as well as crew. The model contains several non-linear constraints

and is therefore not applicable for real-world instances. The second step is a

decomposition of this integrated model to achieve a more tractable stochastic

model. The new model can be solved by a combination of the iterative approach,

proposed by Weide et al. [2009], and classical column generation methods, thus

providing a good starting point for considering robustness with real-life problem

instances.

6.1. Formulation of the Integrated Stochastic Problem

The integrated airline crew pairing and aircraft routing problem can be formula-

ted as a set partitioning problem, where cost-optimal sets of legal crew pairings

and aircraft routes have to be selected to partition all available flights. The crew

pairing and the aircraft routing problems interact through aircraft changes of

crews: thus if the crew ground time during an aircraft change does not contain

6. A Stochastic Optimisation Approach to Crew Pairing and Aircraft Scheduling

sufficient slack, then a possible delay of the incoming flight is propagated both to

the next flight of the crew and the next flight of the aircraft. This delay propa-

gation can be measured for given schedules by the propagation model introduced

in (7.4) - (7.5). The objective is then to minimize costs induced by crew pairings

and propagated delays since we assume that the operational costs of all aircraft

of the same fleet are identical. Equations (6.1)-(6.7) describe the mathematical

formulation of the integrated stochastic model for crew scheduling and aircraft

routing.

The set Frepresents all flights that must be covered, the sets Pand Rthe

possible crew pairings and aircraft routes. A solution to the problem consisting

of a set of legal crew pairings and routes of flights for each aircraft is represented

by Xand Yrespectively. The binary variable xj∈X(yi∈Y) indicates whether

the crew pairing j(aircraft route i) is part of the solution or not. The cost cjof

a crew pairing jrepresents the costs of working time and overnight rests. The

objective is to minimize these costs.

p∈P

cjxj+Q(X, Y, Ω) →min stochastic integrated problem (6.1)

p∈P(f)

xj= 1 ∀f∈F(6.2)

r∈R(f)

yi= 1 ∀f∈F(6.3)

r∈R(s)

yi≤1∀s∈SR(6.4)

r∈R(e)

yi≥1∀e∈ER(6.5)

xj∈ {0,1} ∀j∈P(6.6)

yi∈ {0,1} ∀i∈R(6.7)

In the following, Q(X, Y, Ω) = cQQ(X, Y, Ω) describes the penalty for the pro-

pagation of delays by aircraft and crews. The model for Q(X, Y, Ω) is described

by (6.8) - (6.17) and computes in this case the total number of propagated delays.

Ωis the set of scenarios used for evaluation of the recourse, and pωis the proba-

6.1. Formulation of the Integrated Stochastic Problem

bility of the scenario ω∈Omega. A scenario is a representation of the stochastic

variables for the departure and arrival of flights. Deviations of these times from

the scheduled times define primary delays. rfω and dfω represent actual arrival

and departure time for flight funder scenario ω.d

rfω and d

dfω represent the

arrival and departure times for flight funder scenario ω, if no planning decisions

are considered. Thus these times include primary delays only. The scheduled

arrival and departure time of flight fare given by sA

fand sD

f, the flight time of

flight funder scenario ωby tfω. The scenarios for primary delays are obtained

from historical data.

The primary delays are represented implicitly by the random variables gp

fω,

fω and tfω. Propagated delays result when aircraft or crews are too late for the

next flight on their route. Constraints (6.9) consider the minimal ground time for

the selected aircraft routes and constraints (6.10) the minimal ground time for

the selected crew pairings possibly leading to delayed departure times. It is to be

noted that both equations are non-linear for the integrated model (6.1) - (6.7).

For a given solution Xand Y,ai(f)points to the predecessor flight of flight f

in aircraft route i, and cj(f)to the predecessor flight of flight fin crew pairing

j.gp

fω is the ground time for the final preparations of the aircraft before the

flight funder scenario ω.ga

ai(f)fω > gp

fω is the total ground time between flight

fand the aircraft predecessor flight, and gc

cj(f)fω > gp

fω is the total ground time

between flight fand the crew predecessor flight under scenario ω. Constraints

(6.11) and (6.12) ensure consistency between flight arrival and departure times,

and the constraints (6.13)-(6.15) represent the computation of primary delays.

The decision variables of the evaluation model Q(X, Y, Ω) are the actual arrival

and departure times: thus the additional delays induced by the crew pairing and

aircraft assignment decisions are minimized (equation (6.8)). δfω is the total

arrival delay for flight f, whereas d

δfω is the number of primary delays occurring

during the actual flight or the last preparations before departure under scenario

ω. Delay times must be nonnegative (constraints (6.16) and (6.17)).

6. A Stochastic Optimisation Approach to Crew Pairing and Aircraft Scheduling

Q(X, Y, Ω) = min X

ω∈Ω

pωX

f∈F

(δfω −d

δfω)(6.8)

dfω −[rai(f)ω+ga

ai(f)fω]yi≥0,∀yi∈Y, ∀f∈F, ∀ω∈Ω(6.9)

dfω −[rcj(f)ω+gc

cj(f)fω]xj≥0,∀xj∈X, ∀f∈F, ∀ω∈Ω(6.10)

rfω −dfω ≥tfω,∀f∈F, ∀ω∈Ω(6.11)

rfω −δfω ≤sA

f,∀f∈F, ∀ω∈Ω(6.12)

dfω −gp

fω =sD

f,∀f∈F, ∀ω∈Ω(6.13)

rfω −d

δfω =sA

f,∀f∈F, ∀ω∈Ω(6.14)

rfω −d

dfω =tfω,∀f∈F, ∀ω∈Ω(6.15)

δfω ≥0,∀f∈F, ∀ω∈Ω(6.16)

δfω ≥0,∀f∈F, ∀ω∈Ω(6.17)

6.2. Decomposition Strategy for the Recourse Model

In order to eliminate the non-linear constraints, the recourse function is redefi-

ned to consider the aircraft routes and crew pairings in isolation, represented by

Q(X, Y, Ω) = cQ(PjxjQP(j, Y, Ω) + PiyiQR(i, X, Ω)). The new recourse model

for crew pairings is given in (6.18) - (6.27). The main difference from the integra-

ted model defined in Section 6.1 is that d

δfω represents primary delays as well as

those induced by aircraft routes. Thus constraints (6.24) are added and replace

constraints (6.13). P(δfω −d

δfω)are the additional delays induced by the crew

scheduling decisions only. The non-linear equation (6.10) is replaced by equation

(6.20) indicating that the recourse is evaluated only for one crew pairing. Then

∀f∈jis the set of all flights covered by pairing j.

6.2. Decomposition Strategy for the Recourse Model

QP(j, Y, Ω) = min X

ω∈Ω

pωX

f∈F

(δfω −d

δfω)(6.18)

dfω −[rai(f)ω+ga

ai(f)fω]yi≥0,∀yi∈Y, ∀f∈F, ∀ω∈Ω(6.19)

dfω −rcj(f)ω−gc

cj(f)fω ≥0,∀f∈j, ∀ω∈Ω(6.20)

rfω −dfω ≥tfω,∀f∈F, ∀ω∈Ω(6.21)

rfω −δfω ≤sA

f,∀f∈F, ∀ω∈Ω(6.22)

δfω ≥0,∀f∈F, ∀ω∈Ω(6.23)

dfω −[\ra(f)ω+ga

ai(f)fω]yi= 0,∀yi∈Y, ∀f∈i, ∀ω∈Ω(6.24)

rfω −d

δfω =sA

f,∀f∈F, ∀ω∈Ω(6.25)

rfω −d

dfω =tfω,∀f∈F, ∀ω∈Ω(6.26)

δfω ≥0,∀f∈F, ∀ω∈Ω(6.27)

This recourse model considers the interdependencies of aircraft routes due to

several aircraft changes during one crew pairing, but it does not consider interde-

pendencies of crew pairings if those are sharing one aircraft. Moreover, through

the decomposition into two separate recourse problems, the presented recourse

models measure the additional delay propagation over aircraft or crew changes

only. This means the presented recourse model corresponds to the principle "crew

follows aircraft and vice versa", which is also found in Yen and Birge [2006] and

Weide et al. [2009].

The recourse model (6.18) - (6.27) deals with the average delay for each flight

having regard to all scenarios ω∈Ω. Based on this model alternative robustness

indicators can easily be formulated. A straightforward way in which to consider

the expected number of delayed flights and to penalize the longer delays higher

is to sum up the squares of the delays in the objective. Another alternative is

to count delays over a certain threshold only. Then all flights with such delays

are penalized equally and shorter delays are ignored. QP

t(j, Y, Ω) represents the

6. A Stochastic Optimisation Approach to Crew Pairing and Aircraft Scheduling

model extension for the robustness indicator based on the expected number of

reactionary delays over a threshold to:

t(j, Y, Ω) = min X

ω∈Ω

pωX

f∈F

zfω (6.28)

subject to (6.19)-(6.27) and

δfω −d

δfω < to+zfωδM∀f∈F, ∀ω∈Ω(6.29)

zfω is binary ∀f∈F, ∀ω∈Ω(6.30)

The new variable zfω indicates whether the additional delay of flight fin scenario

ωis greater than the given threshold to.δMbelongs to the big M formulation of

the constraint.

A very similar recourse model QP

d(j, Y, Ω) represents the robustness indicator

based on the expected number of crew duty disruptions. For each flight in a crew

pairing the value Dmax

fdescribes the duty slack, i.e. maximal possible delay of

this flight f, which does not directly lead to a disruption of the crew duty limits

(compare also Equation (6.47) on page 85). Dmax

fis only set for the last flight

of each crew duty to the corresponding duty slack: for all other flights it is set

to infinity. The value of the duty slack is then the individual threshold for each

flight leading to the following recourse model:

d(j, Y, Ω) = min X

ω∈Ω

pωX

f∈F

zfω (6.31)

subject to (6.19)-(6.27)

δfω < Dmax

f+zfωδM∀f∈F, ∀ω∈Ω(6.32)

zfω is binary ∀f∈F, ∀ω∈Ω(6.33)

The labels QPfor crew scheduling and QRfor aircraft routing refer in this

chapter to any recourse model based on the computation of propagated delays

for individual path variables independently of the actual solution. The models

tand QP

dare only two possible alternatives. The choice of the recourse model

depends on user preference only, because the computational properties of all

three models are comparable. The formulation of the analogous recourse models

QRfor the aircraft routing problem is straightforward.

6.2. Decomposition Strategy for the Recourse Model

Algorithm 6.1: Iterative Method for the Stochastic Crew and Aircraft Sche-

duling

Set cQ= 0 /* penalty value for non-robustness*/

Solve crew pairing problem without a given aircraft routing solution

while cQ≤cQ

max do

Increase cQ=cQ+ const.

Solve aircraft routing problem with cost c

cRbased on crew schedule

Solve crew pairing problem with cost c

cPbased on aircraft schedule

if Pj∈PxjQP(j, Y, Ω) + Pi∈RyiQR(i, X, Ω) does not change then

break

Note that for a given aircraft schedule the penalty costs for non-robustness

can be computed during crew pairing generation for each crew pairing separately.

Analogously, for a given crew schedule the additional delays and duty disruptions

induced by the routing decisions for each aircraft are penalized. The decompo-

sition of the recourse model enables the decomposition of the whole integrated

problem into separate problems for crew pairing scheduling and aircraft routing,

which can be solved iteratively. The interdependencies of those two problems

are considered through the non-robustness penalty in the objective. For given

aircraft routes the stochastic recourse for the crew scheduling problem becomes

linear and vice versa. Classical column generation methods can be easily applied

to each scheduling problem, because the new recourse only considers individual

path variables. Algorithm 6.1 gives an overview of the complete iterative algo-

rithm. The iterative approach starts by solving a crew pairing problem without

penalty costs for non-robustness and without a given aircraft routing solution.

The resulting crew costs form a lower bound on the actual optimal costs. Based

on this crew schedule, the two scheduling problems are solved iteratively with

increasing penalty value for non-robustness cQuntil a maximum penalty value

max is reached or the value of the recourse functions cannot be further improved.

6. A Stochastic Optimisation Approach to Crew Pairing and Aircraft Scheduling

The separate crew scheduling problem can be formulated as the following well-

known set partitioning problem with recourse

j∈P

xjcP

j+cQQP(j, Y, Ω)→min stochastic crew pairing problem (6.34)

j∈P(f)

xj= 1 ∀f∈F(6.35)

xj∈ {0,1} ∀j∈P(6.36)

An analogous set partitioning model with recourse can be used for the aircraft

routing problem. By adding penalty costs for non-robustness the separate air-

craft routing problem is no longer just a feasibility problem. Thus the problem

formulation based on a Dantzig-Wolfe decomposition reads

i∈R

yicQQR(i, X, Ω) →min stochastic aircraft assignment problem (6.37)

r∈R(f)

yr= 1 ∀f∈F(6.38)

r∈R(s)

yr≤1∀s∈SR(6.39)

r∈R(e)

yr≥1∀e∈ER(6.40)

yr∈ {0,1} ∀r∈R(6.41)

The Dantzig-Wolfe formulation of the aircraft routing problem has the advan-

tage that it can be solved by existing column generation methods. The reduced

costs are defined analogously to the reduced costs of crew pairings. The crew

pairing as well as the aircraft routing problem are solved by a branch-and-price

method, described in Chapter 5and Chapter 8. The extensions to the original

problems are fully represented by the recourse models. Thus these extensions

need to be considered during the generation of new path variables only.

Moreover, the method for the evaluation of the recourse models QPcan be

easily integrated into the solution method for the pricing subproblem. The same

task network used for the pricing subproblems can be used to compute the delay

propagation. In this way the costs associated with the recourse function are

6.3. Corresponding Deterministic Indicators

computed for partial paths and therefore implicitly considered in the pricing

subproblem. The recourse functions, furthermore, can be evaluated recursively

by dynamic programming methods analogous to the methods already used for

the pricing subproblem. Equations (6.42) and (6.43) show the recursive functions

for primary and reactionary delays based on the recourse models QP.

δfω =−sA

f+tfω+sA

a(f)+ga

ai(f)fω +\

δa(f)ω(6.42)

δfω =−sA

f+tfω+sA

c(f)+gc

cj(f)fω +δa(f)ω(6.43)

The information about primary delays as well as the aircraft schedule (in the

case of crew scheduling) are available before the solution process. Thus the

values for d

δfω can be computed in advance, if necessary for the evaluation of

the recourse models. The values for δfω depend on the path generated and are

therefore computed recursively during the solution of the pricing subproblem.

The solution method for the pricing subproblem in this work is based on dy-

namic programming. Dynamic programming stores information about paths at

each node in the underlying network and reuses this information at all successor

nodes. This storage method is also applied to the computation of delay propaga-

tion leading to additional increase in the efficiency of the method. Partial paths

may be reconsidered in different pricing iterations by saving storage information

for future column generation iterations. This strategy is called iteration-spanning

storage and can further reduce the solution times. A greater size of iteration-

spanning storage may have positive effects on the efficiency of the evaluation

process, but in general it is limited by the available physical memory. For this

reason, a maximum storage size is defined and elements that are less frequently

considered in later iterations are removed from the storage to ensure the maxi-

mum storage size.

6.3. Corresponding Deterministic Indicators

A well-known indicator of punctuality of schedules is the number of aircraft

changes by crews with low slack between the two flights, i.e. restricted aircraft

changes, see Weide et al. [2009] and Mercier and Soumis [2007].

6. A Stochastic Optimisation Approach to Crew Pairing and Aircraft Scheduling

We represent the severity of a connection between two flights in a crew pairing

in this work by the penalty factor 0≤π(f1, f2)≤1. An aircraft change between

the flights f1and f2is then penalized with the product cγ·π(f1, f2). This

indicator is based on two values, a minimal slack required during every aircraft

change and a maximal slack defining the upper limit to penalize. The penalty

factor is then computed using following Equation (6.44):

π(f1, f2) = 









1,if slack during connection <minimal slack

0,if slack during connection >maximal slack

1−slack during connection−minimal slack

maximal slack−minimal slack p,otherwise

(6.44)

A connection with π(f1, f2)>0is called restricted connection. The iterative

approach proposed in this chapter can also be used to minimize the number of

aircraft changes at such restricted connections. Weide et al. [2009] propose to

minimize the number of restricted connections in crew pairings and to maximize

it in aircraft routes during the iterative approach in order to reach a minimization

globally. It is to be noted that during aircraft assignment π(f1, f2)describes a

restricted connection in the current crew solution. Thus the goal of the aircraft

assignment problem is to cover as many current restricted connections by aircraft

routes in order to minimize the number of aircraft changes at such connections.

The new objective functions are formulated as follows:

j∈P

xj

cP

j+cQX

(f1,f2)∈j

π(f1, f2)

→min crew pairing (6.45)

i∈P

yicQX

(f1,f2)∈i

π(f1, f2)→max aircraft route (6.46)

Figure 6.1 shows a visualization of the penalty factor for different values for p.

Higher values for plead to higher penalties for shorter slack and lower penalties

for longer slack than the linear penalty function with p= 1. The experiments in

this work were all performed using the quadratic penalty function with p= 2.

The minimal slack is set to ten minutes and the maximal to 60 minutes.

A straightforward choice for a robustness indicator facing crew duty disruptions

is based on the distribution of duty slack in the crew schedule. Duty slack is the

maximal duration of an arrival delay for the last flight of a duty, which does not

6.3. Corresponding Deterministic Indicators

0.2

0.4

0.6

0.8

0 10 20 30 40 50 60 70

Penalty Factor

Slack For Aircraft Change (Minutes)

Figure 6.1.: Graph of Penalty Factor with Values 1, 2, 3 and 4 for p

lead to a crew duty limit or a crew rest disruption. It is to be noted that the

maximal duty duration allowed can be increased depending on the following rest

duration; see Section 2.1.4 on page 12 for details. Thus to identify the maximal

slack it is necessary to compute the duty slack for all possible maximal duty

durations using the corresponding minimal rest times. Duties with low duty

slack are called restricted. The duty slack is computed as follows

min 









maximal allowed duty duration - scheduled duty duration

maximal allowed duty flight time - scheduled duty flight time

scheduled rest duration after duty - minimal rest duration











(6.47)

The penalty factor is then computed using following equation:

σ(duty) = 









1,if actual duty slack <minimal duty slack

0,if actual duty slack >maximal duty slack

1−actual duty slack−minimal duty slack

maximal duty slack−minimal duty slack2,otherwise

(6.48)

The values for minimal and maximal duty slack are set to 30 and 120 minutes

respectively. This robustness indicator can also be used with the iterative ap-

proach. Let duty ∈jand duty ∈ienumerate the duties ending with a flight

6. A Stochastic Optimisation Approach to Crew Pairing and Aircraft Scheduling

covered by pairing jor aircraft route irespectively; the new objective functions

are then formulated as follows:

j∈P

xj

cP

j+cQX

duty∈j

σ(duty)

→min crew pairing (6.49)

i∈P

yicQX

duty∈i

σ(duty)→max aircraft route (6.50)

6.4. Computational Experiments

The quality of the robustness indicators is discussed in detail in Chapter 7.

In this chapter we discuss the solution times for four models presented in this

chapter. The four models for crew and aircraft scheduling are a stochastic model

for minimizing reactionary delays represented by the recourse models QP

tand

t, a stochastic model for minimizing crew duty disruptions represented by the

recourse models QP

tand QR

tand the deterministic models penalizing restricted

aircraft changes and restricted duties described in Section 6.3. Figure 6.2 shows

a comparison of the solution times during the iterative approach for all four

models. The solution times are average values of 20 flight schedules of small size,

each of 220 – 272 flights. For the stochastic models we use 1000 delay scenarios,

each with an average of over 50% of flights delayed. This means, that each flight

is delayed in over 500 scenarios on average.

The stochastic model for delay propagation leads to significantly higher solu-

tion times than on all other models. The average total solution time here is 3:30

hours. Three instances are very difficult to solve with total solution times over

8 hours. In these three cases over 90% of the solution time was spent in the first

iteration. This means in some cases the scheduling method has the difficulty in

finding the first optimal solution. Later iterations, however, are initialized with

the optimal solution of the previous iteration and solved much faster. In 15 of

20 cases, however, the solution times for the stochastic model are below 2 hours.

In these cases the solution time was distributed more equally over the iterations.

The average total solution times for the other three models are much lower,

but the increase during the iterative method is comparable for all models. The

three difficult problems lead to significantly higher solution times for the other

6.4. Computational Experiments

0:00

0:28

0:57

1:26

1:55

2:24

2:52

3:21

3:50

Total Solution Time [hours]

Iteration

Stochastic Model for Delay Propagation

Stochastic Model for Duty Violations

Model with Restricted Aircraft Changes

Model with Restricted Duties

Figure 6.2.: Solution Times of the Iterative Method for all Models

three models also, although never more than 8 hours. The models evaluating

restricted duties usually need less solution time because fewer evaluation steps

are needed in the pricing problem.

The increase of the solution times for the stochastic models is low in com-

parison to the deterministic models, given that over 500 delay scenarios must

be considered for each flight during the generation of new variables. This good

performance is only possible because of the dynamic programming method with

storage techniques used to evaluate of the recourse models. In order to show

the effects of the different storage strategies we analyze the solution times of

the pricing subproblem during one column generation run in detail. Figure 6.3

shows a comparison of the running times of the pricing subproblem for the first

25 iterations of the column generation algorithm. Evidently, enabling the storage

has positive effects on the efficiency of the evaluation model.

While the recourse function without storage constantly needs about 50%-60%

of the time in the pricing subproblem, this ratio can be reduced to around 12% in

later iterations through enabling the iteration-exclusive storage, i.e. the storage is

cleared in each iteration of column generation. The high relative time consumed

by the evaluation method in these early iterations, however, only leads to a low

increase of the total running time, because the pricing subproblem can be solved

6. A Stochastic Optimisation Approach to Crew Pairing and Aircraft Scheduling

10%

20%

30%

40%

50%

60%

Time Ratio per Iteration

no storage

iteration-exclusive

storage

iteration-spanning

storage

Iteration

Efficiency

Figure 6.3.: Comparison of Solution Times for Different Storage Strategies

extremaly fast in the first iterations. Later pricing iterations need longer solution

times, thus it is important that the recourse function can then be performed as

efficiently as possible then. The iteration-spanning storage strategy can decrease

the solution time by around 2% in later iterations compared to the iteration-

exclusive storage.

7. Evaluation of indicators for Stability

The aim of this chapter is the evaluation of the quality of the stochastic as well

as deterministic robustness indicators presented in Chapter 6. The evaluation

is based on the computation of robustness measures by simulating crew and

aircraft schedules. We propose to measure the quality of indicators according to

the following properties:

Predictability describes the relation between the robustness indicator during

scheduling and the robustness measures during simulation. High predic-

tability means that there is a strong mathematical relation between the

values of the indicator and those of the measure.

Efficiency describes the relation between the cost of the schedule and the robust-

ness measures during simulation. High efficiency means that the increase

of the robustness measure is high for already low increase of cost.

Our method of evaluation of robustness indicators using a simulation model

is highlighted in Figure 7.1. In the first step a set of robust crew and aircraft

schedules is generated for each flight schedule and each robustness indicator.

We use the iterative approach presented in chapter 6. No specific method for

generation of those schedules is, however, required, as long as each schedule in

the resulting set has different costs or different value of the robustness indicator.

In the second step each crew and aircraft schedule is simulated to measure the

robustness, e.g. statistics on schedule disruptions and reactionary delays.

The remainder of this chapter is organized as follows. Firstly, we present as-

sumptions underlying the simulation model used for this evaluation, e.g. the

generation of primary delays. In the second step we present the simulation mo-

del. And finally we evaluate the robustness indicators presented in the previous

chapter and compare the stochastic model with the deterministic indicators.

7. Evaluation of indicators for Stability

Flight Schedule

Crew and

Aircraft

Schedule

Crew and

Aircraft

Schedule

Crew and

Aircraft

Schedule

Crew and

Aircraft

Schedule

Crew and

Aircraft

Schedule

Crew and

Aircraft

Schedule

Crew and

Aircraft

Schedule

Crew and

Aircraft

Schedule

Crew and

Aircraft

Schedule

Robustness

Measures

Crew and

Aircraft

Schedule

Crew and

Aircraft

Schedule

Crew and

Aircraft

Schedule

Crew and

Aircraft

Schedule

Robustness

Indicators

Simulation

Strategy for

Robust

Scheduling

Evaluation of

Scheduling

Strategy

Comparison

Recovery

Strategy

Primary DelaysPrimary Delays

Figure 7.1.: Framework for Evaluation of Strategies for Robust Scheduling

7.1. Assumptions and Empirical Data

There are three important assumptions underlying the simulation model. Firstly,

the ground processes for aircraft and crews at airports are represented abstractly.

Secondly, no rescheduling method is incorporated into the simulation model;

instead the rescheduling effort is measured by counting schedule disruptions that

cannot be resolved by propagating delays. Thirdly, primary delays are generated

according to probability distributions derived from historical data of a major

European airline.

In this work a delay propagation model is used to evaluate the stability of

aircraft and crew schedules. The model describes the interdependencies of crew

pairings and aircraft routes. Thus when crews change aircraft, delays of a crew

may be propagated to another aircraft and further also to other crews. The

ground tasks at airports are not modelled in detail: instead one task of fixed du-

ration is assumed to be performed immediately before departure. The duration

of this task corresponds to the minimal turn time for aircraft and minimal sit

time for crews respectively, i.e. the duration of all ground tasks is independent

of the actual airport, daytime or season. A detailed model of ground tasks re-

quires comprehensive knowledge of these processes, including duration and delay

probabilities, which significantly differ between airports, aircraft types and even

7.1. Assumptions and Empirical Data

parking positions at the same airport. Whereas extensive data of processes and

task durations may exist and mean considerable effort for modelling, historical

data on delay probabilities for each task of these processes simply does not exist.

Delays during the ground processes are often recorded as departure delays of

flights only. Thus a detailed model of ground tasks in our simulation model

would not lead to a better approximation of delay generation, due to lack of

relevant information. For the computation of the delay propagation between

two flights only the total duration of the ground processes is relevant. Thus

we choose to model the ground process between two flights as one task, but

distinguish between aircraft and crews.

Delay can lead to schedule disruptions, which need to be resolved to allow ope-

ration of the schedules. We distinguish between two general strategies to resolve

schedule conflicts. Firstly, delays may be propagated to subsequent flights of

aircraft and crew. Secondly, the schedules for aircraft and crews can be resche-

duled. In order to measure stability no rescheduling, which can lead to changes

of the schedule, is performed in our simulation model. Instead, the aircraft and

crew connect disruptions are resolved by performing reactionary delay propaga-

tion only. Crew rest and crew duty limit disruptions are recorded for statistics,

but not resolved. In particular, not even reactionary delays are propagated to

resolve crew rest and crew duty limit disruptions, because this usually leads to

unrealistically high delays at the beginning of the next duty. In practice such dis-

ruptions are resolved through extensive rescheduling and use of reserve resources,

as shown in Chapter 8. Thus for this analysis the recovery effort is measured by

counting the crew duty disruptions.

The generation of primary delays is based on historical data of a major Euro-

pean airline from 2003 to 2006. These empirical data on delays only contains the

differences between scheduled and actual departure and arrival times respecti-

vely. In particular, primary delays during the ground process which do not lead

to a delayed departure are not measured. All delays are classified according to

the IATA delay codes. According to these data, we derive theoretical distribu-

tions for duration and frequency of delays for use in our simulation model. We

give a brief overview of the analysis and results; for details we refer to Spengler

[2009].

7. Evaluation of indicators for Stability

200

400

600

800

1000

1200

1400

1600

1800

2000

no smoothing

with a = 2

with a = 5

with a = 10

Number of Delayed Flights

Duration of Delays

Figure 7.2.: Example for Smoothing with the Central Moving Average Method

with a= number data points, Source: Spengler [2009]

We group the different delay causes according to delay type as well as place

and frequency of occurrence. For each delay group the empirical data of delays

for the years 2003 to 2005 are then used to perform an automatic distribution

fitting for duration and frequency of delays. This process consists of three steps.

In the first the effects of manual input are eliminated by smoothing the empi-

rical data by computing the central moving average of five data points. The

new empirical distribution is [

F(x), where xis the delay duration. Figure 7.2

shows an example for the smoothing effect. In the second step, the smoothed

empirical distribution [

F0305(x)of the years 2003 to 2005 is automatically fitted

to a probability distribution using the software EasyFit1. The resulting proba-

bility function is F0(x). In the third step the theoretical probability distribution

F0(x)is compared with the smoothed empirical probability distribution d

F06(x)

from the year 2006 by computing the maximum distance Dbetween the two

1Product of MathWave Technologies [2009]

7.1. Assumptions and Empirical Data

Description Relative Average

Occurrence Duration

Airline Internal 12.6% 2 min

Aircraft, passenger and baggage handling 5.7% 10 min

Aircraft maintenance 2.7% 34 min

Flight operations and Crewing 1.28% 13 min

Automated equipment failure 1.1% 13 min

No gates and wrong scheduled ground time 0.34% 11 min

Weather 0 – 15% 25 min

Airspace congestion 0 – 15% 13 min

Airport congestion 0 – 15% 10 min

Table 7.1.: Distributions for Primary Delays

distributions. The empirical distributions are discrete: accordingly, the maximal

distance is computed as follows. Compare also [Toutenberg,2005, pp. 165–189]:

D= max

i∈1...n nD+

i,D−

io(7.1)

with D+

i=d

F06(x(i−1))−F0(x(i))(7.2)

D−

i=d

F06(x(i))−F0(x(i))(7.3)

Di≈ngives the distance between the two distributions at the position nminutes

and is a measure of the goodness of the fitted theoretical probability distribu-

tion. The theoretical distributions obtained in this work often underestimate the

probability of delays shorter than five minutes and in turn overestimate the pro-

babilities for delays longer than one hour. The values Di≈5for the distributions

found during this analysis range from 2.3% to 6.7%. This deviation seems to

be high, but still meets the requirements of the analysis in this work, because

the average duration of delays fits and the probability of severe delays is not

underestimated.

The result of this analysis is a set of nine delay groups. Table 7.1 shows a

summary of the delay cause groups2.

2Details on the found probability distributions are given in Appendix C.

7. Evaluation of indicators for Stability

The first six groups describe delays faced by individual flights. An indepen-

dence of the events can be assumed. Thus the probability of occurrence for those

delays is independent of the occurrence of other delays and can be set to a fixed

value according to the relative frequency of occurrence in the empirical data. The

duration of these delays is modelled by a theoretical distribution. The partitio-

ning of the delay causes into groups follows the suggestion of IATA with slight

modifications due to distinct statistical properties of different delays groups.

The last three groups represent primary delays caused by events or circum-

stances which lead to many delays of flights during a period; e.g. congestion

at an airport leads to an increased probability of primary delays for all flights

departing and arriving at this airport. In this work these groups contains delays

caused by weather, airport and airspace congestion. The analysis of these delay

causes shows that the occurrence probability varies either with the season or

departure and arrival airport respectively. But the duration of those delays does

not significantly correlate with the occurrence probability. Therefore for each

delay cause group one probability distribution for the duration of the delay dC

and several distributions for the occurrence probability πCare selected.

Given the distributions for occurrence probability, there are two ways of consi-

dering them during simulation depending on the aim of analysis. The first op-

tion is to introduce random variables in the simulation model for the occurrence

probabilities of delay of each delay cause. The second option is to use a fixed

occurrence probability for the whole simulation run. The first option can be rea-

lized in a two-step delay generation. In the first step the occurrence probabilities

of each delay cause are determined and in the second step the actual delays of

flights are generated according to the occurrence probability.

In this work we choose the second option and only consider one setting of the

occurrence probability for each delay cause group during a simulation run. This

option is suitable to exploring the behaviour of an airline schedule in certain

circumstances, e.g. bad weather or congestion at one airport. By performing

several simulation runs for different settings we can compare the performance of

a schedule in different circumstances in detail. We use twelve fixed probability

settings, which are presented in Table 7.2.

The stochastic models for optimization presented in Chapter 6are similar to

the simulation model used for evaluation. In order to prevent an overfitting

7.2. Simulation of Airline Aircraft and Crew Schedules

Config Weather Airport Congestion Airspace Congestion

medD 20% 10% -

medC - 10% 20%

medB 10% 20% -

medA 10% 10% 10%

lowD 10% 5% -

lowC - 5% 10%

lowB 5% 10% -

lowA 5% 5% 5%

highD 30% 15% -

highC - 15% 30%

highB 15% 30% -

highA 15% 15% 15%

Table 7.2.: Configurations for Probabilities of Primary Delays During Simulation

effect, different primary delays for optimization and simulation are used. During

optimization no primary delays due to weather, airspace congestion and airport

are considered, i.e. the primary delays during optimization are underestimated.

7.2. Simulation of Airline Aircraft and Crew Schedules

In accordance with the assumptions presented in the previous section we here

present a delay propagation model for aircraft and crews. The delay propagation

model is used with a Monte Carlo method to compute schedule stability measures.

Fis the set of flights. The scheduled departure and arrival times are then given

for each flight f∈Fby sD

fand sA

fand the actual departure and arrival times

are given by dfand rf. Equations (7.4)–(7.7) describe the delay propagation

model, where the actual time of arrival rfis computed on the actual time of

departure dfand the flight time tf. Before a flight can depart the turn process

of the aircraft abd the ground task of the crew have to be finished. ga

a(f),f and

c(f),f represent the ground times for aircraft and crews between two flights.

The predecessor flights are given by a(f)for aircraft routes and by c(f)for crew

pairings. Xfis the primary departure delay for flight fthat is independent of

7. Evaluation of indicators for Stability

the slack to the predecessor flight. Dfis the total arrival delay for flight fand

Rfis the reactionary arrival delay for flight f.

rf= max nsA

f, df+tfo,∀f∈F(7.4)

df= max 



sD

f,max 





ra(f)+ga

a(f),f ,

rc(f)+gc

c(f),f 







+Xf,∀f∈F(7.5)

Df=rf−sA

f,∀f∈F(7.6)

Rf=Df−Xf,∀f∈F(7.7)

where Xfis the sum of several stochastic variables corresponding to different

delay causes, Xf=PC∈Causes XC

f. Equation (7.8) shows a representation of

the stochastic variable by two parameters: the occurrence probability πCand

the duration dC. The duration dCis always a random variable distributed by a

log-normal or log-logistic distribution.

f=(0,if random > πC

dC∼FC,otherwise (7.8)

One important value of delay statistics is the fraction of flights facing reactio-

nary delays of nor more minutes:

0≤Pn=|{f∈F|Rf≥n}|

|F|≤1.0(7.9)

Another measure is the number of crew duty limit and crew rest disruptions.

This number corresponds to the number of flights in the following set

V=|{f∈F|Df> Dmax

f}|,(7.10)

where Dmax

fis the maximal duration of an arrival delay of flight f, which does

not lead to a crew duty limit or a crew rest disruption. In this work this value

is called duty slack, Dmax

fis only set for the last flight of each crew duty to the

corresponding duty slack; for all other flights it is set to infinity. The computation

of the duty slack is given in Equation (6.47).

7.2. Simulation of Airline Aircraft and Crew Schedules

Algorithm 7.1: Monte Carlo Method for Simulation of Airline Schedules

Initialize Dmax

ffor the last flight of each crew duty

while arrival on-time performance changes significantly for any flight do

Generate primary delays Xffor each flight

Compute delay and duty rule disruption counters Df,Rfand C

Algorithm 7shows the Monte Carlo method. In each iteration of the method

two steps are performed. Firstly, a set of new primary delays is generated using

the given probability distributions. Secondly, the resulting total and reactionary

delays and the number of crew duty disruptions are computed using the model

given by Equations 7.4 –7.7 and 7.10. The simulation terminates when the

arrival on-time performance values of each flight stabilize or a maximal number

of iterations is reached. The arrival on-time performance values for a flight

describe the relative number of iterations, where this flight arrived within 0, 5

and 15 minutes respectively after scheduled arrival.

We evaluate the predictability of a robustness indicator by computing the li-

near dependency of the robustness indicator with the corresponding robustness

measures in the simulation. The efficiency of a robustness indicator is evaluated

by quantifying the linear dependency of the schedule costs with the robustness

measure. The absolute values of the robustness indicators, robustness measures

and costs of aircraft and crew schedules differ greatly between flight schedules.

Thus the evaluation of the linear dependency of the robustness indicator with the

robustness measures and crew costs based on absolute values can only be made

for aircraft and crew schedules of the same flight schedule. In order to evaluate

the predictability and efficiency of a robustness indicator for all flight schedules,

we propose to evaluate the linear dependency based on the relative difference

of the robustness indicator, robustness measure and crew costs. This means for

each flight schedule, a basis aircraft and crew schedule firstly is computed that

is not used for evaluation. A set of subsequent aircraft and crew schedules is

then computed using different robustness models. The corresponding simula-

tion and scheduling results for each schedule in this set are compared with the

basis schedule. The relative difference is then computed for the robustness indi-

7. Evaluation of indicators for Stability

cator computed during optimization, the robustness measures computed during

simulation and the crew costs.

Now, let S={sk|k= 1..n}be the set of crew and aircraft schedules generated

for different flight schedules. Let riB(sk)be the absolute value of the robust-

ness indicator Bfor schedule sk,rmP15 (sk)the value of the robustness measure

counting propagated delays over 15 minutes, rmV(sk)the value of the robustness

measure counting crew duty disruptions and c(sk)is the value of the crew costs.

Then, for each crew and aircraft schedule, rimax(sk),rmmax(sk)and cmin(sk)

refer to the properties of the basis schedule of the same flight schedule. IBis

the set of the relative differences of the robustness indicator B,MP15 and MV

are the relative differences of the two robustness measures from simulation and

Care the relative differences of the crew costs:

IB=(ik=rimax

B(sk)−riB(sk)

rimax

B(sk)k= 1..n)(7.11)

MP15 =(mk=rmmax

P15 (sk)−rmP15 (sk)

rmmax

P15 (sk)k= 1..n)(7.12)

MV=(mk=rmmax

V(sk)−rmV(sk)

rmmax

V(sk)k= 1..n)(7.13)

C=(ck=c(sk)−cmin(sk)

c(sk)k= 1..n)(7.14)

The Pearson product-moment correlation factor (Equation (7.15), compare

Rodgers and Nicewander [1988]) is used to evaluate a possible linear dependence

between the relative decrease of a robustness indicator and the relative decrease

of a robustness measure

Cor(I, M) = Pn

k=1 ik−Imk−M

rPn

k=1 ik−I2Pn

k=1 mk−M2.(7.15)

A correlation factor of 1 or -1 means a high linear relation, whereas a correla-

tion factor near 0 means no linear dependence. A high linear dependence between

the relative decrease of an indicator and the relative decrease of a measure indi-

cates high predictability of the indicator. The definition of the correlation factor

7.3. Simulation Experiments

Cor(C, M), i.e. between the relative increase of crew costs and the relative de-

crease of a robustness measure is analogous.

7.3. Simulation Experiments

The stochastic recourse models presented in Chapter 6are referred to as Qt

for the delay propagation model and Qdfor the duty slack model. We define

rit(sk) = Pj∈skQP

t(j, Ysk, ω)and rid(sk) = Pj∈skQP

d(j, Ysk, ω). The determi-

nistic indicators are defined as follows: riπ(sk) = P(f1,f2)∈skπ(f1, f2)for the

restricted aircraft changes and riσ(sk) = Pduty∈skσ(duty)for restricted duties.

The sets It,Id,Iπand Iσthen represent the relative differences of the objective

values of these recourse models.

The first step of the evaluation is now to quantify the linear dependency for

these indicators. The stochastic iterative method presented in this chapter is

used to generate crew and aircraft schedules for 20 domestic flight schedules.

Using the recourse models Qtthis results in 61 aircraft and crew schedules, which

are simulated using the simulation model. 20 schedules are the basis schedules

leading to 41 schedules with relative differences for indicators, measures and

costs. Thus the sets MP15 ,MV,Cand Itcontain 41 elements, which are used

for the following analysis.

Figure 7.3 shows the results for the simulation configuration highA. There is a

strong linear correlation between the relative decrease of the penalty factor for

the expected reactionary delays and the relative decrease of the actual reactio-

nary delays over 15 minutes (Cor(It, MP15 )=0.85) as well as a strong linear

correlation between the relative increase of crew costs and the relative decrease

of the actual reactionary delays over 15 minutes (Cor(C, MP15 )=0.77). The

model for linear regression between the relative increase of crew costs and the

relative decrease of reactionary delays is mk= 6.3% + 8.6ck, i.e. on average a

decrease in reactionary delays of 6.3% can be achieved without increasing crew

costs and an additional decrease by 8.6% can be achieved by increasing crew

costs by 1%.

Figure 7.4 shows the results of the correlation analysis as well as the regres-

sion analysis for all simulation configurations. The factor for linear correlation

between the relative decrease of reactionary delays and the relative decrease of

7. Evaluation of indicators for Stability

10%

15%

20%

25%

30%

35%

40%

45%

0% 50% 100%

Relative Decrease of

Reactionary Delays over 15 Minutes

Relative Decrease of Expected

Reactionary Delays

10%

15%

20%

25%

30%

35%

40%

45%

0% 1% 2% 3%

Relative Decrease of

Reactionary Delays over 15 Minutes

Relative Increase of Crew Costs

Figure 7.3.: Comparison of the Relative Decrease of Expected Reactionary De-

lays as well as the Relative Increase of Crew Costs with the Relative

Decrease of Reactionary Delays (Configuration highA)

the corresponding penalty factor is greater than 0.82 for all configurations. The

corresponding correlation factor with the relative increase of crew costs is always

greater than 0.7. Both observations indicate a high predictability of the stochas-

tic model on the punctuality of the schedules. The linear regression models are

very similar for all simulation configurations, i.e. the interpretation of the model

above also holds for different configurations.

The next step is to evaluate the robustness indicator for the expected number

of crew duty disruptions. Figure 7.5 shows the evaluation of this robustness indi-

cator for the configuration highA and Figure 7.6 for all simulation configurations.

There is a high linear correlation between the relative decrease of the expected

and observed crew duty disruptions (Cor(Id, MV)>0.7) for all configurations.

A detailed analysis of the relation between the relative increase of crew costs and

the decrease of crew duty disruptions leads to the following regression model for

the scenario highA: mk= 32% + 9.8ck. This means an average decrease of crew

duty disruptions of 32% can be achieved without increasing costs significantly.

Additionally, the number of crew duty disruptions can be further decreased by

9.8% with each increase of crew costs by 1%. The correlation factor for this linear

100

7.3. Simulation Experiments

10%

15%

20%

25%

30%

35%

40%

45%

50%

0% 1% 2% 3%

Relative Decrease of

Reactionary Delays over 15 Minutes

Relative Increase of Crew Costs

0,60 0,70 0,80 0,90

highA

highB

highC

highD

lowA

lowB

lowC

lowD

medA

medB

medC

medD

Correlation Factor Between Relative

Decrease of Reactionry Delays

Increase Crew Cost

Decrease Expected React. Delays

Figure 7.4.: Correlation Factor and Linear Regression Models for Penalty Factor

for the Expected Number of Reactionary Delays With All Simulation

Configurations

relation (Cor(C, MV)), however, is only 0.5. The results for other configurations

are very similar, compare Figure 7.6

Figure 7.7 shows the comparison of the delay propagation indicator with the

number of crew duty disruptions as well as the comparison of the expected crew

duty disruptions with the number of reactionary delays. In some cases the num-

ber of crew duty disruptions increases with a decreasing number of expected

reactionary delays, but in most cases there is a low decrease of crew duty dis-

ruptions. As expected, the Pearson’s correlation coefficient and the Spearman’s

rank correlation coefficient are both positive and low (0.27 and 0.4) for this ef-

fect. There is also no significant effect of the decrease of expected crew duty

disruptions on the number of reactionary delays.

For the deterministic robustness indicators we only present the results for the

simulation configuration highA. The results for the other configurations are very

similar. The following experiments using the indicator for restricted aircraft

changes are based on 56 crew and aircraft schedules generated for 20 different

domestic flight schedules. 20 schedules provide bases: therefore 36 schedules with

rimax

t(sk)−rit(sk)

rimax

t(sk)>0can be used for the evaluation.

101

7. Evaluation of indicators for Stability

10%

20%

30%

40%

50%

60%

70%

80%

0% 20% 40% 60% 80%

Relative Decrease of Crew Duty Violations

Relative Decrease of Expected Crew Duty

Violations

10%

20%

30%

40%

50%

60%

70%

80%

0% 1% 2% 3% 4%

Relative Decrease of Crew Duty Violations

Relative Increase of Crew Costs

Figure 7.5.: Comparison of the Relative Decrease of Expected Crew Duty dis-

ruptions as well as the Relative Increase of Crew Costs with the

Decrease of Observed Crew Duty disruptions (Configuration highA)

0,4 0,5 0,6 0,7 0,8 0,9

highA

highB

highC

highD

lowA

lowB

lowC

lowD

medA

medB

medC

medD

Correlation Factor Between the Relative

Decrease of Crew Duty Violations

Increase Crew Costs

Decrease Expected Violations

10%

20%

30%

40%

50%

60%

70%

80%

0% 1% 2% 3% 4%

Relative Decrease of Crew Duty Violations

Relative Increase of Crew Costs

Figure 7.6.: Correlation Factor and Linear Regression Models for the Stochas-

tic Robustness Measure Based on Expected Crew Duty disruptions

With All Simulation Configurations

102

7.3. Simulation Experiments

-40%

-30%

-20%

-10%

10%

20%

30%

40%

0% 50% 100%

Relative Decrease of Crew Duty Violations

Relative Decrease of Expexted

Reactionary Delays

-15%

-10%

-5%

10%

0% 20% 40% 60% 80%

Relative Decrease of

Reactionary Delays over 15 Minutes

Relative Decrease of Expected Crew Duty

Violations

Figure 7.7.: Comparison of the Robustness Indicators with the Other Robustness

Measures (Configuration highA)

Figures 7.8 show the results for the indicator based on restricted aircraft

changes. The left figure shows a high linear dependency between the relative

decrease of the penalty factor for restricted aircraft changes and the relative

decrease of the reactionary delays over 15 minutes. The exact value of the corre-

lation factor is Cor(Iπ, MP15 )=0.86. The high linear dependency means a high

predictability of the indicator on the number of reactionary delays.

The right figure shows a comparison of the relative increase of crew costs and

the relative decrease of reactionary delays. In many cases increasing the penalty

for restricted aircraft changes leads to a significant decrease in reactionary delays

without increasing the crew costs at all. A regression analysis leads to the linear

model mk= 6.4% + 6.24ck. One possible interpretation of this regression model

is, that the number of reactionary delays can be decreased on average by 6.4%

without increasing crew costs. Additionally, a decrease of reactionary delays by

6.24% can be expexted by increasing crew costs by 1%. This, however, is only a

rough estimateon, because there is only a low linear correlation.

103

7. Evaluation of indicators for Stability

10%

12%

14%

16%

18%

20%

0% 20% 40% 60% 80%

Relative Decrease of

Reactionary Delays over 15 Minutes

Relative Decrease of

Restricted Aircraft Changes

10%

12%

14%

16%

18%

20%

0,00% 0,50% 1,00%

Relative Decrease of

Reactionary Delays over 15 Minutes

Relative Increase of Crew Costs

Figure 7.8.: Comparison of the Relative Decrease of Restricted Aircraft Changes

as well as the Relative Increase of Crew Costs with the Relative

Decrease of Reactionary Delays

For the evaluation of the deterministic indicator for restricted duties 80 crew

and aircraft schedules are generated resulting in 60 schedules with positive rela-

tive decrease of the penalty factor.

The results of the evaluation of the linear correlation of the relative decrease of

the penalty factor for restricted duties with the relative decrease of the crew duty

disruptions in Figure 7.9 show a high predictability of the indicator (Cor(Iσ, MV) =

0.86). In contrast to the indicator based on restricted aircraft changes, that ba-

sed on restricted duties also leads to a high linear correlation between the re-

lative increase of crew costs and the relative decrease of crew duty disruptions

(Cor(C, MV)=0.83). A regression analysis of this relation leads to the linear

model mk= 7.7%+5.4ck. The interpretation of this model is that on average the

number of crew duty disruptions can be decreased by 7.7% without increasing

costs. Furhtermore, an increase of crew costs by 1% leads to an average decrease

in crew duty disruptions of 5.4%.

Figure 7.10 shows a comparison of the decrease of restricted aircraft changes

with the decrease of crew duty disruptions observed during simulation as well

as a comparison of the decrease of restricted crew duties with the decrease in

reactionary delays. The result is that a low decrease of restricted aircraft changes

104

7.3. Simulation Experiments

10%

20%

30%

40%

50%

60%

70%

80%

0% 20% 40% 60%

Relative Decrease of Crew Duty Violations

Relative Decrease of Restricted Duties

10%

20%

30%

40%

50%

60%

70%

80%

0% 5% 10%

Relative Decrease of Crew Duty Violations

Relative Increase of Crew Costs

Figure 7.9.: Comparison of the Relative Decrease of Restricted Duties as well as

the Relative Increase of Crew Costs with the Relative Decrease of

Crew Duty Disruptions

also leads to a decrease of crew duty disruptions, but a large decrease of restricted

aircraft changes can lead to an increase of crew duty disruptions. The linear

regression model represents this effect and crosses the horizontal axis at 47%. The

linear correlation factor, however, is only Cor(Iπ, MV) = −0.47. A decrease of

restricted duties, however, has no significant effect on the number of reactionary

delays.

The predictability and the efficiency of the stochastic indicator for the number

of reactionary delays are similar to the properties of the corresponding determi-

nistic indicator for punctuality. There are no samples with relative increase of

crow costs by more than 1% for the deterministic indicator. The comparison of

the samples with cost increase less than 1%, however, shows similar correlation

and regression properties for both indicators (Iπand It). In both cases a relative

decrease in reactionary delays of up to 20% is possible. The linear correlation

between the relative decrease of the indicator and the relative decrease of the

measure is in both cases high, between 0.8 and 0.9. The linear correlation of the

relative increase of crew costs with the relative decrease of the measure is in both

cases low, between 0.3 and 0.4.

105

7. Evaluation of indicators for Stability

-60%

-40%

-20%

20%

40%

60%

0% 20% 40% 60% 80%

Relative Decrease of Crew Duty Violations

Relative Decrease of Restricted Aircraft

Changes

-30%

-20%

-10%

10%

20%

0% 20% 40% 60% 80%

Relative Decrease of

Reactionary Delays over 15 Minutes

Relative Decrease of Restricted Duties

Figure 7.10.: Comparison of the Robustness Indicators with the Other Robust-

ness Measures

Comparison of the stochastic indicator for restricted duties with the corres-

ponding deterministic indicator shows a significantly higher efficiency of the sto-

chastic model and comparable predictability of both indicators. Unlike with the

deterministic indicator, higher decreases of crew duty disruptions can be achie-

ved with the stochastic model in both cases; without significantly increasing costs

(32% compared to 7.7%) as well as by increasing costs in steps of 1% (9.8% com-

pared to 5.4%). A detailed analysis shows that the higher values for the relative

decrease are based on higher absolute values of the decrease and not on higher

reference values. The reference values rmmax

d(s)for the stochastic model are

lower than or equal to the values of the deterministic indicator rmmax

σ(s)for all

schedules s.

Both approaches for punctuality, the stochastic as well as the deterministic,

lead to high predictability and efficiency of the robust scheduling. The determi-

nistic approach, however, need an extensive calibration in order to reach these

results. The first attempts with the deterministic indicator lead either to no

improvement of robustness at all or to very high costs. Numerous experiments

and manual calibration were needed to find a penalty function, that leads to

good compromise between robustness and costs. But even this compromise has

106

7.3. Simulation Experiments

a major disadvantage. We were not able to generate schedules with more than

1% additional costs with the iterative approach. The stochastic approach on the

other hand, lead to schedules with a wider range of the trade-off between costs

and robustness, without any calibration. In the case of crew duty disruptions,

our attempts to calibrate the deterministic indicator were not as successfull as

in the case of punctuality. The stochastic model leads without any calibration

to significantly better results. These results show the main advantage of the sto-

chastic approach. Using the stochastic model less calibration and understanding

of the effects of delay propagation by the decision maker is needed to achieve

very good results.

107

8. Simultaneous Rescheduling of

Aircraft and Crew Pairings

In this chapter a rescheduling method for crews and aircraft incorporating reac-

tionary delays and swapping resources is presented. This method can be used to

recover schedules during simulation automatically. The approach is based on a

decomposition of the integrated recovery problem, analogous to the approach in

Chapter 6. The resulting rescheduling problems for crews and aircraft are solved

by the proposed branch-and-price-and-cut framework iteratively. A new concept

for the iterative local search and additional extensions to the branch-and-price-

and-cut framework are needed in order to incorporate reactionary delays. These

concepts are presented in this chapter together with first simulation results.

8.1. Integrated Formulation for Aircraft and Crew

Rescheduling

The formulation of the integrated recovery problem is based on the individual

set partitioning formulations of the crew and aircraft recovery problems. The

set Frepresents all flights that must be covered, the sets Pand Rthe possible

crew pairings and aircraft routes. The different retiming possibilities for each

flight f∈Fare represented by a set of arcs I(f). The constraints (8.2) and

(8.3) ensure that exactly one arc of each flight is covered by a crew pairing and

an aircraft route. The constraints, that in the resulting crew as well as in the

corresponding aircraft schedule the same arcs for retimed flights are chosen is

given in (8.8). Aircraft and crew availability and flow constraints are given by

(8.4) – (8.7). The objective is to minimize the use of reserve crews, additional

delays of flights and changes to the schedule. This objective is represented by

costs associated with crew pairing and aircraft route variables.

109

8. Simultaneous Rescheduling of Aircraft and Crew Pairings

p∈P

cpxp+X

r∈R

cryr→min recovery problem (8.1)

i∈I(f)X

p∈P(f)

xp= 1 ∀f∈F(8.2)

i∈I(f)X

r∈R(f)

yr= 1 ∀f∈F(8.3)

r∈R(s)

yr≤1∀s∈SR(8.4)

r∈R(e)

yr≥1∀e∈ER(8.5)

p∈P(s)

yr≤1∀s∈SP(8.6)

p∈P(e)

yr≥1∀e∈EP(8.7)

i∈I(f)

X

p∈P(i)

xp−X

r∈R(i)

yr

= 0 ∀f∈F(8.8)

xp∈ {0,1} ∀p∈P(8.9)

yr∈ {0,1} ∀r∈R(8.10)

The introduced formulation includes both crew pairing and aircraft route va-

riables. The decomposition of the integrated problem into a classical set partitio-

ning formulation for the crew pairing problem as well as the aircraft assignment

problem leads to a connection of the resulting separated problems by additional

objective costs, regarding the usage of retimed flights. Those additional costs are

considered during the generation of the path variables. Thus the seperate crew

and aircraft recovery problems can be solved iteratively.

A retiming during the solution of the crew pairing (aircraft assignment) pro-

blem which renders an existing aircraft assignment (crew pairing) solution invalid

is called incompatible retiming. Incompatible retimings can easily be identified

110

8.2. The Iterative Solution Approach

and penalized during the generation of new path variables. Given the penalty

value cQ, the costs of crew pairing and aircraft assignment variables become

cp=cp+X

i∈I(p)X

r∈R(i)

(1 −yr)cQ,(8.11)

cr=cr+X

i∈I(r)X

p∈P(i)

(1 −xp)cQ.(8.12)

It is to be noted that after the decomposition the arcs representing the dif-

ferent retiming possibilities for a flight are no longer represented in the given

formulation. The compatibility of the schedules is now considered during the

generation of the path variables only. Additionally, the constraint of using the

earliest possible flight departure leads always to path variables with unambi-

guous costs. I.e. for a path variable it is always clear what departure times

for the covered flights are used. In contrast, in a setting where flight retimings

could be used to increase slack time, it is possible to generate two path variables

which cover the same flights but have different costs due to different departure

times and slack times. In this case it is no longer trivial always to ensure that

the better alternative of several path possibilities is generated, without explicitly

representing the different retiming possibilities in the main formulation.

8.2. The Iterative Solution Approach

Both resulting problems are solved iteratively with increasing penalty value for

retimings that lead to incompatible schedules. Algorithm 8.1 gives an overview of

the iterative method, which starts with solving a crew pairing problem without a

given aircraft assignment solution. The resulting crew costs form a lower bound

on the actual optimal costs. Based on this crew schedule, the two scheduling

problems are solved iteratively using the new cost functions c

cPand c

cRwith

increasing penalty for incompatible retimings until a feasible schedule is found.

Retiming possibilities for each flight are computed in a preprocessing step be-

fore the main algorithm with the objective of enabling new connections. These

connections are represented by new retiming arcs between each flight and earlier

flights at the same airport. If a retiming of a flight leads to a loss of previously

possible successor connections, a recursive retiming for the successor is also per-

111

8. Simultaneous Rescheduling of Aircraft and Crew Pairings

Algorithm 8.1: Iterative Method for Simultaneous Recovery

Set cQ= 0 ;/* penalty cost for incompatible retimings */

Solve crew pairing problem without a given aircraft assignment solution

while cQ≤cQ

max do

Increase cQ

Solve aircraft assignment problem with cost c

cRbased on crew schedule

if new aircraft routes do not contain any incompatible retimings then

break

Solve crew pairing problem with cost c

cPbased on aircraft schedule

if new crew pairings do not contain any incompatible retimings then

break

formed. The new arcs for retiming possibilities are added to the network as

additional flight arcs. Hence a flight is now represented by several arcs in the

network. To ensure that the earliest arc for a flight is always selected, we only

allow selected connections for the retiming arcs, which were identified during

the preprocessing step. The generation of retiming arcs can be limited by li-

miting the set of flights enabled for retiming or limiting the depth for recursive

retiming. Retiming possibilities increase the number of possible connections bet-

ween flights and therefore also the complexity of the problems. The resulting

network is heuristically searched for new path variables with the label setting

algorithm introduced in Chapter 5.

The retiming arcs are only used in the pricing subproblems and therefore need

no longer to be represented in the set partitioning formulations of the master

problems. Since, we require always to use the earliest possible flight departure,

the departure times as well as the objective value of each path variable are well-

defined.

8.3. Simulation Experiments

The proposed method was tested with domestic schedules of a European airline.

For our analysis we simulate the closure of a hub airport for two morning hours.

All flights scheduled to arrive during this time at the closed airport are randomly

delayed to arrive up to 30 minutes after the end of the disruption. Table 8.1

112

8.3. Simulation Experiments

Testcase#Primary ØPrimary #Reactionary ØReactionary #Conflicts

[h:mm] [h:mm]

dom094 4 1:36 5 0:29 6

dom104 7 1:28 14 0:36 1

dom106 10 1:38 27 1:08 13

dom117 10 1:05 23 1:20 5

dom121 7 1:38 23 0:43 -

dom124 7 1:32 28 1:35 6

dom128 3 1:47 9 1:10 1

dom171 4 1:54 7 0:48 -

Table 8.1.: Primary and Reactionary Delays After Simple Propagation

shows the number of originally delayed flights (primary delays) and the average

duration of those delays for eight problem instances with 94 - 171 flights.

As the first step of our analysis a simple propagation of all delays is performed

resulting in a set of new delays (reactionary delays) and disruptions of pairing

rules, like maximal daily flight or working time (conflicts). Table 8.1 also shows

those results. As expected the large number of conflicts and reactionary delays

shows that a simple propagation is usually not the right strategy for coping with

such severe disruption. The main point of this analysis is to demonstrate the

close interdependency of crews and aircraft in the used schedules, which leads to

the high number of reactionary delays.

All used schedules are one day’s duration. In our experiments we assume, that

the occurrence of the disruption is known several hours in advance. As a result

we use the whole schedule for the rescheduling and fix only the airports and times

where the aircraft routes and crew pairings start at the beginning of the schedule

and finish at its end.

The proposed rescheduling method does not automatically cancel flights nor

uses any reserve aircraft. The used objective function is intended to minimize

the number of reserve crews. Assigning a task to another pairing (task swap) is

usually preferred to delaying a task; thus delays are only performed for feasibility

reasons. Crew swaps, where two pairings swap their ending stations and times

are not needed in this test setting, because the recovery period includes the whole

schedule. In detail, the following weights were used:

113

8. Simultaneous Rescheduling of Aircraft and Crew Pairings

Testcase #Reserve #Swaps #Reactionary ØReactionary #Conflicts

[h:mm]

dom094 - 6 5 0:48 -

dom104 - 16 7 0:40 -

dom106 1 27 14 0:30 -

dom117 - 41 4 0:38 -

dom121 1 10 9 0:52 -

dom124 - 19 13 0:45 -

dom128 - 9 4 0:36 -

dom171 - 2 2 0:51 -

Table 8.2.: Reactionary Delays and Schedule Changes After Rescheduling

•reserve crew: 200

•task swap: 5

•delayed flight: 5

•one minute delay: 1

All schedules could be rescheduled using the available aircraft resources. Table

8.2 shows a comparison of the rescheduling results performed by the proposed

method and by a simple propagation. In all cases all conflicts regarding crew pai-

ring rules could be resolved. In two cases a reserve crew was scheduled starting

and ending at the same crew base. The number of retimed flights (reactionary

delays) is in most cases significantly lower in comparison to the simple propaga-

tion. In one case more total reactionary delay time was needed to resolve the

conflicts, but in most cases the total reactionary delay time as well as the average

delay duration are significantly lower. The number of tasks assigned to a pairing

other than original (swaps) varies greatly, but also closely correlates with the

number of reactionary delays saved.

The results probably differ from a practical solution but match the used weights

in the objective. They show that the method is capable of minimizing reactionary

delays as well as constructing compatible schedules at the same time, even if large

changes to both schedules are needed.

114

9. Summary and Conclusions

In this work we addressed simultaneous scheduling of aircraft and crews under

consideration of disruption. These tactical scheduling tasks are usually performed

several months prior to the day of operations. Both schedules are easily disrupted

on the day of operations, because of restrictions on maintenance of aircraft and

working time of crews. These disruptions are hard to recover and often lead to

additional delays. Both problems are also closely interdependent due to crews

changing aircraft on the day of operations. Such aircraft changes can lead to

additional propagation of delays between aircraft, i.e. following the crew from one

to another aircraft. In Chapter 2we describe the different sources of disruptions

as well as operational effects and possible responses.

The study of literature to date in Chapter 3shows that simultaneous schedu-

ling of aircraft and crews can greatly reduce costs as well as delay propagation.

The crew and aircraft scheduling problems, however, are both computationally

very difficult and therefore usually solved sequentially. Most existing approaches

for robust scheduling of aircraft and crews are based on indicators for delay pro-

pagation. But most of these approaches only measure local effects of delay propa-

gation. Moreover, there is no common framework for evaluation and comparison

of different approaches for robust scheduling. On this analysis we developed in

Chapter 4the following three research objectives for this work: (1) development

of a heuristic approach to simultaneous scheduling of aircraft and crews, which

incorporates a more exact measure of delay propagation using historical data,

(2) development of an evaluation framework to compare the new approach to

robust scheduling with existing approaches and (3) development of a new opti-

mization method for aircraft and crew schedules based on well-founded concepts

from literature in order efficiently to solve the robust scheduling problems.

In Chapter 5we proposed a common optimization method for the deterministic

tactical scheduling problems for crews and aircraft as well as the corresponding

115

9. Summary and Conclusions

rescheduling problems. The proposed branch-and-price-and-cut method was used

to efficiently solve the named problems as well as the stochastic problems introdu-

ced in this work. The pricing subproblems were modelled as resource-constrained

shortest-path problems and solved by a dynamic programming approach. In or-

der to cope with the complex problems, we presented a new backtracking scheme

as well as a new label categorizing technique for the dynamic programming al-

gorithm. We showed that both techniques are crucial to solving the stochastic

pricing subproblem efficiently but can also be applied to problems without sto-

chastic scenarios. Other important developments in this work were the heuristic

branching and node selection strategies as well as the consideration of subset

row inequalities in the branch-and-price-and-cut method. The heuristic diving

strategies in combination with problem fixing were crucial to efficiently solving

large-scale scheduling problems and corresponds to the third research objective.

In accordance with the first research objective we presented in Chapter 6an

integrated stochastic model for aircraft assignment and crew pairing with the

objective of minimizing planned crew costs as well as total delay propagation

between aircraft and crews. The integrated model incorporates a very detailed

representation of the delay propagation on the day of operations. But, it is also

computationally very difficult due to non-linear constraints and binary decision

variables. We proposed to solve the integrated model heuristically by decompo-

sing it into separate stochastic problems for crews and aircraft, modelling the

interdependencies of the two problems by a common objective function and ap-

plying an iterative solution approach. The heuristic solution approach enabled

us to generate robust aircraft and crew schedules for weekly scheduling problems

with more than 250 flights in less than four hours. Despite the decomposition

of the problem and the heuristic nature of our solution approach it incorporates

the most exact representation of delay propagation between aircraft and crews in

current literature. The main property of the stochastic problems resulting from

our decomposition is that the delay scenarios only need be considered in the

pricing subproblems. We showed that the additional constraints modelling delay

propagation can easily be modelled by the resource constrained shortest-path

problem and thus enable us to reuse existing dynamic programming methods in

the pricing subproblem. The result is an increase of the average solution time of

the iterative approach by only 74% for the stochastic model, than in a determins-

116

tic model (from 2 hours to 3.5 hours). In future research the solution times for

the stochastic problem can be decreased significantly by incorporating sampling

methods for the consideration of delay scenarios.

Chapter 7we devoted to the second objective and here presented a simulation

model as well as a framework within which to compare different approaches for

robust scheduling. With this framework we compared the stochastic scheduling

approach with a similar deterministic approach to robust scheduling. The de-

terministic approach penalizes short slack between two flights if the crews are

scheduled to change aircraft. This approach is very similar to the method pro-

posed by Weide [2009]. The deterministic model does not consider any delay

scenarios or delay propagation and thus leads to shorter solution times. We eva-

luated the approaches by computing the operational performance of schedules.

The later is measured by simulating crew and aircraft schedules and comparing

the number of reactionary delays as well as the number of crew duty disrup-

tions, which are not resolved by delay propagation. We proposed to measure the

quality of the approaches for robustness by evaluating the predictability and the

efficiency of those approaches. Both approaches to increasing the punctuality, the

stochastic and the deterministic, show a strong mathematical relation between

the indicated values during scheduling and corresponding punctuality measures

in the simulation. The approaches are also equally efficient, i.e. the relation

between increase of robustness and crew costs is comparable. The deterministic

indicators, however, need extensive calibration to reach comparable results.

Despite higher solution times for the stochastic model for increasing punctua-

lity, this model offers great advantages and possibilities for future research. The

two main advantages are automatic calibration and extensibility of the stochastic

model. Whereas the stochastic model automatically computes propagated delays

based on the delay scenarios used, the performance of the deterministic model

depends on the selected minimal and maximal slack during an aircraft change.

For different delay distributions or schedule properties these values need to be

adjusted. Moreover, on the propagation model presented in this work it is pos-

sible to compute probabilities for severe delays and to compute delay statistics

for certain flights and airports. This information may be used for positioning of

reserve crews, schedule redesign and evaluation of rescheduling actions.

117

9. Summary and Conclusions

In Chapter 8we proposed an approach to rescheduling aircraft and crews on

the day of operations. The presented approach solves the recovery problems for

crews and aircraft iteratively using flight retiming. The proposed decomposition

of the integrated problem leads to a reduced complexity and therefore to lower

solution times of the iterative approach than with methods for the integrated

problem. All test cases in our test set could be solved in few a seconds or

minutes using our prototype solver. This approach was not an original objective

of this work. The main idea of this approach resulted from the experience with

the optimization methods as well as the approaches to robust scheduling. The

rescheduling approach could be realized very quickly by reusing the optimization

methods from Chapter 5.

Future research includes the development of indicators of flexibility and the

extension of the evaluation framework to measure schedule flexibility, e.g. by

the approach to rescheduling proposed in this work. Examples for indicators

of flexibility are move-up, stand-by and reserve crews, which may be schedules

at crew bases based on expected delay. Alternatively, full recovery procedures

could be considered during scheduling, e.g. as a subproblem with the objective

of evaluating the flexibility of full or partial schedules. Additional research is

needed to find possibilities of incorporating multiple objectives, e.g. stability

and flexibility indicators, in the iterative solution approach to the integrated

model.

In this work we simultaneously schedule crew pairings and aircraft. In future

research additional airline scheduling problems may be integrated into simulta-

neous scheduling, e.g. fleet assignment and flight retiming. The fleet assignment

problem may be integrated with the objective of increasing possibilities for re-

covery actions, because aircraft and crew swaps are easier to perform within the

same fleet. Flight retiming can be used to increase slack between pairs of flights,

where it cannot efficiently be obtained by crew and aircraft scheduling.

Finally, an important aspect of future research in robust scheduling shall be

the estimation of the impact of delayed flights. Today most approaches treat

all delayed flights equally or even totalise the duration of all delays. In practice

delays often have very different side-effects and costs, e.g. stranded passengers

and new bottlenecks at airport facilities. Thus additional research is needed the

118

better to estimate the impact of delays in order to be able to deal with "right"

delays at "right" cost.

119

Appendix A.

European Regulations on Crew

Work-Time

Excerpt from REGULATION (EC) No 1899/2006 OF THE

EUROPEAN PARLIAMENT AND OF THE COUNCIL

SUBPART Q

OPS 1.1090

Objective and scope

1. An operator shall establish a flight and duty time limitations and rest

scheme (FTL) for crew members.

2. An operator shall ensure that for all its flights:

a) The flight and duty time limitations and rest scheme is in accordance

with both:

i. the provisions of this subpart; and

ii. any additional provisions that are applied by the Authority in

accordance with the provisions of this subpart for the purpose of

maintaining safety.

b) Flights are planned to be completed within the allowable flight duty

period taking into account the time necessary for pre-flight duties, the

flight and turn-around times.

c) Duty rosters will be prepared and published sufficiently in advance to

provide the opportunity for crew members to plan adequate rest.

121

Appendix A. European Regulations on Crew Work-Time

3. Operators’ responsibilities

a) An operator shall nominate a home base for each crew member.

b) Operators shall be expected to appreciate the relationship between

the frequencies and pattern of flight duty periods and rest periods

and give due consideration to the cumulative effects of undertaking

long duty hours interspersed with minimum rest.

c) Operators shall allocate duty patterns which avoid such undesirable

practices as alternating day/night duties or the positioning of crew

members so that a serious disruption of established sleep/work pattern

occurs.

d) Operators shall plan local days free of duty and notify crew members

in advance.

e) Operators shall ensure that rest periods provide sufficient time to en-

able crew to overcome the effects of the previous duties and to be well

rested by the start of the following flight duty period.

f) Operators shall ensure flight duty periods are planned to enable crew

members to remain sufficiently free from fatigue so they can operate

to a satisfactory level of safety under all circumstances.

4. Crew members’ responsibilities

a) A crew member shall not operate an aeroplane if he/she knows that

he/she is suffering from or is likely to suffer from fatigue or feels unfit,

to the extent that the flight may be endangered.

b) Crew members should make optimum use of the opportunities and

facilities for rest provided and plan and use their rest periods properly.

5. Responsibilities of civil aviation authorities

a) Variations

i. Subject to the provisions of Article 8, the Authority may grant

variations to the requirements in this subpart in accordance with

applicable laws and procedures within the Member States concer-

ned and in consultation with interested parties.

122

ii. Each operator will have to demonstrate to the Authority, using

operational experience and taking into account other relevant fac-

tors such as current scientific knowledge, that its request for a

variation produces an equivalent level of safety.

Such variations will be accompanied with suitable mitigation measures where

appropriate.

OPS 1.1095

Definitions

For the purposes of this Regulation, the following definitions shall apply:

1. Augmented flight crew

A flight crew which comprises more than the minimum number required

for the operation of the aeroplane and in which each flight crew member

can leave his/her post and be replaced by another appropriately qualified

flight crew member.

2. Block time

The time between an aeroplane first moving from its parking place for

the purpose of taking off until it comes to rest on the designated parking

position and all engines or propellers are stopped.

3. Break

A period free of all duties, which counts as duty, being less than a rest

period.

4. Duty

Any task that a crew member is required to carry out associated with the

business of an AOC holder. Unless where specific rules are provided for

by this Regulation, the Authority shall define whether and to what extent

standby is to be accounted for as duty.

5. Duty period

A period which starts when a crew member is required by an operator to

commence a duty and ends when the crew member is free from all duties.

123

Appendix A. European Regulations on Crew Work-Time

6. Flight duty period

A flight duty period (FDP) is any time during which a person operates in an

aircraft as a member of its crew. The FDP starts when the crew member is

required by an operator to report for a flight or a series of flights; it finishes

at the end of the last flight on which he/she is an operating crew member.

7. Home base

The location nominated by the operator to the crew member from where

the crew member normally starts and ends a duty period or a series of duty

periods and where, under normal conditions, the operator is not responsible

for the accommodation of the crew member concerned.

8. Local day

A 24-hour period commencing at 00:00 local time.

9. Local night

A period of eight hours falling between 22:00 hours and 08:00 hours local

time.

10. A single day free of duty

A single day free of duty shall include two local nights. A rest period may

be included as part of the day off.

11. Operating crew member

A crew member who carries out his/her duties in an aircraft during a flight

or during any part of a flight.

12. Positioning

The transferring of a non-operating crew member from place to place, at

the behest of the operator, excluding travelling time. Travelling time is

defined as:

•time from home to a designated reporting place and vice versa;

•time for local transfer from a place of rest to the commencement of

duty and vice versa.

124

13. Rest period

An uninterrupted and defined period of time during which a crew member

is free from all duties and airport standby.

14. Standby:

A defined period of time during which a crew member is required by the

operator to be available to receive an assignment for a flight, positioning

or other duty without an intervening rest period.

15. Window of circadian low (WOCL):

The window of circadian low (WOCL) is the period between 02:00 hours

and 05:59 hours. Within a band of three time zones the WOCL refers to

home base time. Beyond these three time zones the WOCL refers to home

base time for the first 48 hours after departure from home base time zone,

and to local time thereafter.

OPS 1.1100

Flight and duty limitations

1. Cumulative duty hours

An operator shall ensure that the total duty periods to which a crew mem-

ber is assigned do not exceed:

a) 190 duty hours in any 28 consecutive days, spread as evenly as prac-

ticable throughout this period; and

b) 60 duty hours in any seven consecutive days.

2. Limit on total block times

An operator shall ensure that the total block times of the flights on which

an individual crew member is assigned as an operating crew member does

not exceed

•900 block hours in a calendar year; or

•100 block hours in any 28 consecutive days.

125

Appendix A. European Regulations on Crew Work-Time

OPS 1.1105

Maximum daily flight duty period (FDP)

1. General:

a) This OPS does not apply to single pilot operations and to emergency

medical service operations.

b) An operator shall specify reporting times that realistically reflect the

time for safety related ground duties as approved by the Authority.

c) The maximum basic daily FDP is 13 hours.

d) These 13 hours will be reduced by 30 minutes for each sector from the

third sector onwards with a maximum total reduction of two hours.

e) When the FDP starts in the WOCL, the maximum stated in point

1c and point 1d will be reduced by 100% of its encroachment up to a

maximum of two hours. When the FDP ends in or fully encompasses

the WOCL, the maximum FDP stated in point 1c and point 1d will

be reduced by 50% of its encroachment.

2. Extensions:

a) The maximum daily FDP can be extended by up to one hour.

b) Extensions are not allowed for a basic FDP of six sectors or more.

c) Where an FDP encroaches on the WOCL by up to two hours exten-

sions are limited to up to four sectors.

d) Where an FDP encroaches on the WOCL by more than two hours

extensions are limited to up to two sectors.

e) The maximum number of extensions is two in any seven consecutive

days.

f) Where an FDP is planned to use an extension pre and post flight

minimum rest is increased by two hours or post flight rest only is

increased by four hours. Where the extensions are used for consecutive

FDPs the pre and post rest between the two operations shall run

consecutively.

126

g) When an FDP with extension starts in the period 22:00 to 04:59 hours

the operator will limit the FDP to 11.45 hours.

3. Cabin Crew

a) For cabin crew being assigned to a flight or series of flights, the FDP

of the cabin crew may be extended by the difference in reporting time

between cabin crew and flight crew, as long as the difference does not

exceed one hour.

4. Operational robustness

a) Planned schedules must allow for flights to be completed within the

maximum permitted flight duty period. To assist in achieving this

operators will take action to change a schedule or crewing arrange-

ments at the latest where the actual operation exceeds the maximum

FDP on more than 33% of the flights in that schedule during a sche-

duled seasonal period.

5. Positioning

a) All the time spent on positioning is counted as duty.

b) Positioning after reporting but prior to operating shall be included as

part of the FDP but shall not count as a sector.

c) A positioning sector immediately following operating sector will be

taken into account for the calculation of minimum rest as defined in

OPS 1.1110 (1a) and (1b).

6. Extended FDP (split duty)

a) The Authority may grant approval to an operation based on an ex-

tended FDP including a break, subject to the provisions of Article

b) Each operator will have to demonstrate to the Authority, using opera-

tional experience and taking into account other relevant factors, such

as current scientific knowledge, that its request for an extended FDP

produces an equivalent level of safety.

127

Appendix A. European Regulations on Crew Work-Time

OPS 1.1110

Rest

1. Minimum rest

a) at least as long as the preceding duty period or 12 hours whichever is

the greater;

b) The minimum rest which must be provided before undertaking a flight

duty period starting away from home base shall be at least as long as

the preceding duty period or 10 hours whichever is the greater; when

on minimum rest away from home base, the operator must allow for

an eight-hour sleep opportunity taking due account of travelling and

other physiological needs;

c) An operator will ensure that effects on crew members of time zone

differences will be compensated by additional rest, as regulated by

the Authority subject to the provisions of Article 8.

d) Notwithstanding (1a) and (1b) and subject to the provisions of Article

8, the Authority may grant reduced rest arrangements.

e) Each operator will have to demonstrate to the Authority, using opera-

tional experience and taking into account other relevant factors, such

as current scientific knowledge, that its request for reduced rest ar-

rangements produces an equivalent level of safety.

2. Rest periods

a) An operator shall ensure that the minimum rest provided as outlined

above is increased periodically to a weekly rest period, being a 36-hour

period including two local nights, such that there shall never be more

than 168 hours between the end of one weekly rest period and the

start of the next. As an exception to OPS 1.1095 (9), the Authority

may decide that the second of those local nights may start from 20:00

hours if the weekly rest period has a duration of at least 40 hours.

OPS 1.1115

Extension of flight duty period due to in-flight rest

128

1. Subject to the provisions of Article 8 and providing each operator demons-

trates to the Authority, using operational experience and taking into ac-

count other relevant factors such as current scientific knowledge, that its

request produces an equivalent level of safety:

a) Flight crew augmentation

the Authority shall set the requirements in connection with the aug-

mentation of a basic flight crew for the purpose of extending the flight

duty period beyond the limits in OPS 1.1105 above;

b) Cabin crew

the Authority shall set the requirements in connection with the mi-

nimum in-flight rest by cabin crew member(s) when the FDP goes

beyond the limitations in OPS 1.1105;

OPS 1.1120

Unforeseen circumstances in actual flight operations — commander’s

discretion

1. Taking into account the need for careful control of these instances implied

underneath, during the actual flight operation, which starts at the reporting

time, the limits on flight duty, duty and rest periods prescribed in this

subpart may be modified in the event of unforeseen circumstances. Any

such modifications must be acceptable to the commander after consultation

with all other crew members and must, in all circumstances, comply with

the following:

a) The maximum FDP referred to in OPS 1.1105(1.3) above may not

be increased by more than two hours unless the flight crew has been

augmented, in which case the maximum flight duty period may be

increased by not more than three hours;

i. If on the final sector within a FDP unforeseen circumstances oc-

cur after take off that will result in the permitted increase being

exceeded, the flight may continue to the planned destination or

alternate;

129

Appendix A. European Regulations on Crew Work-Time

ii. In the event of such circumstances, the rest period following the

FDP may be reduced but never below the minimum rest defined

in OPS 1.1110(1b) of this subpart;

b) The Commander shall, in case of special circumstances, which could

lead to severe fatigue, and after consultation with the crew members

affected, reduce the actual flight duty time and/or increase the rest

time in order to eliminate any detrimental effect on flight safety;

c) An operator shall ensure that:

i. The Commander submits a report to the operator whenever a

FDP is increased by his/her discretion or when a rest period is

reduced in actual operation and

ii. Where the increase of a FDP or reduction of a rest period exceeds

one hour, a copy of the report, to which the operator must add

his comments, is sent to the Authority no later than 28 days after

the event.

OPS 1.1125

Standby

1. Airport standby

a) A crew member is on airport standby from reporting at the normal

report point until the end of the notified standby period.

b) Airport standby will count in full for the purposes of cumulative duty

hours.

c) Where airport standby is immediately followed by a flight duty, the

relationship between such airport standby and the assigned flight duty

shall be defined by the Authority. In such a case, airport standby shall

be added to the duty period referred to in OPS 1.1110 under points

1.1 and 1.2 for the purposes of calculating minimum rest.

d) Where the airport standby does not lead to assignment on a flight

duty, it shall be followed at least by a rest period as regulated by the

Authority.

130

e) While on airport standby the operator will provide to the crew member

a quiet and comfortable place not open to the public.

2. Other forms of standby (including standby at hotel)

a) Subject to the provisions of Article 8, all other forms of standby shall

be regulated by the Authority, taking into account the following:

i. All activity shall be rostered and/or notified in advance.

ii. The start and end time of the standby shall be defined and notified

in advance.

iii. The maximum length of any standby at a place other than a

specified reporting point shall be determined.

iv. Taking into account facilities available for the crew member to rest

and other relevant factors, the relationship between the standby

and any assigned flight duty resulting from the standby shall be

defined.

v. The counting of standby times for the purposes of cumulative

duty hours shall be defined.

OPS 1.1130

Nutrition

A meal and drink opportunity must occur in order to avoid any detriment to

a crew member’s performance, especially when the FDP exceeds six hours.

OPS 1.1135

Flight duty, duty and rest period records

1. An operator shall ensure that crew member’s records include:

a) block times;

b) start, duration and end of each duty or flight duty periods;

c) rest periods and days free of all duties;

and are maintained to ensure compliance with the requirements of this

subpart; copies of these records will be made available to the crew member

upon request.

131

Appendix A. European Regulations on Crew Work-Time

2. If the records held by the operator under paragraph 1 do not cover all of

his/her flight duty, duty and rest periods, the crew member concerned shall

maintain an individual record of his/her

a) block times;

b) start, duration and end of each duty or flight duty periods; and

c) rest periods and days free of all duties.

3. A crew member shall present his/her records on request to any operator

who employs his/her services before he/she commences a flight duty period.

4. Records shall be preserved for at least 15 calendar months from the date

of the last relevant entry or longer if required in accordance with national

laws.

5. Additionally, operators shall separately retain all aircraft commander’s dis-

cretion reports of extended flight duty periods, extended flight hours and

reduced rest periods for at least six months after the event.

Source: European Parliament and the Council [2006]

132

Appendix B.

Standard IATA Delay Codes

Excerpt from IATA – Airport Handling Manual (Chapter

AHM 011)

Others

00-05 AIRLINE INTERNAL CODES

06 (OA) NO GATE/STAND AVAILABILITY DUE TO OWN AIRLINE ACTIVITY

09 (SG) SCHEDULED GROUND TIME LESS THAN DECLARED MINIMUM

GROUND TIME

Passenger and Baggage

11 (PD) LATE CHECK-IN, acceptance after deadline

12 (PL) LATE CHECK-IN, congestions in check-in area

13 (PE) CHECK-IN ERROR, passenger and baggage

14 (PO) OVERSALES, booking errors

15 (PH) BOARDING, discrepancies and paging, missing checked-in passenger

16 (PS) COMMERCIAL PUBLICITY/PASSENGER CONVENIENCE, VIP, press,

ground meals and missing personal items

17 (PC) CATERING ORDER, late or incorrect order given to supplier

18 (PB) BAGGAGE PROCESSING, sorting etc.

133

Appendix B. Standard IATA Delay Codes

Cargo and Mail

21 (CD) DOCUMENTATION, errors etc.

22 (CP) LATE POSITIONING

23 (CC) LATE ACCEPTANCE

24 (CI) INADEQUATE PACKING

25 (CO) OVERSALES, booking errors

26 (CU) LATE PREPARATION IN WAREHOUSE

27 (CE) DOCUMENTATION, PACKING etc (Mail Only)

28 (CL) LATE POSITIONING (Mail Only)

29 (CA) LATE ACCEPTANCE (Mail Only)

Aircraft and Ramp Handling

31 (GD) AIRCRAFT DOCUMENTATION LATE/INACCURATE, weight and ba-

lance, general declaration, pax manifest, etc.

32 (GL) LOADING/UNLOADING, bulky, special load, cabin load, lack of loading staff

33 (GE) LOADING EQUIPMENT, lack of or breakdown, e.g. container pallet loader,

lack of staff

34 (GS) SERVICING EQUIPMENT, lack of or breakdown, lack of staff, e.g. steps

35 (GC) AIRCRAFT CLEANING

36 (GF) FUELLING/DEFUELLING, fuel supplier

37 (GB) CATERING, late delivery or loading

38 (GU) ULD, lack of or serviceability

39 (GT) TECHNICAL EQUIPMENT, lack of or breakdown, lack of staff, e.g. pushback

134

Technical and Aircraft Equipment

41 (TD) AIRCRAFT DEFECTS.

42 (TM) SCHEDULED MAINTENANCE, late release.

43 (TN) NON-SCHEDULED MAINTENANCE, special checks and/or additional

works beyond normal maintenance schedule.

44 (TS) SPARES AND MAINTENANCE EQUIPMENT, lack of or breakdown.

45 (TA) AOG SPARES, to be carried to another station.

46 (TC) AIRCRAFT CHANGE, for technical reasons.

47 (TL) STAND-BY AIRCRAFT, lack of planned stand-by aircraft for technical rea-

sons.

48 (TV) SCHEDULED CABIN CONFIGURATION/VERSION ADJUSTMENTS.

Damage to Aircraft & EDP/Automated Equipment Failure

51 (DF) DAMAGE DURING FLIGHT OPERATIONS, bird or lightning strike, tur-

bulence, heavy or overweight landing, collision during taxiing

52 (DG) DAMAGE DURING GROUND OPERATIONS, collisions (other than during

taxiing), loading/off-loading damage, contamination, towing, extreme weather

conditions

55 (ED) DEPARTURE CONTROL

56 (EC) CARGO PREPARATION/DOCUMENTATION

57 (EF) FLIGHT PLANS

135

Appendix B. Standard IATA Delay Codes

Flight Operations and Crewing

61 (FP) FLIGHT PLAN, late completion or change of, flight documentation

62 (FF) OPERATIONAL REQUIREMENTS, fuel, load alteration

63 (FT) LATE CREW BOARDING OR DEPARTURE PROCEDURES, other than

connection and standby (flight deck or entire crew)

64 (FS) FLIGHT DECK CREW SHORTAGE, sickness, awaiting standby, flight time

limitations, crew meals, valid visa, health documents, etc.

65 (FR) FLIGHT DECK CREW SPECIAL REQUEST, not within operational requi-

rements

66 (FL) LATE CABIN CREW BOARDING OR DEPARTURE PROCEDURES, other

than connection and standby

67 (FC) CABIN CREW SHORTAGE, sickness, awaiting standby, flight time limita-

tions, crew meals, valid visa, health documents, etc.

68 (FA) CABIN CREW ERROR OR SPECIAL REQUEST, not within operational

requirements

69 (FB) CAPTAIN REQUEST FOR SECURITY CHECK, extraordinary

Weather

71 (WO) DEPARTURE STATION

72 (WT) DESTINATION STATION

73 (WR) EN ROUTE OR ALTERNATE

75 (WI) DE-ICING OF AIRCRAFT, removal of ice and/or snow, frost prevention ex-

cluding unserviceability of equipment

76 (WS) REMOVAL OF SNOW, ICE, WATER AND SAND FROM AIRPORT

77 (WG) GROUND HANDLING IMPAIRED BY ADVERSE WEATHER CONDI-

TIONS

136

Air Traffic Flow Management Restrictions

81 (AT) ATFM due to ATC EN-ROUTE DEMAND/CAPACITY, standard de-

mand/capacity problems

82 (AX) ATFM due to ATC STAFF/EQUIPMENT EN-ROUTE, reduced capacity

caused by industrial action or staff shortage, equipment failure, military exer-

cise or extraordinary demand due to capacity reduction in neighbouring area

83 (AE) ATFM due to RESTRICTION AT DESTINATION AIRPORT, airport

and/or runway closed due to obstruction, industrial action, staff shortage,

political unrest, noise abatement, night curfew, special flights

84 (AW) ATFM due to WEATHER AT DESTINATION

Airport and Governmental Authorities

85 (AS) MANDATORY SECURITY

86 (AG) IMMIGRATION, CUSTOMS, HEALTH

87 (AF) AIRPORT FACILITIES, parking stands, ramp congestion, lighting, buildings,

gate limitations, etc.

88 (AD) RESTRICTIONS AT AIRPORT OF DESTINATION, airport and/or runway

closed due to obstruction, industrial action, staff shortage, political unrest,

noise abatement, night curfew, special flights

89 (AM) RESTRICTIONS AT AIRPORT OF DEPARTURE WITH OR WITHOUT

ATFM RESTRICTIONS, including Air Traffic Services, start-up and push-

back, airport and/or runway closed due to obstruction or weather, industrial

action, staff shortage, political unrest, noise abatement, night curfew, special

flights

137

Appendix B. Standard IATA Delay Codes

Reactionary

91 (RL) LOAD CONNECTION, awaiting load from another flight

92 (RT) THROUGH CHECK-IN ERROR, passenger and baggage

93 (RA) AIRCRAFT ROTATION, late arrival of aircraft from another flight or pre-

vious sector

94 (RS) CABIN CREW ROTATION, awaiting cabin crew from another flight

95 (RC) CREW ROTATION, awaiting crew from another flight (flight deck or entire

crew)

96 (RO) OPERATIONS CONTROL, re-routing, diversion, consolidation, aircraft

change for reasons other than technical

Miscellaneous

97 (MI) INDUSTRIAL ACTION WITH OWN AIRLINE

98 (MO) INDUSTRIAL ACTION OUTSIDE OWN AIRLINE, excluding ATS

99 (MX) OTHER REASON, not matching any code above

Source: IATA [2008], EUROCONTROL [2009]

138

Appendix C.

Distributions for Primary Delays

The generation of primary delays is based on historical data of a major European

airline. All delays are classified according to the IATA delay codes. From these

data, we derive theoretical distributions for duration and frequency of delays for

use in our simulation model. We group the delay causes according to delay type

as well as place and frequency of occurrence. Then, for each delay group the

empirical data of delays are used to perform an automatic distribution fitting

for duration and frequency of delays. In Section 7.1 we gave a brief overview of

the analysis and results; here we present the detailed results. For details of the

analysis method we refer to Spengler [2009].

Airline internal delay causes vary from airline to airline. These delay causes

are mostly related to processes or equipment failure, which is specific to

the airline, e.g. for identifying messages of automatic systems or problems

with specific aircraft equipment. In the examined data these are the most

frequent delays, but also have the shortest expected duration. The delays

last on average 2 minutes and obviously follow a uniform distribution. Thus

no distribution fitting and testing of goodness is performed in this case.

IATA delay codes: 0 – 5

Occurrence probability: π= 12.6%

Average duration: 2 minutes

Distribution of duration: Uniform distribution between 1, 2 and 3 mi-

nutes.

Aircraft, passenger and baggage handling delay causes describe problems cau-

sed by individual passengers, airlines, suppliers as well as problems with

139

Appendix C. Distributions for Primary Delays

the equipment needed for aircraft handling at the gate. Examples are late

check-in of passengers, overbooking of the flight and delayed cleaning or ca-

tering by suppliers. These delay causes include most delay causes applying

to the airport ground handling process described in Section 2.2.1 (pp. 16).

IATA delay codes: 11 – 18 and 31 – 39

Occurrence probability: π= 5.7%

Average duration: 10 minutes

Distribution of duration: Log-logistic distribution with α= 2.82,β= 8.33

and γ= 0.50;Di≈5= 0.06739.

Aircraft maintenance delay causes describe the breakdown of the aircraft with

consequential unscheduled aircraft maintenance as well as problems during

the scheduled aircraft maintenance, e.g. breakdown of maintenance equip-

ment or lack of planned stand-by aircraft for technical reasons. The delays

in this group are rare but very serious, i.e. of long average duration. The

two delay code ranges 41 – 48 and 51– 52 actually have different average

durations, e.g. the average delay for codes 51 and 52 is 70 minutes. The

common distribution, however, is extremely good, approximated by the

Log-normal distribution presented.

IATA delay codes: 41 – 48, 51 and 52

Occurrence probability: π= 2.7%

Average duration: 34 minutes

Distribution of duration: Log-normal distribution with σ= 1.05,µ= 2.95

and γ= 0.85;Di≈5= 0.02708.

Flight operations and Crewing delay causes describe operational problems, e.g.

extraordinary security checks or late completion of flight plan, as well as

late and missing crew for reasons other than reactionary, e.g. missing

documents, sickness or disruption of individual flight time limitations.

IATA delay codes: 61 – 69

Occurrence probability: π= 1.28%

Average duration: 13 minutes

Distribution of duration: Log-logistic distribution with α= 2.30,β= 8.94

and γ= 0.91;Di≈5= 0.04765.

140

Automated equipment failure delay causes describe problems with computer

systems and automated equipment used during aircraft handling, e.g. de-

parture control system, cargo preparation and documentation, baggage sor-

ting and other.

IATA delay codes: 55 – 57

Occurrence probability: π= 1.1%

Average duration: 13 minutes

Distribution of duration: Log-logistic distribution with α= 2.37,β= 8.89

and γ= 0.72;Di≈5= 0.065098.

No gates and wrong scheduled ground time are two, very rare delay causes.

In the first case the gates are missing due to own airline activity. In the

second case the scheduled ground time is less than the declared minimum.

IATA delay codes: 6 and 9

Occurrence probability: π= 0.34%

Average duration: 11 minutes

Distribution of duration: Log-normal distribution with σ= 0.75,µ= 2.14

and γ= 0.32;Di≈5= 0.03695.

Weather delay causes describe the ATFM restrictions due to weather as well

as restrictions at airports due to weather, e.g. removal of snow and ice

from aircraft and airport. The average duration of such delays is long and

the probability of occurrence differs according to season, less than 2% in

summer and up to 12% in winter. We therefore propose three probability

distributions for π: one for the period April – October, one for the period

November – March and one for the whole year.

IATA delay codes: 71 – 79 and 84

Occurrence probability: πis a random variable with the following seasonal

distribution:

•Whole year: Log-normal distribution with σ= 0.98 and µ=−3.45

•April – October: Log-logistic distribution with α= 2.217 and

β= 0.02

•November – March: Log-normal distribution with σ= 0.97 and

µ=−2.99

141

Appendix C. Distributions for Primary Delays

Average duration: 25 minutes

Distribution of duration: Log-logistic distribution with α= 1.99,β= 15.07

and γ= 0.92;Di≈5= 0.02361.

Airspace congestion delay causes describe the ATFM restrictions due to redu-

ced capacity en-route. Reasons for reduced capacity include high demand

by airlines, staff shortage at the control centers and industrial or military

action. The analysis of the data shows a significantly higher probability

of delay in the summer than winter months. This observation match the

seasonal effects of total traffic and delays observed by EUROCONTROL,

see Subsection 2.2.2 (pp. 18).

IATA delay codes: 81 and 82

Occurrence probability: πis a random variable with the following seasonal

distribution:

•Whole year: Log-normal distribution with σ= 0.57 and µ=−3.06

•April – October: Log-normal distribution with σ= 0.46 and

µ=−2.88

•November – March: Log-normal distribution with σ= 0.97 and

µ=−2.99

Average duration: 13 minutes

Distribution of duration: Log-logistic distribution with α= 1.99,β= 15.07

and γ= 0.92;Di≈5= 0.05258.

Airport congestion delay causes describe general capacity reduction at the des-

tination airport as well as the departure airport. Such capacity reductions

affect all flights at those airports. Examples of causes of capacity decrease

are increased demand, gate limitations, industrial actions and staff shor-

tage at immigration or security stations. The probability of such delays

varies greatly from airport to airport. This effect is demonstrated by more

detailed analysis of the two hub airports in the network. Thus two possibi-

lities of modelling the occurrence probability are presented next. The first

distribution completely models the average occurrence probability for all

airports in the network. Alternatively, the occurrence probability can be

represented by three distributions. Two distributions model the occurrence

142

probability of delays only at the first and second hub airport in the net-

work respectively and another distribution models the average probability

of delays for all except the two hub airports.

IATA delay codes: 83 and 85 – 89

Occurrence probability: πis a random variable with following distribution

dependent on the airport:

•All airports: Normal distribution with σ= 0.03 and µ=−0.13

•Hub A: Log-normal distribution with σ= 0.16 and µ=−1.78

•Hub B: Log-logistic distribution with α= 7.46 and β= 0.12

•All airports except hubs A and B: Normal distribution with σ= 0.15

and µ=−0.04

Average duration: 10 minutes

Distribution of duration: Log-normal distribution with σ= 0.70,µ= 2.02

and γ= 0.64;Di≈15 = 0.06265

143

Glossary

Aircraft assignment problem The aircraft assignment problem determines main-

tenance schedules for aircraft as well as individual aircraft routes which

cover all flights. Depending on the focus, context and solution method

this problem is also called maintenance routing, aircraft routing or tail

assignment.

Aircraft routing see aircraft assignment problem.

Airport turnaround The process of unloading, preparing and loading the aircraft

between two flights at an airport.

Crew assignment problem Crew rostering is the assignment of anonymous crew

crew pairings to individual crew members, satisfying individual work-time

regulations.

Crew base The location nominated by the airline to the crew member from

where the crew member normally starts and ends a duty period or a series

of duty periods and where, under normal conditions, the airline is not

responsible for the accommodation of the crew member concerned.

Crew pairing A sequence of duty and rest periods of a crew, starting and ending

at the same crew base.

Crew pairing problem The crew pairing problem determines cost minimal iti-

neraries for crews, crew pairings, covering all flights and satisfying general

work-time regulations.

Crew rostering see crew assignment problem.

De-icing is the process of removing frozen contaminant, snow, ice, from an air-

craft.

145

Glossary

Deadheading describes the transfer of crew members as passengers on regular

flights. This can be necessary to return the crew to the crew base or to

transfer the crew to the next flight at another airport. Deadheading incurs

costs because the crew members need seats on the aircraft, which cannot

be offered to paying customers.

Disruption is a conflict of invalid airline schedules, e.g. missing aircraft, missing

crew or insufficient time for crew rest. Disruptions are consequences of pri-

mary or reactionary delays or of any other unforeseen events, e.g. damage

to aircraft, capacity decrease at airports or missing crews.

Duty A daily working shift of a crew which consists of a sequence of flights. The

maximal allowed duration of a duty is 10 hours, but can be extended up

to 14 hours depending on the duration of the subsequent rest period.

Fleet assignment problem The fleet assignment problem determines for each

flight an aircraft type considering the demand forecast as well as the avai-

lability of aircraft.

Flexibility Flexible schedules can be efficiently adapted to changing operating

environment.

Maintenance base The location nominated by the airline to perform long-term

maintenance checks at aircraft. A maintenance base needs certain technical

equipment and staff to perform checks. The capacity of the maintenance

facilities is restricted and therefore needs to be scheduled.

Maintenance routing see aircraft assignment problem.

Minimal sit time is the minimal time needed for a crew between two flights.

It depends on the minimal turn time. In the case the crew stays on the

aircraft both times are equal. When the crew changes aircraft normally the

minimal sit time is longer, due to additional time needed by the crew to

move at the airport and to perform additional checks on the new aircraft.

Minimal turn time is the minimal time needed to complete the airport turna-

round process for an aircraft. It depends on the aircraft type as well as

146

Glossary

airport facilities, i.e. the size of the aircraft, the number of entrance points

and the number of available boarding bridges.

On-time performance is the percentage of fights arriving or departing at the

gate on time. An arrival or departure is on time if it is within xminutes

of the originally scheduled time. xis usually 0, 5, 15 and 60 minutes.

Primary delay A primary delay is caused by any initial event. Unlike reactionary

delay it is not caused by any earlier delay.

Reactionary delay A reactionary delay is caused by an earlier delay, a conse-

quence of the unavailability of aircraft, crew or load due to disruptions

earlier in the day. This earlier disruption can itself be a consequence of

either a primary or a reactionary delay.

Recovery refers to the overall process of adapting the schedules to the new si-

tuation as recovery of schedules. The recovery process includes using ma-

thematical methods such as optimization and simulation, as well as manual

adjustments to the schedules especially in combination with communication

between staff.

Rescheduling is the creation of a new schedule for a resource on the day of

operation with the aim of adapting the schedule to a new situation by

performing as few changes to the schedule as possible.

Rest A night between two duties of a crew not in the crew base, where the crew

can have a rest. The required time is between 10 and 14 hours, depending

on the duration of the preceding duty period.

Schedule design problem The schedule design problem determines which connec-

tions between airports at which time are offered considering a forecast on

the demand of customers.

Secondary delay see reactionary delay.

Stability Stable airline schedules are likely to remain feasible and near-cost op-

timal in a changing operating environment.

147

Glossary

Tail assignment see aircraft assignment problem.

Taxi in Movement of the aircraft from runway to the gate or parking position

after landing.

Taxi out Movement of the aircraft from the gate or parking position to the

runway before take-off.

148

Acronyms

ATC air traffic control.

ATFM air traffic flow management.

CFMU Central Flow Management Unit.

EUROCONTROL European Organisation for the Safety of Air Navigation.

IATA International Air Transport Association.

IPM interior point method.

MIP mixed integer programming.

OCC operation control center.

RCSP resource-constrained shortest path problem.

RMP restricted master problem.

SCP set covering problem.

SPP set partitioning problem.

149

List of Figures

2.1. Tactical and Operational Problems in the Airline Industry .... 7

2.2. Structure of a Crew Pairing ..................... 12

2.3. Departure Delay Causes in Europe, 2008, EUROCONTROL [2009] 16

2.4. Airport Turnaround Process of an Aircraft ............. 17

2.5. Traffic Variation in Europe Since 2003, Source: EUROCONTROL

[2008] ................................. 19

2.6. Evolution of the Average ATFM Delay Per Flight, Source: EU-

ROCONTROL [2008] ........................ 19

2.7. Comparison of Total Traffic and Flights Delayed > 15 min due to

ATFM Restrictions in 2008, Source: EUROCONTROL [2009] . . 20

2.8. Interrelation of Disruptions ..................... 24

5.1. Branch-and-Price-and-Cut Framework ............... 51

5.2. Flight-based Time-Space Network for Pairing Generation . . . . 53

5.3. Comparison of Different Solution Strategies for Small Problems . 67

5.4. Comparison of Different Solution Strategies for Medium Problems 68

5.5. Cumulated Average Solution Times for Different Solution Strate-

gies for Medium Problems ...................... 69

5.6. Effect of the Improvement Technique Label Categorizing on the

Solution Quality for All Medium Problems ............. 70

5.7. Effect of the Improvement Technique SR3Inequalities on the So-

lution Quality for All Medium Problems .............. 72

5.8. Effect of the Improvement Technique History Fixing on the Solu-

tion Quality for All Medium Problems ............... 74

6.1. Graph of Penalty Factor with Values 1, 2, 3 and 4 for p..... 85

6.2. Solution Times of the Iterative Method for all Models ...... 87

151

List of Figures

6.3. Comparison of Solution Times for Different Storage Strategies . . 88

7.1. Framework for Evaluation of Strategies for Robust Scheduling . . 90

7.2. Example for Smoothing with the Central Moving Average Method

with a= number data points, Source: Spengler [2009] . . . . . . 92

7.3. Comparison of the Relative Decrease of Expected Reactionary De-

lays as well as the Relative Increase of Crew Costs with the Rela-

tive Decrease of Reactionary Delays (Configuration highA) . . . 100

7.4. Correlation Factor and Linear Regression Models for Penalty Fac-

tor for the Expected Number of Reactionary Delays With All Si-

mulation Configurations ....................... 101

7.5. Comparison of the Relative Decrease of Expected Crew Duty dis-

ruptions as well as the Relative Increase of Crew Costs with the

Decrease of Observed Crew Duty disruptions (Configuration highA)102

7.6. Correlation Factor and Linear Regression Models for the Stochas-

tic Robustness Measure Based on Expected Crew Duty disruptions

With All Simulation Configurations ................ 102

7.7. Comparison of the Robustness Indicators with the Other Robust-

ness Measures (Configuration highA) ................ 103

7.8. Comparison of the Relative Decrease of Restricted Aircraft Changes

as well as the Relative Increase of Crew Costs with the Relative

Decrease of Reactionary Delays ................... 104

7.9. Comparison of the Relative Decrease of Restricted Duties as well

as the Relative Increase of Crew Costs with the Relative Decrease

of Crew Duty Disruptions ...................... 105

7.10. Comparison of the Robustness Indicators with the Other Robust-

ness Measures ............................. 106

152

List of Tables

5.1. Crew Scheduling Rules ........................ 49

5.2. Relevant Resources .......................... 56

7.1. Distributions for Primary Delays .................. 93

7.2. Configurations for Probabilities of Primary Delays During Simu-

lation ................................. 95

8.1. Primary and Reactionary Delays After Simple Propagation . . . 113

8.2. Reactionary Delays and Schedule Changes After Rescheduling . . 114

153

List of Algorithms

3.1. Basic label setting algorithm for the RCSP ............. 28

3.2. Branch-and-Bound ........................... 29

3.3. Column Generation Algorithm .................... 32

5.1. Label Setting Algorithm for Pairing Generation .......... 55

5.2. Considering SR3Inequalities in Pairing Generation ........ 64

6.1. Iterative Method for the Stochastic Crew and Aircraft Scheduling 81

7.1. Monte Carlo Method for Simulation of Airline Schedules ..... 97

8.1. Iterative Method for Simultaneous Recovery ............ 112

155

Bibliography

Abdelghany, A., G. Ekollu, R. Narasimhan, and K. Abdelghany (2004). A proac-

tive crew recovery decision support tool for commercial airlines during irregular

operations. Annals of Operations Research 127(1), 309–331.

Abdelghany, K. F., A. F. Abdelghany, and G. Ekollu (2008, March). An in-

tegrated decision support tool for airlines schedule recovery during irregular

operations. European Journal of Operational Research 185(2), 825–848.

Ageeva, Y. (2000, August). Approaches to incorporating robustness into airline

scheduling. Master’s thesis, Massachusetts Institute of Technology.

AhmedBeygi, S., A. Cohn, and M. Lapp (2008). Decreasing airline delay

propagation by re-allocating schedule slack. Technical report, AGIFORS.

http://www.agifors.org/award/submissions2008/Ahmadbeygi_paper.pdf.

Ahuja, R., T. Magnanti, and J. Orlin (1993). Network Flows: Theory, Algo-

rithms, and Applications. Englewood Cliffs, NJ, USA: Prentice Hall.

Anbil, R., J. J. Forrest, and W. R. Pulleyblank (1998). Column generation

and the airline crew pairing problem. Documenta Mathematica, Journal der

Deutschen Mathematiker Vereinigung Extra Volume ICM(III), 677–686.

Andersson, T. and P. Värbrand (2004, April). The flight perturbation problem.

Transportation Planning and Technology 27(2), 91–117.

Barnhart, C., N. L. Boland, L. W. Clarke, E. L. Johnson, G. L. Nemhauser, and

R. G. Shenoi (1998). Flight string models for aircraft fleeting and routing.

Transportation Science 32, 208–220.

157

Bibliography

Barnhart, C., A. M. Cohn, E. L. Johnson, D. Klabjan, G. L. Nemhauser, and

P. H. Vance (2003). Handbook of Transportation Science, Chapter Airline Crew

Scheduling, pp. 517–560. Springer New York.

Barnhart, C., E. L. Johnson, G. L. Nemhauser, M. W. Savelsbergh, and P. H.

Vance (1998). Branch-and-price: Column generation for solving huge integer

programs. Operations Research 46, 316–329.

Bixby, R., J. Gregory, I. Lustig, R. Marsten, and D. Shanno (1992). Very large-

scale linear programming: A case study in combining interior point and simplex

methods. Operations Research 40(5), 885–897.

Boeing (2005). 737 - airplane characteristics for airport planning.

http://www.boeing.com/commercial/airports/plan_manuals.html, last access

on 19th October 2009.

Burke, E., P. De Causmaecker, G. De Maere, J. Mulder, M. Paelinck, and G. Van-

den Berghe (2010). A multi-objective approach for robust airline scheduling.

Computers & Operations Research 37(5), –.

Cao, J.-M. and A. Kanafani (1997a, March). Real-time decision support for

integration of airline flight cancellations and delays part i: mathematical for-

mulation. Transportation Planning and Technology 20(3), 183–199.

Cao, J.-M. and A. Kanafani (1997b, March). Real-time decision support for

integration of airline flight cancellations and delays part ii: algorithm and

computational experiments. Transportation Planning and Technology 20(3),

201–217.

Clarke, L., E. Johnson, G. Nemhauser, and Z. Zhu (2003). The aircraft rotation

problem. Anals of Operations Research 51, 387–296.

Clausen, J., A. Larsen, J. Larsen, and N. J. Rezanova (2009, May). Disruption

management in the airline industry – concepts, models and methods. Compu-

ters & Operations Research 37(5), 809–821.

Cohn, A. and C. Barnhart (2003). Improving crew scheduling by incorporating

key maintencance routing decisions. Operations Research 51(3), 387–396.

158

Bibliography

Cordeau, J.-F., G. Stojkovic, F. Soumis, and J. Desrosiers (2001). Benders de-

composition for simultaneous aircraft routing and crew scheduling. Transpor-

tation Science 35(4), 375–388.

Desaulniers, G., J. Desrosiers, Y. Dumas, S. Marc, B. Rioux, M. M. Solomon,

and F. Soumis (1997). Crew pairing at Air France. European Journal of

Operational Research 97(2), 245 – 259.

Desaulniers, G., J. Desrosiers, Y. Dumas, M. Solomon, and F. Soumis (1997).

Daily aircraft routing and scheduling. Management Science 43(6), 841–855.

Desaulniers, G., J. Desrosiers, A. Lasry, and M. M. Solomon (1999). Crew pai-

ring for a regional carrier. Lecture notes in economics and mathematical sys-

tems 471, 19–41.

Desaulniers, G., J. Desrosiers, and M. Solomon (2001). Essays and Surveys in

Metaheuristics, Chapter Accelerating Strategies in Column Generation Me-

thods for Vehicle Routing and Crew Scheduling Problems, pp. 309–324. Bos-

ton: Kluwer.

Desrosiers, J. and M. Lübbecke (2005). Column Generation, Chapter A Primer

in Column Generation, pp. 1–32. New York: Springer.

Ehrgott, M. and D. M. Ryan (2002). Constructing robust crew schedules with

bicriteria optimization. Journal of Multi-Criteria Decision Analysis 11(3),

139–150.

Etschmaier, M. and D. Mathaisel (1985). Airline scheduling: An overview. Trans-

portation Science 19(2), 127–138.

EUROCONTROL (2007). Trends in air traffic volume 2 - a matter of time: Air

traffic delay in europe. http://www.eurocontrol.int/statfor/, last access on

19th October 2009.

EUROCONTROL (2008). Annual report 2008. http://www.eurocontrol.int, last

access on 19th October 2009.

EUROCONTROL (2009). Digest – annual 2008: Delays to air transport in

europe. http://www.eurocontrol.int/coda/, last access on 19th October 2009.

159

Bibliography

European Parliament and the Council (2006). Regulation (ec) no 1899/2006.

Fahle, T., U. Junker, S. E. Karisch, N. Kohl, M. Sellmann, and B. Vaaben

(2002). Constraint programming based column generation for crew assignment.

Journal of Heuristics 8(1), 59–81.

Fuhr, B. (2007, April). Robust flight scheduling - an analytic approach to per-

formance evaluation and optimization. Technical report, Clausthal University

of Technology, Lufthansa Airlines.

Galia, R. and C. Hjorring (2004). Modelling of complex costs and rules in a crew

pairing column generator. In D. Ahr, R. Fahrion, M. Oswald, and G. Reinelt

(Eds.), Operations Research Proceedings 2003 – Selected Papers of the Inter-

national Conference on Operations Research (OR 2003), Berlin, pp. 133–140.

Springer.

Gopalakrishnan, B. and E. L. Johnson (2005). Airline crew scheduling: State-

of-the-art. Annals of Operations Research 140, 305–337.

Gopalan, R. and K. Talluri (1998a). The aircraft maintenance routing problem.

Operation Research 46, 260–271.

Gopalan, R. and K. Talluri (1998b). Mathematical models in airline schedule

planning: A survey. Annals of Operations Research 76, 155–185.

Grönkvist, M. (2005). The Tail Assignment Problem. Ph. D. thesis, Chalmers

University of Technology and Göteborg University.

Guo, Y. (2005, January). Decision support systems for airline crew recovery. Ph.

D. thesis, University of Paderborn.

Hassin, R. (1992). Approximation schemes for the restricted shortest path pro-

blem. Mathematics of Operations Research 17(1), 36–42.

IATA (2008). Airport Handling Manual. IATA.

IBM ILOG (2009). http://www.ilog.com/. last access on 19th October 2009.

160

Bibliography

Ioachim, I., J. Desrosiers, F. Soumis, and N. Bélanger (1999). Fleet assignment

and routing with schedule synchronization constraints. European Journal of

Operational Research 119(1), 75–90.

Irnich, S. and G. Desaulniers (2005). Column Generation, Chapter Shortest Path

Problems with Resource Constraints, pp. 33–65. Springer.

Jacobs, P. H. M., A. Verbraeck, and J. B. P. Mulder (2005). Flight scheduling at

klm. In WSC ’05: Proceedings of the 37th conference on Winter simulation,

pp. 299–306. Winter Simulation Conference.

Jans, R. and Z. Degraeve (2004). An industrial extension of the discrete lot-sizing

and scheduling problem. IIE Transactions 36(1), 47–58.

Jarrah, A. I. Z., G. Yu, N. Krishnamurthy, and A. Rakshit (1993). A Decision

Support Framework for Airline Flight Cancellations and Delays. Transporta-

tion Science 27(3), 266–280.

Jepsen, M., B. Petersen, S. Spoorendonk, and D. Pisinger (2008). Subset-row

inequalities applied to the vehicle-routing problem with time windows. Ope-

rations Research 56(2), 497–511.

Johnson, V., L. Lettovsky, G. Nemhauser, R. Pandit, and S. Querido (1994).

Final report to northwest airlines on the crew recovery problem. Technical

report, The Logistic Institute, Georgia Institute of Technology, Atlanta, USA.

Klabjan, D. (2005). Column Generation, Chapter Large-Scale Models in the

Airline Industry, pp. 163––196. Springer.

Klabjan, D., E. L. Johnson, G. L. Nemhauser, E. Gelman, and S. Ramaswamy

(2001a). Airline crew scheduling with regularity. Transportation Science 35(4),

359–374.

Klabjan, D., E. L. Johnson, G. L. Nemhauser, E. Gelman, and S. Ramaswamy

(2001b). Solving large airline crew scheduling problems: Random pairing gene-

ration and strong branching. Computational Optimization and Applications 20,

73–91.

161

Bibliography

Klabjan, D., E. L. Johnson, G. L. Nemhauser, E. Gelman, and S. Ramas-

wamy (2002). Airline crew scheduling with time windows and plane-count

constraints. Transportation Science 36(3), 337–448.

Kohl, N. and S. Karisch (2004). Airline crew rostering: Problem types, modeling

and optimization. Annals of Operations Research 127, 223–257.

Lan, S., J.-P. Clarke, and C. Barnhart (2006, February). Planning for robust

airline operations: Optimizing aircraft routings and flight departure times to

minimize passenger disruptions. Transportation Science 40(1), 15–28.

Leal de Matos, P. and R. Ormerod (2000). The application of operational re-

search to European air traffic flow management – understanding the context.

European Journal of Operational Research 123(1), 125–144.

Lettovsky, L. (1997). Airline operations recovery: an optimization approach. Ph.

D. thesis, Georgia Institute of Technology, Atlanta, USA.

Lettovský, L., E. L. Johnson, and G. L. Nemhauser (2000). Airline crew recovery.

Transportation Science 34(4), 337–348.

Lübbecke, M. E. and J. Desrosiers (2005). Selected topics in column generation.

Operations Research 53(6), 1007–1023.

MathWave Technologies (2009). http://www.mathwave.com. last access on 19th

October 2009.

Medard, C. P. and N. Sawhney (2007, December). Airline crew scheduling from

planning to operations. European Journal of Operational Research 183(3),

1013–1027.

Mercier, A., J.-F. Cordeau, and F. Soumis (2005). A computational study of

benders decomposition for the integrated aircraft routing and crew scheduling

problem. Computers & Operations Research 32(6), 1451–1476.

Mercier, A. and F. Soumis (2007). An integrated aircraft routing, crew scheduling

and flight retiming model. Computers & Operations Research 34(8), 2251–

2265.

162

Bibliography

MOPS Optimierungssysteme GmbH & Co. KG (2009). http://www.mops-

optimizer.com. last access on 19th October 2009.

Nissen, R. and K. Haase (2006). Duty-period-based network model for crew

rescheduling in european airlines. Journal of Scheduling 9, 255–278.

Rakshit, A., N. Krishnamurthy, and G. Yu (1996, Mar.–Apr.). System operations

advisor: A real-time decision support system for managing airline operations

at united airlines. Interfaces 26(2), 50–58.

Rodgers, J. L. and W. A. Nicewander (1988). Thirteen ways to look at the

correlation coefficient. The American Statistician 42(1), 59–66.

Rosenberger, J. M., E. L. Johnson, and G. L. Nemhauser (2003, November).

Rerouting aircraft for airline recovery. Transportation Science 37 (4), 408–421.

Rosenberger, J. M., A. J. Schaefer, D. Goldsman, E. L. Johnson, A. J. Kley-

wegt, and G. L. Nemhauser (2002, November). A stochastic model of airline

operations. Transportation Science 36(4), 357–377.

Ryan, D. M. and B. A. Foster (1981). An integer programming approach to

scheduling. Computer Scheduling of Public Transport 1, 269–280.

Sarac, A., R. Batta, and C. Rump (2006). A branch-and-price approach for

operational aircraft maintenance routing. European Journal of Operational

Research 175, 1850–1869.

Schaefer, A. J., E. L. Johnson, A. J. Kleywegt, and G. L. Nemhauser (2005).

Airline crew scheduling under uncertainty. Transportation Science 39(3), 340–

348.

Scholl, A. (2001). Robuste Planung und Optimierung: Grundlagen - Konzepte

und Methoden - Experimentelle Untersuchungen, Chapter Robuste Planung,

pp. 89 –172. Physica-Verlag Heidelberg.

Shebalov, S. and D. Klabjan (2006, August). Robust airline crew pairing: Move-

up crews. Transportation Science 40(3), 300–312.

163

Bibliography

Spengler, F. (2009). Statistische Abbildung von Verspätungen im Luftverkehr.

Decision Support & Operations Research Lab, Universität Paderborn.

Sriram, C. and A. Haghani (2003). An optimization model for aircraft mainte-

nance scheduling and re-assignment. Transportation Research Part A: Policy

and Practice 37(1), 29–48.

Steinzen, I. (2007). Topics in Integrated Vehicle and Crew Scheduling in Public

Transport. Ph. D. thesis, Universität Paderborn, Paderborn.

Stojković, M. and F. Soumis (2001). An optimization model for the simultaneous

operational flight and pilot scheduling problem. Management Science 47 (9),

1290–1305.

Stojković, M. and F. Soumis (2005). The operational flight and multi-crew sche-

duling problem. Yugoslav Journal of Operations Research 15, 25–48.

Stojković, M., F. Soumis, and J. Desrosiers (1998). The operational airline crew

scheduling problem. Transportation Science 32(3), 232–245.

Teodorovic, D. and E. Krcmar-Nozic (1989). Multicriteria model to determine

flight frequencies on an airline network under competitive conditions. Trans-

portation Science 23(1), 14–25.

Toutenberg, H. (2005). Induktive Statistik (3 ed.). Springer Berlin Heidelberg.

Vance, P. H., A. Atamtürk, C. Barnhart, E. Gelman, E. L. Johnson, A. Krishna,

D. Mahidhara, G. L. Nemhauser, and R. Rebello (1997). A heuristic branch-

and-price approach for the airline crew pairing problem. Technical Report

LEC-97-06, Georgia Institute of Technology.

Vance, P. H., C. Barnhart, E. L. Johnson, and G. L. Nemhauser (1997, March–

April). Airline crew scheduling: A new formulation and decomoposition algo-

rithm. Operation Research 45(2), 188–200.

Weide, O. (2009). Robust and Integrated Airline Scheduling. Ph. D. thesis, The

University of Auckland, Auckland.

164

Bibliography

Weide, O., D. Ryan, and M. Ehrgott (2009, May). An iterative approach to

robust and integrated aircraft routing and crew scheduling. Computers &

Operations Research 37(5), 833–844.

Wolsey, L. A. (1998). Integer Programming, Chapter Lagrangian Duality, pp.

167 –181. John Wiley & Sons, Inc.

Wu, C.-L. (2006, September). Improving airline network robustness and opera-

tional reliability by sequential optimisation algorithms. Networks and Spatial

Economics 6(3), 235–251.

Yan, S. and D.-H. Yang (1996, December). A decision support framework for

handling schedule perturbation. Transportation Research Part B: Methodolo-

gical 30(6), 405–419.

Yen, J. W. and J. R. Birge (2006). A stochastic programming approach to the

airline crew scheduling problem. Transportation Science 40(1), 3–14.

Yu, G. and X. Qi (2004). Disruption management: framework, models and ap-

plications. World Scientific Publishing Company.

Zhao, X., J. Zhu, and M. Guo (2007, Dec.). Application of grey programming in

irregular flights scheduling. In Industrial Engineering and Engineering Mana-

gement, 2007 IEEE International Conference on, pp. 164–168.

165