Airline Reservation Systems

Gerard Kindervater
KLM – AMS/RX

2

Utrecht 2010

Objective of the presentation

• To illustrate

- what happens when passengers make a reservation

- how airlines decide what fare to charge to passengers

3

Utrecht 2010

Basic Disciplines

• Economics

- supply / demand / fares

• Econometrics

- models / optimization techniques

• Computer Science

- process management 

4

Utrecht 2010

Travel Example (1)

• Route

- Amsterdam 

→

Houston 

→

Amsterdam

• Availability request

- airline office / website

- biased

- travel agent / website

- neutral

5

Utrecht 2010

Travel Example (2)

• Result

- many alternatives

- journey & fare

- different journey (route or date) 

different fare

- airline / route
- flights (different expected load factor)

- same journey 

different fares

- fare conditions

- cancellation / change / service level / ...

- origin of availability request (point of sale)

6

Utrecht 2010

System Components

• Reservation system (RS)

- controls bookings based on flight statuses
- global systems : Amadeus, Galileo, Worldspan, …
- airline systems : Arco, Alpha3, Corda, …

• Revenue management system (RMS)

- computes flight settings
- sends the settings to the reservation system
- systems : PROS, Sabre, AirFrance/KLM, …

7

Utrecht 2010

• Airline reservation system (ARS)

- airline owned
- Arco, Alpha3, Corda, …

• Central reservation system (CRS)

- airline independent
- Amadeus, Galileo, Worldspan, …

Reservation Systems (RS)

8

Utrecht 2010

Airline Reservation System (ARS)

• Responsible for the airline’s own data

- flight schedule / fares / passenger data / …

• Decides whether or not to accept a passenger and 

determines the fare the passenger will have to pay

• Communication with

- other airlines (ARS’s)
- travel agents / passengers
- central reservation systems (CRS’s)
- ...

9

Utrecht 2010

Central Reservation System (CRS)

• Makes reservations for passengers in ARS’s

• Responsible for its bookings

-

reservation / ticketing / consistency with data in ARS

• Communication with

- airlines (ARS’s)
- travel agents / passengers
- …

10

Utrecht 2010

Overview Picture

ARS

ARS

ARS

CRS

CRS

11

Utrecht 2010

Availability Request

• Passenger (travel agent / website) connects to ARS / 

CRS

• ARS / CRS knows where the passenger is located

• Fare offered depends on location (point of sale) of 

passenger and path from passenger to ARS

-

passenger (Berlin) 

United 

United (flight IAH-FRA)

-

passenger (Berlin) 

Lufthansa 

United (flight IAH-FRA)

-

passenger (Oslo) 

United 

United (flight IAH-FRA)

→

United may (most likely will) offer different fares

• Travel websites (Priceline / CheapTickets) try several 

paths (by faking a change of location!)

12

Utrecht 2010

Revenue Management Systems (RMS)

• Reservation systems

- accept passengers and determine the fare to pay

• Revenue management system

- computes settings to be used by reservation systems 

when accepting passengers

- PROS, Sabre, AirFrance/KLM, …

13

Utrecht 2010

Airline Passenger Revenue Management

• Process of maximizing seat revenue through :

- pricing

- market segmentation
- “different products at different prices”

- inventory control

- limit the number of seats available to

specific market segments

- anticipate on future cancellations and no-shows

14

Utrecht 2010

Pricing (1)

• Market segmentation

- single fare class

untapped revenue

expected seats sold

revenue

unaccommodated

demand

dilution

fare

demand curve

15

Utrecht 2010

Pricing (2)

• Market segmentation

- multiple fare classes with different restrictions

expected seats sold

fare

demand curve

revenue

16

Utrecht 2010

Inventory Control

• Maximize total revenue

- compute the “optimal” passenger mix

- number of passengers / fare

- allow (limited) overbooking

- number of denied boardings (close to) zero
- yield of accepting extra passengers higher than denied 

boarding costs

17

Utrecht 2010

Example

• Amsterdam (AMS) – Houston (IAH/HOU)

• Departure date : 13 December 2009

• Booking date : 8 December 2009

18

Utrecht 2010

(RS) Availability AMS - IAH / 13 DEC

