6
$\begingroup$

I am considering a bid prices (shadow price of the capacity constraint) problem (from Chen, L. and Homem-de Mello, T. (2009)., page 14) where the acceptable classes for booking requests for itineraries need to be determined to maximize expected revenue over a time interval. Let $\{N_k (t)\}$ denote the point process generated by the arrivals of class $k$ customers. The demand for the booking horizon $\tau$ ($\xi_k = N_k(\tau)$) has the following distribution for classes 1 and 2 (the distribution of $\xi_k$ is approximated by a truncated Poisson): $$ \xi_1 = \begin{cases} 5 &\text{ with prob. } 0.5\\ 1 &\text{ with prob. } 0.5\\ \end{cases}, \ \xi_2 = \begin{cases} 2 &\text{ with prob. } 0.5\\ 4 &\text{ with prob. } 0.5\\ \end{cases} $$ The capacity for seats is 4 and the fares are respectively 100 and 60. Consider the following initial problem (DLP): \begin{align} \max_{x} &\quad 100 x_1 + 60 x_2\\ \text{s.t. }&\quad x_1 + x_2 \leq 4\\ &\quad 0 \leq x_i \leq \mathbb{E}[\xi_i] \end{align} For an arbitrary time $t \leq \tau$, let $\xi_k^t$ denote the random number of arrivals of class $k$ up to $t$ and let $\hat{\eta}^t$ denote the number of sold seats up to $t$. The re-solving model is thus (re-solving DLP): \begin{align} \max_{x} &\quad 100 x_1 + 60 x_2\\ \text{s.t. }&\quad x_1 + x_2 \leq 4-\hat{\eta}^t\\ &\quad 0 \leq x_i \leq \mathbb{E}[\xi_i - \xi_i^t] \end{align} Moreover, suppose that we can divide the time horizon into two periods such that in the first period there are two class-2 arrivals only. We have

  • $\mathbb{E}[\xi_1] = 3 \leq 4$
  • $\mathbb{P}(\xi_1^t = 0)=1$
  • So $\mathbb{E}[\xi_1 - \xi_1^t] = 3$

The initial policy determined by the bid prices is to accept all the requests (DLP). Then, after the first period, two seats are occupied. When re-solving to obtain new bid prices after the class-2 arrivals, the policy becomes only accepting class-1 customers (I checked that the solution is $(2,0)^T$ and expected revenue 150 because with probability 0.5 there is one ticket sold in class 1 for the re-solving DLP).

However, it is stated in the article that the expected revenue for the initial problem (DLP) is 155.95 in the second period, which is very unclear to me. In Julia code, the initial problem is as follows:

using JuMP, Gurobi

# DLP without resolving
function DLP()
    dlp = Model(Gurobi.Optimizer)
    
    class_1_dem = 0.5*5 + 0.5*1
    class_2_dem = 0.5*2 + 0.5*4
     
    @variable(dlp, x_1 >= 0)
    @variable(dlp, x_2 >= 0)
    @objective(dlp, Min, -(100*x_1 + 60*x_2))
    @constraint(dlp, cap, x_1 + x_2 <= 4)
    @constraint(dlp, x_1 <= class_1_dem)
    @constraint(dlp, x_2 <= class_2_dem)
    
    optimize!(dlp)
    rev = abs(objective_value(dlp))
    sol = [value(x_1), value(x_2)]

    return sol, rev, abs(shadow_price(cap))
end

and output ([3.0, 1.0], 360.0, 60.0). How do I handle the realization of $\xi_2^1$ to obtain 155.95 as expected revenue after the first period for the DLP? $$ 155.95 = \mathbb{E}[\text{rev}] = \underbrace{0.5 (2\cdot 100 + 0 \cdot 60)}_{\text{2 seats in class 1 and 0 in class 2}} + \underbrace{0.5 (1\cdot 100 + x \cdot 60)}_{\text{1 seat in class 1 and } x \text{ in class 2}}$$

EDIT
This was probably a mistake in the article.

$\endgroup$

0