Yield Management: What Quantities of Airline Tickets to Sell at What Prices and What Times

The first several PROC OPTMODEL statements declare index sets and parameters and then read the input data:

proc optmodel;
   set PERIODS = 1..&num_periods;

   set <str> CLASSES;
   num num_seats {CLASSES};
   read data class_data into CLASSES=[class] num_seats;

   set OPTIONS = 1..&num_options;

   num price {PERIODS, CLASSES, OPTIONS};
   read data price_data into [period class]
      {option in OPTIONS} <price[period,class,option]=col('price'||option)>;

   set SCENARIOS;
   num prob {SCENARIOS};
   read data scenario_data into SCENARIOS=[_N_] prob;
   set SCENARIOS2 = SCENARIOS cross SCENARIOS;
   set SCENARIOS3 = SCENARIOS2 cross SCENARIOS;

   num demand {PERIODS, SCENARIOS, CLASSES, OPTIONS};
   read data demand_data into [period scenario class]
      {option in OPTIONS}
      <demand[period,scenario,class,option]=col('demand'||option)>;

   num actual_demand {PERIODS, CLASSES, OPTIONS};
   read data actual_demand_data into [period class]
      {option in OPTIONS}
      <actual_demand[period,class,option]=col('demand'||option)>;

   num actual_price {PERIODS, CLASSES};
   num actual_sales {PERIODS, CLASSES};
   num actual_revenue {PERIODS, CLASSES};

   num current_period;

The following VAR statements declare the decision variables:

   var P1 {CLASSES, OPTIONS} binary;
   var P2 {SCENARIOS, CLASSES, OPTIONS} binary;
   var P3 {SCENARIOS2, CLASSES, OPTIONS} binary;

   var S1 {SCENARIOS, CLASSES, OPTIONS} >= 0;
   var S2 {SCENARIOS2, CLASSES, OPTIONS} >= 0;
   var S3 {SCENARIOS3, CLASSES, OPTIONS} >= 0;

   var R1 {SCENARIOS, CLASSES, OPTIONS} >= 0;
   var R2 {SCENARIOS2, CLASSES, OPTIONS} >= 0;
   var R3 {SCENARIOS3, CLASSES, OPTIONS} >= 0;

   var TransferFrom {SCENARIOS3, CLASSES} >= 0;
   var TransferTo {SCENARIOS3, CLASSES} >= 0;

   var NumPlanes >= 0 <= &num_planes integer;

The following CON statement declares the constraints that enforce seat capacities:

   con NumPlanes_con {<i,j,k> in SCENARIOS3, class in CLASSES}:
      sum {option in OPTIONS}
         (S1[i,class,option] + S2[i,j,class,option] + S3[i,j,k,class,option])
    + TransferFrom[i,j,k,class] - TransferTo[i,j,k,class]
   <= num_seats[class] * NumPlanes;

The following statements declare the constraints that restrict adjustment between classes:

   for {<i,j,k> in SCENARIOS3, class in CLASSES} do;
      TransferFrom[i,j,k,class].ub = &transfer_fraction_ub * num_seats[class];
      TransferTo[i,j,k,class].ub   = &transfer_fraction_ub * num_seats[class];
   end;
   con Balance_con {<i,j,k> in SCENARIOS3}:
      sum {class in CLASSES} TransferFrom[i,j,k,class]
    = sum {class in CLASSES} TransferTo[i,j,k,class];

The following CON statements declare the constraints that enforce one price level per class:

   con P1_con {class in CLASSES}:
      sum {option in OPTIONS} P1[class,option] = 1;
   con P2_con {i in SCENARIOS, class in CLASSES}:
      sum {option in OPTIONS} P2[i,class,option] = 1;
   con P3_con {<i,j> in SCENARIOS2, class in CLASSES}:
      sum {option in OPTIONS} P3[i,j,class,option] = 1;

