Page 307 -

TRANSPORTATION SIMPLEX METHOD: A SPECIAL-PURPOSE SOLUTION PROCEDURE 287

MANAGEMENT SCIENCE IN ACTION

UPS’s optimization-based transportation planning system – VOLCANO
PS is a major delivery company operating in six regional hubs in other key US locations and
U over 200 countries and dealing with a huge more than 100 airports. An optimization-based
volume of deliveries each day: over 13 million transportation planning system has been devel-
packages and eight million customers. One of its oped, called VOLCANO (the Volume, Location
premium delivery services in the USA, next day air, and Aircraft Network Optimizer) and UPS reckons
utilizes the company’s huge fleet of aircraft (over to have saved over $90 million through using the
250) to transport packages that have been optimization modeller with a further saving of $200
dropped off by customers by early evening to their million over the next decade. UPS’s Tome Weide-
destinations by the following morning. Clearly, given meyer commented ‘VOLCANO will make UPS more
the complexity of the delivery network and the huge competitive by ensuring we are running the most
volume of deliveries, decisions on transportation efficient network possible’.
routes are critical to the company’s success. In
the case of the next day air service, UPS has a Based on A. P. Armacost, C. Barnhart, K. A. Ware and A. M. Wilson
network with a central hub in Louisville, Kentucky ‘UPS Optimizes its Air Network’, Interfaces 34/1 (2004): 15–25.

In Section 7.1 we introduced the Foster Electronics transportation problem and
showed how to formulate and solve it as a linear programme. The LP formulation
involved 12 variables and seven constraints. In this section we describe a special-
purpose solution procedure, called the transportation simplex method, that takes
advantage of the network structure of the transportation problem and makes pos-
sible the solution of large transportation problems efficiently on a computer and
small transportation problems by hand.
The transportation simplex method, like the simplex method for linear
programmes, is a two-phase procedure; it involves first finding an initial
feasible solution and then proceeding iteratively to make improvements in the
solution until an optimal solution is reached. To summarize the data conven-
iently and to keep track of the calculations, we utilize a transportation tableau.
The transportation tableau for the Foster Electronics problem is presented in
Table 7.3.
Note that the 12 cells in the tableau correspond to the 12 arcs shown in
Figure 7.1; that is, each cell corresponds to the route from one origin to one
destination. So, each cell in the transportation tableau corresponds to a variable
in the linear programming formulation. The entries in the right-hand margin of
the tableau indicate the supply at each origin, and the entries in the bottom
margin indicate the demand at each destination. Each row corresponds to a
supply node, and each column corresponds to a demand node in the network
model of the problem. The number of rows plus the number of columns equals
the number of constraints in the linear programming formulation of the prob-
lem. The entries in the upper right-hand corner of each cell show the trans-
portation cost per unit shipped over the corresponding route. Note also that for
the Foster Electronics problem total supply equals total demand. The trans-
portation simplex method can be applied only to a balanced problem (total
supply ¼ total demand); if a problem is not balanced, a dummy origin or dummy
destination must be added. The use of dummy origins and destinations will be
discussed later in this section.

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.