5
Dynamic Overbooking
www.pros.com
The traditional DP model has been in the PROS
optimization engine for close to two decades. When
incorporating cancellations, no-shows and overbooking
into the traditional DP model, the following convenient
extensions are necessary:
1. The terminal reward (boundary condition for the dp
recursion to start) is no longer trivially zero; instead, it
now takes denied boarding cost and no-show rate into
consideration. We can still make the (currently) typical
assumption that each passenger shows up independently
with the same probability, thus binomial distribution can
be used to calculate the expected overbooking cost as
the terminal reward.
2. The fare collected from each booking needs to be
properly discounted due to cancellation refund and
no-show refund. More specifically, instead of applying
the refund at the moment a cancellation or a no-show
occurs, one can subtract the expected revenue loss (due
to either type of refund) from the fare at the instant of
booking, which is known as equivalent charging in the
literature [1, 2, 5]. While the cancellation probabilities and
no-show probabilities are assumed to be fare-class
independent in order for the DP model to remain one-
dimensional (and hence efficiently solvable), the
cancellation refund and no-show refund are allowed to
be class dependent.
3. An additional cancellation term will be included in DP
recursion, which is because when a booking gets
canceled, the remaining inventory will increase by one,
while in the traditional DP, the remaining inventory can
only decrease (when a booking requested is accepted) or
remain the same (when there is no booking request or
the request is rejected). Thus, there are three possible
state transitions instead of two, as in the traditional DP.
Methodology