The following CON statements declare the constraints that sales cannot exceed demand:

   con S1_con {i in SCENARIOS, class in CLASSES, option in OPTIONS}:
      S1[i,class,option] <= demand[1,i,class,option] * P1[class,option];
   con S2_con {<i,j> in SCENARIOS2, class in CLASSES, option in OPTIONS}:
      S2[i,j,class,option] <= demand[2,j,class,option] * P2[i,class,option];
   con S3_con {<i,j,k> in SCENARIOS3, class in CLASSES, option in OPTIONS}:
      S3[i,j,k,class,option] <= demand[3,k,class,option] *
         P3[i,j,class,option];

The following CON statements encode one possible linearization of the quadratic objective:

   /* R1[i,class,option] =
      price[1,class,option] * P1[class,option] * S1[i,class,option] */
   con R1_con_a {i in SCENARIOS, class in CLASSES, option in OPTIONS}:
      R1[i,class,option] <= price[1,class,option] * S1[i,class,option];
   con R1_con_b {i in SCENARIOS, class in CLASSES, option in OPTIONS}:
      price[1,class,option] * S1[i,class,option] - R1[i,class,option]
   <= price[1,class,option] * demand[1,i,class,option] *
         (1 - P1[class,option]);

   /* R2[i,j,class,option] =
      price[2,class,option] * P2[i,class,option] * S2[i,j,class,option] */
   con R2_con_a {<i,j> in SCENARIOS2, class in CLASSES, option in OPTIONS}:
      R2[i,j,class,option] <= price[2,class,option] * S2[i,j,class,option];
   con R2_con_b {<i,j> in SCENARIOS2, class in CLASSES, option in OPTIONS}:
      price[2,class,option] * S2[i,j,class,option] - R2[i,j,class,option]
   <= price[2,class,option] * demand[2,j,class,option] *
         (1 - P2[i,class,option]);

   /* R3[i,j,k,class,option] =
      price[3,class,option] * P3[i,j,class,option] * S3[i,j,k,class,option] */
   con R3_con_a {<i,j,k> in SCENARIOS3, class in CLASSES, option in OPTIONS}:
      R3[i,j,k,class,option] <= price[3,class,option] * S3[i,j,k,class,option];
   con R3_con_b {<i,j,k> in SCENARIOS3, class in CLASSES, option in OPTIONS}:
      price[3,class,option] * S3[i,j,k,class,option] - R3[i,j,k,class,option]
   <= price[3,class,option] * demand[3,k,class,option] *
         (1 - P3[i,j,class,option]);

An alternative "compact linearization" (not shown) involves fewer constraints, as in Chapter 10.

The following MAX statement declares the linearized objective, which depends on current_period:

   max ExpectedYield =
      (if current_period <= 1
       then sum {i in SCENARIOS, class in CLASSES, option in OPTIONS}
               prob[i] * R1[i,class,option])
    + (if current_period <= 2
       then sum {<i,j> in SCENARIOS2, class in CLASSES, option in OPTIONS}
               prob[i] * prob[j] * R2[i,j,class,option])
    + (if current_period <= 3
       then sum {<i,j,k> in SCENARIOS3, class in CLASSES, option in OPTIONS}
               prob[i] * prob[j] * prob[k] * R3[i,j,k,class,option])
    + sum {period in 1..current_period-1, class in CLASSES}
         actual_revenue[period,class]
    - &plane_cost * NumPlanes;

The following NUM statements use the .sol variable suffix to compute the recommended prices from the optimal values of the decision variables:

   num price_sol_1 {class in CLASSES} =
      sum {option in OPTIONS} price[1,class,option] * P1[class,option].sol;
   num price_sol_2 {class in CLASSES, i in SCENARIOS} =
      sum {option in OPTIONS} price[2,class,option] * P2[i,class,option].sol;
   num price_sol_3 {class in CLASSES, <i,j> in SCENARIOS2} =
      sum {option in OPTIONS} price[3,class,option] * P3[i,j,class,option].sol;

