Example 5.
Scheduling Flights at TriCities Airlines
Background Information
• TriCities Airlines flies several daily commuter flights to and
from the three cities New York, Washington, D.C. and
Boston.
• The company has been flying a fixed daily schedule of
flights, but it is now deciding whether to change this
schedule.
• Each potential flight has an estimated net revenue that is
based on the typical number of passengers for the flight.
• The company owns 4 airplanes, and it does not anticipate
buying any more.
Background Information --
continued
• There is a fixed cost per plane per day that flies
any flights. However, a plane that is not used does
not incur this fixed cost.
• We assume that there is no required delay time on
the ground, so that if a flight arrives in Boston at
time 10, it can leave on a new flight at time 10.
• Also, any plane that arrives to a city after its last
flight of the day has two options. It can sit
overnight in that city, or at a cost of $500, it can be
flown empty to another city overnight.
Background Information --
continued
• The company’s objective is to maximize its net
profit per day, which equals net revenues from
flights flown, minus fixed costs of flying planes,
minus overnight costs of flying empty.
Solution
• We first discuss how this problem can be modeled as a
minimum cost network flow model – which is certainly not
obvious.
• The trick is to have a node for each city/time combination.
Because we allow flights on the half-hour, this means
having nodes of the form Boston8, Boston8.5 and so on,
up to WashDC20.
• There are three types of arcs
– The most obvious type is the “flight” arc. The flow on such an arc
represents the number of planes that fly this flight. Because each
flight should be flown at most once, we impose a capacity of 1 on
all such flight arcs. The “cost” on a flight arc is the net revenue for
flying the flight.
Solution -- continued
– If a flight arrives into New York, say, at time 13, it might sit on the
ground until time 14.5, at which time it leaves for another city. We
model this with the “ground” arcs NY13-NY13.5, NY13.5-NY14,
and NY14-NY14.5. In general, the flow on any ground arc
represents the number of planes sitting on the ground in that city
for the half-hour period. These ground arcs have no capacities and
no costs.
– Finally, the real trick involves relating one day to the next. Suppose
one or more planes end up in New York at the end of the day, at
time 20. They can either sit overnight in New York or they can be
flown to another city, where they will be available at time 8 the next
morning. To model this, we use “overnight” arcs. The flow on an
overnight arc such as NY20-NY8 represents the number of planes
that sit overnight in New York.
Solution -- continued
– A “overnight” arc has no capacity and a cost equal to the fixed cost
of operating a plane. In contrast, the flow on an overnight arc such
as NY20-Boston8 represents the number of planes flown overnight
from New York to Boston. It has no capacity and a cost equal to the
fixed cost of operating a plane plus the cost of flying a plane empty
overnight. Note the total flow on all overnight arcs equals the total
number of planes being used – all planes being used must be
somewhere overnight. In fact, we put a “side” constraint on this
total – it must be less than or equal to the number of planes owned,
4.
• A few of the nodes and arcs for this network are shown on
the next slide. The flight arcs are the diagonal arcs, the
ground arcs all point one step to the right, and the
overnight arcs go backward from right to left.
Solution -- continued
• With this network, there is flow balance at every node. This
might be called “conservation of planes”. The same planes
continue to circulate through the network day after day. Of
course if we wanted different schedules on different days
of the week, we would have to change the model, and it
would become considerably more complex.
Flight [Link]
• The finished model is quite large so we will show it
in pieces. This file contains the model.
• The next slide shows the potential flight schedule,
plus several other inputs.
• Recall that TriCities wants to select the
appropriate subset of these flights to fly, which
could be all of them.
• Note that the cost of flying a plane empty
overnight is a constant. We could easily allow this
cost to depend on the origin and destination of the
flight.
Developing the Model
• The information on the three types of arcs
appears on the following three slides.
• The flight arcs correspond exactly to the available
flights shown. Note that each flight arc has a
capacity of 1.
• There are many ground arcs, each extending one
half-hour into the day and their costs are all 0.
• Finally, there are only nine overnight arcs. Each
has a fixed cost, and those that represent empty
overnight flights also have an overnight cost.
Flight arcs
Ground arcs
Overnight arcs
Developing the Model --
continued
• The rest is straightforward. As usual, we fill out a
table of flow balance constraints, as shown below.
• Note that many rows have been hidden. There is
a constraint for each node – that is, each city/time
combination.
Developing the Model --
continued
• The typical formula for net outflow in cell I37, which can be
copied down column I, is
=SUMIF(Flight_OriginH37,Flight_flow)+SUMIF(Ground_
Origin,H37,Ground_flow) +SUMIF(Overnight_Origin,
H37,Overnight_flow)
-(SUMIF(Flight_destination,H37,Flight_flow)
+SUMIF(Ground_destination,
H37,Ground_flow)+SUMIF(Overnight_destination,
H37,Overnight_flow)).
• This looks complex, but it is simply the sum of outflows
from the three types of arcs minus the sum of inflows from
the three types of arcs. Because there must be flow
balance at each node, we constrain each net outflow to be
0.
Developing the Model --
continued
• The next slide shows the rest of the model and the
Solver dialog box.
• To find the number of planes used, we sum the
flows on all overnight arcs in cell B150 with the
formula =SUM(Overnight_flow).
• Then we calculate the various monetary values
with the usual SUMPRODUCT functions.
• For example, the formula for total net revenue
from flights is
=SUMPRODUCT(Flight_net_revenue,
Flight_flow).
Developing the Model --
continued
• Finally, we combine these into a profit objective in
cell B156 with the formula =B153-B154-B155
• The Solver dialog box follows easily – and is
remarkably compact for such a large and complex
model.
Solution
• The optimal solution can be seen primarily in the
tables for flight arcs and overnight arcs.
• The former indicates that TriCities should fly only
17 of the potential 23 flights.
• The latter shows that no overnight flights should
be flown.
• It also shows that all four planes are used. Two of
which will sit overnight in Boston, and the other
two will sit overnight in Washington, D.C. The daily
profit is $39,600.
Sensitivity Analysis
• There are many interesting sensitivity analyses we
might run.
• For example, what if TriCities had more planes?
• To answer this, we run SolverTable with the cell
B4 as the single input cell, allowing it to vary from
4 to 8 in increments of 1, and we keep track of
monetary values, as well as the number of flights
flown.
• The results appear on the next slide.
Sensitivity Analysis --
continued
• As expected, profit and the number of flights flown
both increase when the company owns more
planes, but this analysis does not take the cost of
purchasing more planes into account.
• TriCities would need to trade off the cost of new
planes with this increased profit.
• From the previous figure, we see that TriCities still
does not fly all 23 potential flights, even with 8
planes. Could it?
Sensitivity Analysis --
continued
• We can answer this question easily by changing
the objective from maximizing profit to maximizing
the number of flights flown and rerunning Solver.
• If you do so, you will find that maximum is 23.
Therefore, TriCities could fly all 23 flights with 8
planes, but the cost structure makes it more
profitable to fly only 22.
• The driving factor here is evidently the fixed cost
per plane. When TriCities owns 8 planes, the
optimal profit solution uses only 7 of these planes.
Sensitivity Analysis --
continued
• A final sensitivity analysis involves empty
overnight flights.
• When TriCities owns 7 planes, it is shown that it
flies two empty overnight flights. What would
happen to this solution if, as a matter of company
policy, empty overnight flights were not allowed?
• There are three ways we could modify the model
to answer this question.
Sensitivity Analysis --
continued
• First, we could impose a huge cost of overnight
flights, effectively ruling them out.
• Second, we could impose capacities of 0 on the
overnight flight arcs.
• Third, we could simply eliminate the arcs.
• We used the first method, with the results shown
on the next slide.
Sensitivity Analysis --
continued
• The solution changes fairly dramatically. Now
TriCities uses only 5 of its 7 planes, it flies only 19
(instead of 22) flights, and its profit decreases
from $43,600 to $42,000.