Optimal Capacity Control
Single Resource Capacity Control
In this section we outline a capacity control policy that is routinely used in various industries (airlines, car rentals, hospitality) to make reservations towards a perishable capacity-constrained resource.
Your job is to determine the knobs that implement the policy in a reservation system where customers are arriving to making a booking. We treat the simplest possible problem of a single resource. The intuition behind the heavy math below is simple1.
Capacity should be allocated to a request if and only if its revenue is greater than the value of the capacity required to satisfy the request. Second the value of capacity should be measured by its expected displacement cost or opportunity cost which is the expected loss in future revenue from using the capacity now rather than protecting it for future use.
The opportunity cost is captured using a value function
Two class model
Let us assume that we are interested in allocating a resource of capacity
and are independent random variables i.e. .
The type
Our aim is to find the a-priori protection level
The maximum number of resource units that can be allocated to type
The units that can be occupied by type
Therefore the maximum number of resource units that can be allocated to type
The units that will be occupied by type
The expected revenue from the occupied resources will be
where the expectation is taken over the random demands of the two types. If we maximize revenue over the protection level
Intuitively, the ratio of the prices
Let us assume now that we set a fixed price ratio
Dynamic Programming Solution
To use a dynamic programming problem formulation, we need to define the variables at the beginning of the two periods involved.
The first period is defined as the point just before the type
Similarly, the second variable is the value function
where we have expanded
{{
The dynamic program formulation would involve relating
The revenue difference from one unit of protection level is given by,
We can prove the last equality as follows
We can study two cases:
Case | Description |
---|---|
$ W(y,C) = W(y,C) - W(y-1,C)$ | |
$ = E {p_d D_d + V_f(C-D_d) } - E {p_d D_d + V_f(C-D_d)} $ | |
$ = E {0 p(D_d C-y) } =0 $ | |
$ W(y,C) = W(y,C) - W(y-1,C)$ | |
Then in all cases, the difference,
If we replace the marginal of the value function
The term is
Note that the marginal value
Calculating the Optimal Protection Limit and Maximum Revenue
The optimal
The optimal booking limit will then be
The maximum possible revenue starting with capacity
Calculating
To start the iteration we need
The first expectation can be written using partial expectations as,
The second expectation can be written as,
Then, starting from
The Multiple Class Model
The value function for the multi-class problem is given by,
The implementation in Matlab as shown in the next listing.
{{function Resource = value_function(Resource,stage,inpstruct)
% vector of all potential states (states represent the
% remaining capacity)
x=1:inpstruct.Num_States;
% the pdf of the demand for this stage - P(D_j == x)
demand_pdf = poisspdf(x,inpstruct.mean_D(stage));
% the complementary cdf of the demand for this stage - P(D_j >= x)
demand_ccdf = 1-poisscdf(x,inpstruct.mean_D(stage));
if stage==1
% The optimal protection level for this initial stage
y_star_prev = 0;
else
% The optimal protection level for this and subsequent stages
y_star_prev = Resource{stage-1}.Protection_Level;
end
T=zeros(inpstruct.C,inpstruct.C);
% Calculate the value function V (note that we are reusing x defining
%it as the state index)
for x=1:inpstruct.Num_States
Resource{stage}.T(x,:)=0;
for k=1:x-y_star_prev
T(x,k)= (inpstruct.price(stage) * k + ...
Resource{stage-1}.V(max(1,x-k)))* demand_pdf(k);
end
Resource{stage}.V(x) = sum(T(x,:)) + ...
inpstruct.price(stage)* max(0,x-y_star_prev) + ...
(Resource{stage-1}.V(max(1,min(x,y_star_prev)))) *...
demand_ccdf(max(1,x-y_star_prev));
end
% Calculate the marginal value of a single resource unit (DeltaV)
deltaV = diff(cat(2,0,Resource{stage}.V));
Resource{stage}.deltaV= deltaV;
% find the point of where the marginal value is larger than the price of
% the next stage
indeces = find(deltaV > inpstruct.price(stage+1));
Resource{stage}.Protection_Level = max(indeces);
A number of calls equal to the number of stages are made. In each call, the corresponding results are stored for usage at the next stage.
For a problem with available initial capacity
—– | —– | ——————- | ————————- ||
1 | 1000 | Poisson(40) | 41 |
2 | 450 | Poisson(15) | 100 |
The marginal value as a function of the remaining resources.
The marginal value as a function of the remaining resources
The optimal protection limits are shown below.
A further example shows the straightforward application of the same DP solution for more classes. The table below outlines the results for an available initial capacity
—– | —– | ——————- | ————————- ||
1 | 100 | Poisson(10) | 6 |
2 | 90 | Poisson(15) | 20 |
3 | 80 | Poisson(25) | 44 |
4 | 70 | Poisson(15) | 50 |
The marginal value as a function of the remaining resources for the three stages of the problem
Its noteworthy to highlight the decreasing marginal value of capacity as the remaining capacity increases. This is intuitive as the more capacity we have remaining the less a unit of this capacity should be worth. Also, it is interesting to highlight the increasing value of marginal capacity with increasing stage. This is also intuitive as the earlier we are in stage i.e. the more time we have until we reach the final stage 1, the more a unit of capacity is worth if we allocate it at that stage.
The optimal protection limits are shown below.
References
[1] K. Talluri and G Van Ryzin, ‘The Theory and Practice of Revenue Management’, Springer, 2004.
Footnotes
It is probably the most essential first step as computer scientists to spend time understanding a domain / problem space and acquire such intuition as to how the system works.↩︎