The following NUM statements use the .sol variable suffix to compute the recommended numbers of seats to sell:

   num remaining_seats {class in CLASSES} =
      num_seats[class] * NumPlanes.sol
    - sum {period in 1..current_period-1} actual_sales[period,class];
   num sell_up_to_1 {class in CLASSES} =
      min(
         max {i in SCENARIOS, option in OPTIONS} S1[i,class,option].sol,
         remaining_seats[class]);
   num sell_up_to_2 {class in CLASSES} =
      min(
         max {<i,j> in SCENARIOS2, option in OPTIONS} S2[i,j,class,option].sol,
         remaining_seats[class]);
   num sell_up_to_3 {class in CLASSES} =
      min(
         max {<i,j,k> in SCENARIOS3, option in OPTIONS}
         S3[i,j,k,class,option].sol, remaining_seats[class]);

The following statements call the mixed integer linear programming solver to determine the optimal prices for period 1:

   current_period = 1;
   solve;
   for {i in SCENARIOS, class in CLASSES, option in OPTIONS}
      S1[i,class,option] = round(S1[i,class,option].sol);
   print price_sol_1;
   print sell_up_to_1;
   print {i in SCENARIOS, class in CLASSES, option in OPTIONS:
      S1[i,class,option].sol > 0} S1;
   print price_sol_2;
   print price_sol_3;
   print NumPlanes ExpectedYield;

The following statements fix the resulting prices for period 1 and use the MIN function to limit sales based on actual demand:

   for {class in CLASSES, option in OPTIONS} do;
      if P1[class,option].sol > 0.5 then do;
         fix P1[class,option] = 1;
         actual_price[1,class] = price_sol_1[class];
         actual_sales[1,class] =
            min(sell_up_to_1[class], actual_demand[1,class,option]);
         for {i in SCENARIOS} fix S1[i,class,option] = actual_sales[1,class];
      end;
      else fix P1[class,option] = 0;
   end;
   for {class in CLASSES}
      actual_revenue[1,class] = actual_price[1,class] * actual_sales[1,class];
   print actual_price actual_sales actual_revenue;

Figure 24.1 shows the output from the mixed integer linear programming solver for period 1.

The following statements drop the period 1 constraints and call the mixed integer linear programming solver to determine the optimal prices for period 2:

   drop P1_con S1_con R1_con_a R1_con_b;
   current_period = 2;
   solve;
   for {<i,j> in SCENARIOS2, class in CLASSES, option in OPTIONS}
      S2[i,j,class,option] = round(S2[i,j,class,option].sol);
   print price_sol_2;
   print sell_up_to_2;
   print {<i,j> in SCENARIOS2, class in CLASSES, option in OPTIONS:
      i = 1 and S2[1,j,class,option].sol > 0} S2;
   print price_sol_3;
   print NumPlanes ExpectedYield;

The following statements fix the resulting prices for period 2 and use the MIN function to limit sales based on actual demand:

   for {i in SCENARIOS, class in CLASSES, option in OPTIONS} do;
      if P2[i,class,option].sol > 0.5 then do;
         fix P2[i,class,option] = 1;
         actual_price[2,class] = price_sol_2[class,i];
         actual_sales[2,class] =
            min(sell_up_to_2[class], actual_demand[2,class,option]);
         for {j in SCENARIOS} fix S2[i,j,class,option] = actual_sales[2,class];
      end;
      else fix P2[i,class,option] = 0;
   end;
   for {class in CLASSES}
      actual_revenue[2,class] = actual_price[2,class] * actual_sales[2,class];
   print actual_price actual_sales actual_revenue;

Figure 24.2 shows the output from the mixed integer linear programming solver for period 2.