13DEC SUN 0001-0300* AMS HOU

01 AMS IAH 1050 1420   KL 661 J4C3I2X9S9B9M9K9H9

74E   0 1030               L9Q9T9V9

02 AMS IAH 1405 1820   KL 663 J9C9I9

737   0 1115

19

Utrecht 2010

(RS) Flight Status KL 661 / 13 DEC

FLIGHT:  KL661  13DEC09 SUN 10:50

LAST BID/BKT UPD:08DEC/1614Z AMS-IAH

BDG  SA  SS TSFS  AU  BID

C AMS   4  43   47  42 1745

M AMS  40 218  258 233  180

CAB  BKT  BA  PR   BND    CAB  BKT  BA  PR   BND

C    1   4   1  1384      M    1  40   0  1946

2   3   1   883           2  40   0  1070

3   2   1   164           3  40   1   834

4   1   0     0           4  39   3   702

5  36   3   572

…

…

…

…

20

Utrecht 2010

(RMS) Flight Status AMS - IAH / 13 DEC

21

Utrecht 2010

(RMS) Forecast Flight KL 661 / 13 DEC

22

Utrecht 2010

(RMS) Fares AMS - IAH / 13 DEC

23

Utrecht 2010

Expected Marginal Seat Revenue (EMSR)

• Heuristic (Belobaba 1989)

- flight based, several variants
- simple, fast, reliable
- works well with any reasonable stochastic demand forecast

• Idea : reserve seats for higher valued demand

• Steering mechanism

- bucket : set of fares 
- bucket protection : number of seats reserved for passengers 

paying at least a fare associated with that bucket

24

Utrecht 2010

Towards Network-Optimization (1)

• Problem : How to deal with connecting passengers?

• Example:

- 1 open seat on a flight from Geneva to Amsterdam
- 2 passengers :

- 1 passenger flying Geneva - Amsterdam

willing to pay a high (business class) fare

- 1 passenger flying Geneva - Amsterdam - Tokyo

willing to pay a low (economy class) fare only

- which passenger should get the seat on the flight

from Geneva to Amsterdam?

25

Utrecht 2010

Towards Network-Optimization (2)

• Flight oriented algorithms (like the one of Belobaba)

are suboptimal for the global network

• Network carriers have >70% connecting traffic

- Lufthansa, British Airways, Delta Airlines, KLM, …

• Huge data volumes

26

Utrecht 2010

(RMS) O&D Forecast KL 661 / 13 DEC 

27

Utrecht 2010

Network Inventory Control

• Maximize total revenue

- compute the “optimal” passenger mix

- number of passengers / route / fare

- allow (limited) overbooking

- number of denied boardings (close to) zero
- yield of accepting extra passengers higher than denied 

boarding costs

28

Utrecht 2010

Input (1)

• Schedule and capacity

- flight departure and arrival times

- cabin capacities

- sales restrictions

29

Utrecht 2010

Input (2)

• Demand and cancellation forecast

- based on observed bookings in the past

- low level :

- route (origin / destination / flight list)
- point of sale
- passenger type
- day of week / season
- fare class

- overrules for specific departure dates

30

Utrecht 2010

Models

• Notations

- OD : dated route (origin, destination, flight list) /

fare class / point of sale / passenger type

- for each OD

- X

OD

: number of passengers to accept (booking limit)

- D

OD 

: probabilistic demand

- F

OD

: fare

- for each flight j

- C

j

: remaining capacity (= capacity - actual seats sold)

(single cabin flights only)

31

Utrecht 2010

Stochastic Model

• Maximize

E( 

∑

∑

∑

∑

OD

F

OD

• min { X

OD 

, 

D

OD 

} 

)

• Subject to

∑

∑

∑

∑

OD 

⊇

⊇

⊇

⊇

flight j 

X

OD  

≤≤≤≤

C

j

(for all flights j)

X

OD  

≥≥≥≥

0 and integer

(for all OD’s)

32

Utrecht 2010

Deterministic Model (1)

• Approximation of stochastic model

• Maximize

∑

∑

∑

∑

OD

F

OD

• X

OD

• Subject to

∑

∑

∑

