4
Dynamic Overbooking
www.pros.com
In this example, the physical capacity is 25, and the
maximum allowed overbooking limit (i.e., overbooking
pad in the literature) is 20. Note the purple line
corresponding to zero seat index together with the
green line corresponding to the overbooking pad
determine the overbooking range across the entire
booking horizon, which is equally divided into 80 time
slots. More specifically, we can make the following
observations from Figure 1:
• Similar to the policy obtained from the traditional DP
model, the acceptance/rejection decision can be
visually made from the regions defined by the lowest
open index trajectories of all the classes. For
example, only bookings for the top two classes are
accepted in the region defined by the yellow and the
orange boundaries.
• Throughout the entire booking horizon, the top class
can overbook, at most, nine seats (indicated by the
blue line).
• When the physical capacity runs out, booking request
for Class 2 would never be accepted until it is close to
departure (approximately 20 time slots away); in the
same situation, Class 3 cannot be overbooked until
approximately five time slots away from departure.
Note that this example considers no-shows only, and the
standard DP structural properties still hold. If
cancellations are included, some of the structural
properties may no longer hold and the lowest open
class index lines (e.g., orange line for class 2) may not be
monotone.
Dynamic
Overbooking
FIGURE 1 .
As an illustration, Figure 1 illustrates how the
overbooking integrated DP works on a single leg flight
with three classes.
-20
-25
70 80 60 50 40 30 20 10 0
-15
-10
-5
0
5
10
15
20
25
Class 1
Class 2
Zero seats left
Overbooking pad
class 1 and
class 2 are both
open
no class 1 is open
no class is open
Lowest Open Class
Time to Departure
Seat
Index