The following statements drop the period 2 constraints and call the mixed integer linear programming solver to determine the optimal prices for period 3:

   current_period = 3;
   drop P2_con S2_con R2_con_a R2_con_b;
   solve;

   for {<i,j,k> in SCENARIOS3, class in CLASSES, option in OPTIONS}
      S3[i,j,k,class,option] = round(S3[i,j,k,class,option].sol);
   print price_sol_3;
   print sell_up_to_3;
   print {<i,j,k> in SCENARIOS3, class in CLASSES, option in OPTIONS:
      <i,j> in {<1,1>} and S3[i,j,k,class,option].sol > 0} S3;
   print NumPlanes ExpectedYield;

The following statements fix the resulting prices for period 3 and use the MIN function to limit sales based on actual demand:

   for {<i,j> in SCENARIOS2, class in CLASSES, option in OPTIONS} do;
      if P3[i,j,class,option].sol > 0.5 then do;
         fix P3[i,j,class,option] = 1;
         actual_price[3,class] = price_sol_3[class,i,j];
         actual_sales[3,class] =
            min(sell_up_to_3[class], actual_demand[3,class,option]);
         for {k in SCENARIOS} fix S3[i,j,k,class,option]
            = actual_sales[3,class];
      end;
      else fix P3[i,j,class,option] = 0;
   end;

   for {class in CLASSES}
      actual_revenue[3,class] = actual_price[3,class] * actual_sales[3,class];
   print actual_price actual_sales actual_revenue;

Figure 24.3 shows the output from the mixed integer linear programming solver for period 3.

The following statements print the expected yield that results from the optimal prices, with sales limited by actual demands:

   current_period = 4;
   print ExpectedYield;
quit;

Figure 24.4 shows the final expected yield.

Maximizing yield based on expected demands is much simpler than the stochastic programming approach and requires only one solver call. The first several PROC OPTMODEL statements are the same as before:

proc optmodel;
   set PERIODS = 1..&num_periods;

   set <str> CLASSES;
   num num_seats {CLASSES};
   read data class_data into CLASSES=[class] num_seats;

   set OPTIONS = 1..&num_options;

   num price {PERIODS, CLASSES, OPTIONS};
   read data price_data into [period class]
      {option in OPTIONS} <price[period,class,option]=col('price'||option)>;

   set SCENARIOS;
   num prob {SCENARIOS};
   read data scenario_data into SCENARIOS=[_N_] prob;

   num demand {PERIODS, SCENARIOS, CLASSES, OPTIONS};
   read data demand_data into [period scenario class]
      {option in OPTIONS}
      <demand[period,scenario,class,option]=col('demand'||option)>;

   num actual_demand {PERIODS, CLASSES, OPTIONS};
   read data actual_demand_data into [period class]
      {option in OPTIONS}
      <actual_demand[period,class,option]=col('demand'||option)>;

   num actual_price {PERIODS, CLASSES};
   num actual_sales {PERIODS, CLASSES};
   num actual_revenue {PERIODS, CLASSES};

The following NUM statement declares the expected_demand parameter as a weighted sum of demand:

   num expected_demand {period in PERIODS, class in CLASSES, option in OPTIONS}
      = sum {scenario in SCENARIOS}
         prob[scenario] * demand[period,scenario,class,option];