∑

OD 

⊇

⊇

⊇

⊇

flight j 

X

OD  

≤≤≤≤

C

j

(for all flights j)

0

≤≤≤≤

X

OD  

≤≤≤≤

ED

OD 

(for all OD’s)

33

Utrecht 2010

Deterministic Model (2)

• Advantages

- simple (linear programming)
- well solvable (large instances)
- easily extendable to multi-cabin flights

• Disadvantages

- fractional solutions
- deterministic (average demand)

→

how to handle unexpected booking behavior?

34

Utrecht 2010

Dual Formulation (1)

• Decision variables

- for each OD :

W

OD

(

≥≥≥≥

0)

- for each dated flight j : 

B

j

(

≥≥≥≥

0)

• Minimize

∑

∑

∑

∑

OD

D

OD

• W

OD 

+ 

∑

∑

∑

∑

j

C

j

• B

j

• Subject to

W

OD  

≥≥≥≥

F

OD

-

∑

∑

∑

∑

OD 

⊇

⊇

⊇

⊇

flight j

B

j

(for all OD’s)

35

Utrecht 2010

• W

OD

& B

j

- marginal values w.r.t. demand and capacity

• Terminology

- B

j

: bid price of flight j

- F

OD

–

∑

∑

∑

∑

OD 

⊇

⊇

⊇

⊇

vlucht j

B

j  

: OD (customer) contribution

→

notation :  CuCo

OD

Dual Formulation (2)

36

Utrecht 2010

• Acceptance strategy for passengers

willing to fly a certain OD

- accept the passengers if

CuCo

OD

=  F

OD

-

∑

∑

∑

∑

OD 

⊇

⊇

⊇

⊇

flight j

B

j  

>  0

- refuse the passengers if

CuCo

OD

=  F

OD

-

∑

∑

∑

∑

OD 

⊇

⊇

⊇

⊇

flight j

B

j  

<  0

- conditionally accept the passengers if

CuCo

OD

=  F

OD

-

∑

∑

∑

∑

OD 

⊇

⊇

⊇

⊇

flight j

B

j  

=  0

Unexpected Booking Behavior

37

Utrecht 2010

Optimization Frequency

• Best strategy

- after each accepted booking
- if expected bookings fail to happen

→

practically infeasible

• Second best strategy

- at regular time intervals : daily, weekly, …
- on demand : heavy booking activity, schedule changes, …

→

how to avoid loss of revenue?

38

Utrecht 2010

Expected Marginal Seat Revenue (contd.)

• Use Belobaba’s algorithm as secondary tool

• Create flight forecast based on customer contribution

• Steering mechanism

- bucket : customer contribution values 
- bucket protection : number of seats reserved for passengers 

paying at least a fare associated with that bucket

• Availability request

- return minimum bucket availability of all flights in the itinerary

39

Utrecht 2010

Cancellations & No-shows (1)

• Overbooking of flights in order to prevent empty seats

•

Risk based overbooking

- limit expected number of denied boardings

→

increase the number of available seats

• Cost based overbooking

- limit expected denied boarding costs

→

extra terms in the objective function

40

Utrecht 2010

Cancellations & No-shows (2)

• Overbooking on bookings on hand

- all passenger data are known
- cancellation forecast model may be trusted

• Overbooking on demand to come

- optimization model computes demand to accept
- actual accepted demand may differ
- to be applied with care

41

Utrecht 2010

Issue : Buy-Down (1)

• Models assume market segmentation

- passengers willing to pay a specific fare

will actually buy a ticket at that fare

• Assumption is valid in case of (strict) fare restrictions

- minimum / maximum stay
- no rerouting
- no refunds
- ...

42

Utrecht 2010

Issue : Buy-Down (2)

• Fare restrictions disappear gradually …

→

Passengers will buy cheapest ticket in the market

→

direct loss of revenue

→

lower demand forecast for higher fares

→

indirect loss of revenue in the future (spiral down)

• New sell-up models incorporate customer behavior

- mixed integer / nonlinear / fare adjustments

43

Utrecht 2010

Issue : Buy-Down (3)

→

Airlines will not always offer low fare tickets
in order to fill up (empty) flights