Car Rental 1


PROC OPTMODEL Statements and Output

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

proc optmodel;
   set <str> DEPOTS;
   read data depot_data into DEPOTS=[depot];

   set DAYS;
   str day_name {DAYS};
   num demand {DEPOTS, DAYS};
   read data demand_data into DAYS=[_N_];
   num num_days = card(DAYS);
   DAYS = 0..num_days-1;
   read data demand_data into [_N_]
      {depot in DEPOTS} <demand[depot,_N_-1]=col(depot)>;

   set LENGTHS;
   num length_prob {LENGTHS};
   num cost {LENGTHS};
   num price_same {LENGTHS};
   num price_diff {LENGTHS};
   read data length_data into LENGTHS=[length]
      length_prob=prob cost price_same price_diff;

   num transition_prob {DEPOTS, DEPOTS};
   read data transition_prob_data into [i]
      {j in DEPOTS} <transition_prob[i,j]=col(j)>;
   for {i in DEPOTS, j in DEPOTS}
      transition_prob[i,j] = transition_prob[i,j] / 100;

   num transfer_cost {DEPOTS, DEPOTS} init 0;
   read data transfer_cost_data nomiss into [i]
      {j in DEPOTS} <transfer_cost[i,j]=col(j)>;

   num repair_capacity {DEPOTS} init 0;
   read data repair_data into [depot] repair_capacity;

   num rental_price {i in DEPOTS, j in DEPOTS, day in DAYS, length in LENGTHS} =
      (if i = j then price_same[length] else price_diff[length])
    - (if day = 5 and length = 1 then &saturday_discount);

Because the company wants a periodic solution, all indices that correspond to days are taken modulo num_days. For simplicity, this notation is suppressed in the mathematical programming formulation that is described earlier. The following statements declare parameters to be used for that purpose in the subsequent constraint declarations:

   num max_length = max {length in LENGTHS} length;
   num mod {s in -max_length..num_days+max_length} = mod(s+num_days,num_days);

The following model declaration statements correspond directly to the mathematical programming formulation that is described earlier:

   var NumCars >= 0;

   var NumUndamagedCarsStart {DEPOTS, DAYS} >= 0;
   var NumDamagedCarsStart {DEPOTS, DAYS} >= 0;

   var NumCarsRented_i_day {i in DEPOTS, day in DAYS} >= 0 <= demand[i,day];
   impvar NumCarsRented
      {i in DEPOTS, j in DEPOTS, day in DAYS, length in LENGTHS} =
      transition_prob[i,j] * length_prob[length] * NumCarsRented_i_day[i,day];

   var NumUndamagedCarsIdle {DEPOTS, DAYS} >= 0;
   var NumDamagedCarsIdle {DEPOTS, DAYS} >= 0;

   var NumUndamagedCarsTransferred {i in DEPOTS, DEPOTS diff {i}, DAYS} >= 0;
   var NumDamagedCarsTransferred {i in DEPOTS, DEPOTS diff {i}, DAYS} >= 0;
   impvar NumCarsTransferred {i in DEPOTS, j in DEPOTS diff {i}, day in DAYS} =
      NumUndamagedCarsTransferred[i,j,day]
    + NumDamagedCarsTransferred[i,j,day];

   var NumDamagedCarsRepaired {i in DEPOTS, DAYS} >= 0 <= repair_capacity[i];

   max Profit =
      sum {i in DEPOTS, j in DEPOTS, day in DAYS, length in LENGTHS}
         (rental_price[i,j,day,length] - cost[length])
       * NumCarsRented[i,j,day,length]
    + sum {i in DEPOTS, day in DAYS}
         &damage_prob * &damage_charge * NumCarsRented_i_day[i,day]
    - sum {i in DEPOTS, j in DEPOTS diff {i}, day in DAYS}
         transfer_cost[i,j] * NumCarsTransferred[i,j,day]
    - &opportunity_cost_per_week * NumCars;

   con Undamaged_Inflow_con {i in DEPOTS, day in DAYS}:
      NumUndamagedCarsStart[i,day]
    = (1 - &damage_prob) * sum {j in DEPOTS, length in LENGTHS}
         NumCarsRented[j,i,mod[day-length],length]
    + sum {j in DEPOTS diff {i}}
         NumUndamagedCarsTransferred[j,i,mod[day-&transfer_length]]
    + NumDamagedCarsRepaired[i,mod[day-&repair_length]]
    + NumUndamagedCarsIdle[i,mod[day-1]];

   con Damaged_Inflow_con {i in DEPOTS, day in DAYS}:
      NumDamagedCarsStart[i,day]
    = &damage_prob * sum {j in DEPOTS, length in LENGTHS}
         NumCarsRented[j,i,mod[day-length],length]
    + sum {j in DEPOTS diff {i}}
         NumDamagedCarsTransferred[j,i,mod[day-&transfer_length]]
    + NumDamagedCarsIdle[i,mod[day-1]];

   con Undamaged_Outflow_con {i in DEPOTS, day in DAYS}:
      NumUndamagedCarsStart[i,day]
    = NumCarsRented_i_day[i,day]
    + sum {j in DEPOTS diff {i}} NumUndamagedCarsTransferred[i,j,day]
    + NumUndamagedCarsIdle[i,day];

   con Damaged_Outflow_con {i in DEPOTS, day in DAYS}:
      NumDamagedCarsStart[i,day]
    = NumDamagedCarsRepaired[i,day]
    + sum {j in DEPOTS diff {i}} NumDamagedCarsTransferred[i,j,day]
    + NumDamagedCarsIdle[i,day];

   con NumCars_con:
      NumCars = sum {i in DEPOTS} (
         length_prob[3] * NumCarsRented_i_day[i,0]
       + sum {length in 2..3} length_prob[length] * NumCarsRented_i_day[i,1]
       + NumUndamagedCarsStart[i,2]
       + NumDamagedCarsStart[i,2]);