Note that the variables, constraints, and parameters are unified and simplified into fewer families than before:

   var P {PERIODS, CLASSES, OPTIONS} binary;
   var S {PERIODS, CLASSES, OPTIONS} >= 0;
   var R {PERIODS, CLASSES, OPTIONS} >= 0;

   var TransferFrom {CLASSES} >= 0;
   var TransferTo {CLASSES} >= 0;

   var NumPlanes >= 0 <= &num_planes integer;

   con NumPlanes_con {class in CLASSES}:
      sum {period in PERIODS, option in OPTIONS} S[period,class,option]
    + TransferFrom[class] - TransferTo[class]
   <= num_seats[class] * NumPlanes;

   for {class in CLASSES} do;
      TransferFrom[class].ub = &transfer_fraction_ub * num_seats[class];
      TransferTo[class].ub   = &transfer_fraction_ub * num_seats[class];
   end;
   con Balance_con:
      sum {class in CLASSES} TransferFrom[class]
    = sum {class in CLASSES} TransferTo[class];

   con P_con {period in PERIODS, class in CLASSES}:
      sum {option in OPTIONS} P[period,class,option] = 1;

   con S_con {period in PERIODS, class in CLASSES, option in OPTIONS}:
      S[period,class,option]
   <= expected_demand[period,class,option] * P[period,class,option];

   /* R[period,class,option] =
      price[period,class,option] * P[period,class,option] *
         S[period,class,option] */
   con R_con_a {period in PERIODS, class in CLASSES, option in OPTIONS}:
      R[period,class,option] <= price[period,class,option] *
         S[period,class,option];
   con R_con_b {period in PERIODS, class in CLASSES, option in OPTIONS}:
      price[period,class,option] * S[period,class,option] -
         R[period,class,option]
   <= price[period,class,option] * expected_demand[period,class,option]
      * (1 - P[period,class,option]);

   max Yield =
      sum {period in PERIODS, class in CLASSES, option in OPTIONS}
         R[period,class,option]
    - &plane_cost * NumPlanes;

   num price_sol {period in PERIODS, class in CLASSES} =
      sum {option in OPTIONS} price[period,class,option] *
         P[period,class,option].sol;

   solve;
   for {period in PERIODS, class in CLASSES, option in OPTIONS}
      S[period,class,option] = round(S[period,class,option].sol);
   print price_sol;
   print {period in PERIODS, class in CLASSES, option in OPTIONS:
      S[period,class,option].sol > 0} S;
   print NumPlanes Yield;
   for {period in PERIODS, class in CLASSES, option in OPTIONS} do;
      if P[period,class,option].sol > 0.5 then do;
         actual_price[period,class] = price_sol[period,class];
         actual_sales[period,class] =
            min(S[period,class,option], actual_demand[period,class,option]);
         actual_revenue[period,class] =
            actual_price[period,class] * actual_sales[period,class];
         R[period,class,option] = actual_revenue[period,class];
      end;
   end;
   print actual_price actual_sales actual_revenue;
   print Yield;

Figure 24.5 shows the output from the mixed integer linear programming solver for the problem based on expected demands.

As anticipated, the yield is smaller than in Figure 24.4 because there is no opportunity here to change prices based on actual demand from previous periods.

The following statements show the modifications to maximize yield based on actual demands:

   drop S_con R_con_b;

   con S_con_actual {period in PERIODS, class in CLASSES, option in OPTIONS}:
      S[period,class,option]
   <= actual_demand[period,class,option] * P[period,class,option];

   con R_con_b_actual {period in PERIODS, class in CLASSES, option in OPTIONS}:
      price[period,class,option] * S[period,class,option] -
         R[period,class,option]
   <= price[period,class,option] * actual_demand[period,class,option]
      * (1 - P[period,class,option]);

   solve;
   for {period in PERIODS, class in CLASSES, option in OPTIONS}
      S[period,class,option] = round(S[period,class,option].sol);
   print price_sol;
   print {period in PERIODS, class in CLASSES, option in OPTIONS:
      S[period,class,option].sol > 0} S;
   print NumPlanes Yield;

Because actual demand is considered directly in this formulation, the postprocessing steps do not need to reduce sales to actual demand:

   for {period in PERIODS, class in CLASSES, option in OPTIONS} do;
      if P[period,class,option].sol > 0.5 then do;
         actual_price[period,class] = price_sol[period,class];
         actual_sales[period,class] = S[period,class,option];
         actual_revenue[period,class] =
            actual_price[period,class] * actual_sales[period,class];
         R[period,class,option] = actual_revenue[period,class];
      end;
   end;
   print actual_price actual_sales actual_revenue;
quit;

Figure 24.6 shows the output from the mixed integer linear programming solver for the problem based on actual demands.

As anticipated, the yield is highest here because optimal prices and sales are determined with perfect knowledge of demand.

The stochastic programming formulation shown earlier represents a natural compromise between the deterministic formulations based on expected demand or actual demand.