

Stochastic
Programming 


Aircraft Allocation to Routes 


An illustration for simple recourse comes from a 1956 article
by Allen R. Ferguson and George B. Dantzig, The
Allocation of Aircraft to Routes  An Example of Linear Programming
under Uncertain Demand, Management Science, Vol. 2, pp
4573 (1956). The numbers in this example come from the original
article and the description was adapted from the Roger Wetts
book.

Deterministic Equivalent 

An airline has four aircraft
types (A, B, C, D) that fly five routes (R1, ..., R5). Data
regarding the aircraft and passengers are given below. The
figure comes from an Excel worksheet used to solve the problem.
The data reflects 1956 prices and is scaled so it may not seem
realistic. The data here is linked to data items on the math
programming model, so a different instance can easily be constructed
and solved. Revenue gives the revenue
per passenger on each route. Capacity is
the number of passengers per aircraft for each aircraftroute
pair. Operating Cost is the cost of operating
a single aircraft on a route. The Net Operating Cost is
the cost of operating the aircraft less the revenue for a full
aircraft. We express this as a negative number because we will
be minimizing the objective. Availability gives the
maximum number of each aircraft type to be scheduled. Some
aircraft cannot be used on some routes as indicated in the
tables as zero capacity and high operating cost.
Our goal is to find the number of aircraft to send on each
route to minimize the total net operating cost. If the number
of passengers willing to travel on each route were
known we could write this problem as a linear program. We write
the demand constraints as "<=" because it may not be optimal
to satisfy all the demand. The negative values of the objective
coefficients encourage the demand to be met, but the aircraft
availabilities and capacities may make that impossible.
This model has the form of a generalized transportation problem
because the variables are multiplied by nonunit coefficients
in the demand constraints. The transportation model feature
of the Math Programming addin allows this variation by including
flow multipliers. The figure below shows the model
with the data of this instance. The
aircraft
capacities are reflected in the Flow Multiplier matrix.
The demands used in the figure are the expected passenger
demands computed from the probability distributions given
later.
The figure shows the optimum solution with the expected demands.
The solution does not meet all the demand for route 5. Indeed
there is no feasible solution that meets all the expected demand. 


The solution above allows fractional numbers of
aircraft, but of course this is not practical. When we require
that all
variables be integer, the solution meets more demand but has
less profit. 
Recourse Model 

The deterministic solutions do
not recognize the uncertainty in demand. The demand for the
routes are independent random variables with the values and
probabilities shown in the table below. The table was constructed
with the Add Random Variable command from the Random
Variables addin. The case shown is an indexed distribution.
There is a column for each route with Dem_k indicating
the demand for route k. The probabilities are given
at the top of the form and the values of the discrete random
variables on the lower part of the form. For example route
1 has demand of 200 with probability 0.2.
When considering randomness, the aircraft allocation
problem is a simple recourse model. We must choose the allocation
of aircraft to routes before the demand is known. After the
demand is realized we find there is either a shortage of demand
(assigned capacity exceeds demand) or an overage of demand
(demand exceeds assigned capacity). In case of overage, the
aircraft flies fully loaded and there is no penalty since the
original objective coefficients were computed assuming full
use of capacity. When there is a shortage, the aircraft flies
with empty seats. The
unit penalty assigned is the revenue not
received. The simple recourse model is below. The z variables
compute the total capacities allocated to the routes. We use
general notation to allow any number of points in the distribution,
but for the example, there are five possible demands for each
route.
For convenience we have computed the cumulative
distribution and the step intervals below. We have also created
the transpose of the two matrices because the data is used
in the model in the transpose form.
To solve this problem, we return to the worksheet
and create a master problem and subproblems. The master problem
has the same format as considered earlier except we do not
restrict the maximum passenger flow (row 16). The solution
shown is optimum.



The subproblems are on a side
model presented in two parts below. When a side model is placed
on the same page as a transportation form, the references to
the linking variables require two indices. These references
are on rows 42 and 43 in columns T through X. Since the transportation
variables are arranged in an array, the linking variables are
referred to by row and column indices, rather than a single
index as with an LP or network model. The linking variables
in this case are the total seats allocated to each route. These
numbers
are in row 18 of the master problem. For purposes of the indices
the transportation flow matrix is extended to include the flow
received row (row 18 above) and the flow shipped column (column
L). The index for the flow received row is 8. The relevant
cells represent the seats allocated are (8,1), (8,2),...,(8,5).
The variables in columns Z through AE are the parts of the piecewise
linear representation of the expected recourse cost. The parameters
for these variables are in the second part of the side model display.
The upper bounds are the demand steps and the objective coefficients
are the cumulative probabilities. The shortage costs for the routes
are the weights in column R. 


The recourse model can be solved
for integer flows by simply requesting that the variables be
integer through
the Change button at the top of the master problem.
Results are compiled below for the solutions without and with
integer restrictions. The expected value solutions restrict
the demand met by the allocation to the expected value of demand.
The recourse solutions recognize the uncertainty of demand
through the recourse costs and optimize the net profit with
an allowance for demand shortages. Quite different solutions
are obtained. Since we are minimizing the expected value solutions
have better (more negative) net costs. This is because they
assume all seats allocated are used. In fact, seats may be
empty so not all revenue will be realized.


Models representing
uncertainty are not too large with simple recourse.
The example above could have been easily adjusted for more
complex
probability
distributions. The methods of the Approximation page
could have been used for demands with continuous distributions.
This problem is most readily modeled using the
transportation format of the Math Programming addin. The side
model feature is adaptable to this structure. With a side model,
the problem is actually solved as an LP by the Excel Solver.
The free version of the Solver can handle only 200 variables,
so the number of master and subproblem variables cannot exceed
that amount. The
side model grows only linearly with the number of random
demands, so quite large models can be constructed on an Excel
worksheet. The ability to solve these models depends on the
capacity of
the Solver.