The NumCars_con constraint expresses the fact that every car is rented on Monday for three days, rented on Tuesday for two or three days, or at some depot at the beginning of Wednesday.

The following statements call the LP solver and use the generic problem symbols _NVAR_ and _VAR_ to round all variables to integer values, as in Williams (2013):

   solve;
   for {j in 1.._NVAR_} _VAR_[j] = round(_VAR_[j].sol);

The following statements print the solution and use the .dual variable suffix to print the shadow prices for repair capacity:

   print NumCars;
   print NumUndamagedCarsStart;
   print NumDamagedCarsStart;
   print NumCarsRented_i_day;
   print {i in DEPOTS, j in DEPOTS diff {i}, day in DAYS:
      NumDamagedCarsTransferred[i,j,day].sol > 0} NumDamagedCarsTransferred;
   print NumDamagedCarsRepaired.dual;
quit;

Figure 25.1 shows the output from the linear programming solver.

Figure 25.1: Output from Linear Programming Solver

The OPTMODEL Procedure

Problem Summary
Objective Sense Maximization
Objective Function Profit
Objective Type Linear
   
Number of Variables 289
Bounded Above 0
Bounded Below 241
Bounded Below and Above 36
Free 0
Fixed 12
   
Number of Constraints 97
Linear LE (<=) 0
Linear EQ (=) 97
Linear GE (>=) 0
Linear Range 0
   
Constraint Coefficients 1145

Performance Information
Execution Mode Single-Machine
Number of Threads 1

Solution Summary
Solver LP
Algorithm Dual Simplex
Objective Function Profit
Solution Status Optimal
Objective Value 119302.04331
   
Primal Infeasibility 3.836931E-13
Dual Infeasibility 5.684342E-13
Bound Infeasibility 0
   
Iterations 82
Presolve Time 0.00
Solution Time 0.00

NumCars
681

NumUndamagedCarsStart
  0 1 2 3 4 5
Birmingham 183 195 126 127 145 182
Glasgow 111 82 70 79 79 71
Manchester 163 104 99 126 110 100
Plymouth 67 44 42 48 47 43

NumDamagedCarsStart
  0 1 2 3 4 5
Birmingham 25 20 22 20 20 20
Glasgow 4 8 8 13 13 8
Manchester 12 12 12 12 12 12
Plymouth 3 5 5 6 12 17

NumCarsRented_i_day
  0 1 2 3 4 5
Birmingham 95 195 126 111 70 81
Glasgow 100 82 70 79 79 0
Manchester 163 104 80 126 110 0
Plymouth 67 44 42 48 47 0

[1] [2] [3] NumDamagedCarsTransferred
Glasgow Birmingham 0 3
Glasgow Birmingham 1 6
Glasgow Birmingham 2 2
Glasgow Birmingham 3 8
Glasgow Birmingham 4 10
Glasgow Birmingham 5 2
Glasgow Manchester 0 2
Glasgow Manchester 1 2
Glasgow Manchester 2 1
Glasgow Manchester 3 1
Glasgow Manchester 4 2
Glasgow Manchester 5 6
Plymouth Birmingham 0 3
Plymouth Birmingham 1 5
Plymouth Birmingham 2 4
Plymouth Birmingham 5 17

NumDamagedCarsRepaired.DUAL
  0 1 2 3 4 5
Birmingham 591.46 590.99 591.46 591.46 591.46 591.46
Glasgow 625.49 637.39 635.16 632.06 625.49 625.49
Manchester 607.36 602.62 617.62 615.27 610.84 610.84
Plymouth 622.55 634.02 632.50 630.10 625.55 625.55



The optimal solution, objective value, and shadow prices differ from Williams (2013), because of errors that will be corrected in a subsequent printing by Wiley.