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