. 9
( 15)


the McMillan problem.

cannot be rotated. First, the parcels are sorted by nonincreasing volumes. Then, the
3-BP-L algorithm (in which 2-BP problems are solved through the BL heuristic) is
used. The solution is made up of six (2.4 — 1.8) m2 sections, loaded as reported in
Figure 5.26. Finally, a 1-BP problem is solved by means of the BFD heuristic. In the
solution (see Table 5.22) three vehicles are used, the most loaded of which carries
a weight of 545.5 kg, much less than the weight capacity. It is worth noting that the
lower bound provided by Equation (5.27) is 37.795/28.08 = 2.

5.5 Questions and Problems
5.1 Show that a warehouse can be modelled as a queueing system.

5.2 A warehouse stores nearly 20 000 pallets. Goods turn about ¬ve times a year.
How much is the required labour force? Assume two eight-hour shifts per day
and about 250 working days per year. (Hint: apply Little™s Law stating that for
a queueing system in steady state the average length LQ of the queue equals
the average arrival rate » times the average waiting time TW , LQ = »TW .)


Table 5.21 Width of the sections generated at the end of
Step 1 of the 3-BP-L heuristic in the McMillan problem.

Width Weight
Section (m) (kg)

1 2.70 281.00
2 2.70 264.50
3 2.70 262.00
4 2.70 194.00
5 2.00 192.50
6 1.40 123.00

Table 5.22 Section allocation to vehicles at the end of
Step 2 of the 3-BP-L heuristic in the McMillan problem.

Section Vehicle

1 1
2 1
3 2
4 2
5 3

5.3 Let d be the daily demand from all orders, lC the average length of a rail car, q
the capacity of a rail car and nC the number of car changes per day. Estimate
the length of rail dock lD needed by a warehouse.
5.4 Show that scheduling an S/R machine can be modelled as a rural postman
problem on a directed graph. The rural postman problem consists of determining
a least-cost route traversing a subset of required arcs of a graph at least once
(see Section 7.6.2 for further details).
5.5 Show that an optimal picker route cannot traverse an aisle (or a portion of an
aisle) more than twice. Illustrate how this property can be used to devise a
dynamic programming algorithm.
5.6 Demonstrate that both the FF and BF heuristics for the 1-BP problem take
O(m log m) steps.
5.7 Devise a branch-and-bound algorithm based on formula (5.26).
5.8 Devise an improved 1-BP lower bound.
5.9 Modify the heuristics for the 1-BP problem for the case where each bin j, j =
1, . . . , n, has a capacity qj and a cost fj . Apply the modi¬ed version of the
BFD algorithm to the following problem. Brocard is a road carrier operating


Table 5.23 List of the parcels to load and corresponding weight
(in kilograms) in the Brocard problem.

Parcel Weight Parcel Weight

1 228 18 170
2 228 19 170
3 228 20 170
4 217 21 170
5 217 22 95
6 217 23 95
7 217 24 95
8 210 25 95
9 210 26 75
10 210 27 75
11 210 28 75
12 195 29 75
13 195 30 75
14 195 31 75
15 170 32 55
16 170 33 55
17 170 34 55

mainly in France and in the Benelux. The vehicle ¬‚eet comprises 14 vans of
capacity equal to 800 kg and 22 vans of capacity equal to 500 kg. The company
has to deliver on behalf of the EU 34 parcels of different sizes from Paris to
Frankfurt (the distance between these cities is 592 km). The characteristics
of the parcels are reported in Table 5.13. As only ¬ve company-owned vans
(all having capacity of 800 kg) will be available on the day of the delivery,
Brocard has decided to hire additional vehicles from a third-party company.
The following additional vehicles will be available:

• two trucks with a capacity of 3 tons each, whose hiring total cost (inclusive
of drivers) is ‚¬1.4 per kilometre;

• one truck with trailer, with a capacity of 3.5 tons, whose hiring total cost
(inclusive of drivers) is ‚¬1.6 per kilometre.

Which trucks should Brocard hire?

5.10 Determine a lower bound on the optimal solution cost in the Brocard problem
by suitably modifying Equation (5.26). Also determine the optimal shipment
decision by solving a suitable modi¬cation of the 1-BP problem.


5.6 Annotated Bibliography
A recent survey on warehouse design and control is:
1. Jeroen P and Van den Berg L 1999 A literature survey on planning and control
of warehousing systems. IIE Transactions 31, 751“762.
An in-depth treatment of warehouse management is:
2. Bartholdi JJ and Hackman ST 2002 Warehouse and Distribution Science.
(Available at http://www.warehouse-science.com.)
A dynamic programming algorithm for the picker routing problem in Section 5.4.2 is
presented in:
3. Ratliff HD and Rosenthal AS 1983 Order picking in a rectangular warehouse:
a solvable case of the travelling salesman problem. Operations Research 31,
A survey of packing problems is:
4. Dowsland KA and Dowsland WB 1992 Packing problems. European Journal
of Operational Research 56, 2“14.
An annotated bibliography on packing problems is:
5. Dyckhoff H, Scheithauer G and Terno J 1997 Cutting and packing. In Annotated
Bibliographies in Combinatorial Optimization (ed. Dell™Amico M, Maf¬oli F
and Martello S). Wiley, Chichester.
For a detailed treatment of 1-BP, Chapter 8 of the following book is recommended:
6. Martello S and Toth P 1990 Knapsack Problems: Algorithms and Computer
Implementations. Wiley, Chichester.
Two recent papers on exact algorithms for two and three-dimensional packing prob-
lems are:
7. Martello S and Vigo D 1998 Exact solution of the two-dimensional ¬nite bin
packing problem. Management Science 44, 388“399.
8. Martello S, Pisinger D and Vigo D 2000 The three-dimensional bin packing
problem. Operations Research 48, 256“267.


Planning and Managing
Long-Haul Freight

6.1 Introduction
Freight transportation plays a fundamental role in every modern supply chain. It
is essential to move raw materials from sources to plants, semi-¬nished products
between factories, and ¬nal goods to customers and retail outlets. As pointed out
in Chapter 1, transportation systems are rather complex organizations which require
considerable human, ¬nancial and material resources. Transportation cost accounts
for a signi¬cant part (often between one-third and two-thirds) of the logistics cost in
several industries.

Players. Several players are involved in freight transportation. Shippers, which
include both producers and brokers, originate the demand for transportation. Carriers,
such as railways, motor carriers and shipping lines, supply transportation services.
Some shippers operate their own transportation ¬‚eet so that they act as a dedicated
carrier. Governments construct and operate several transportation infrastructures, such
as rail facilities, roads, ports and airports, and regulate several aspects of the industry.
This chapter and the next deal with freight transportation planning and management
from a shipper™s or a carrier™s point of view. Strategic planning activities performed
on a regional, national or even international scale, by governments and international
organizations, are beyond the scope of this book.

Long-haul versus short-haul transportation problems. In long-haul freight trans-
portation, goods are moved over relatively long distances, between terminals or other
facilities (plants, warehouses, etc.). Commodities may be transported by truck, rail,
ship or any combination of modes. On the other hand, in short-haul freight transporta-
tion, goods are transported, usually by truck, between pick-up and delivery points

Introduction to Logistics Systems Planning and Control G. Ghiani, G. Laporte and R. Musmanno
© 2004 John Wiley & Sons, Ltd ISBN: 0-470-84916-9 (HB) 0-470-84917-7 (PB)


situated in the same area (e.g. between a warehouse, or a terminal, and a set of cus-
tomers). Such tasks are of short duration (much shorter than a work shift) and vehicle
tours are to be built through a sequence of tasks. Long-haul transportation is examined
in this chapter, while short-haul problems are dealt with in the next chapter.

Classi¬cation of long-haul transportation services. As explained in Chapter 1,
long-haul transportation services can be broadly classi¬ed into two groups, depending
on whether the movement of goods is performed by the shipper or by a public carrier.
In privately operated transportation, freight has to be moved from a restricted number
of origins (e.g. plants and warehouses) to several destinations (e.g. retail locations and
customers). This is the case of private truck ¬‚eet operations and of industrial cargo
shipping. These few-to-many transportation systems are relatively simple to manage
compared to many-to-many systems operated by public carriers. In such systems,
transportation demand is usually made up of several traf¬c classes, each characterized
by an origin, a destination, a commodity class and a freight tonnage. Public carrier
services can be customized or consolidation-based. In customized transportation,
such as TL trucking and tramp cargo shipping, a vehicle serves a single shipper
request at a time. When a shipper calls, a vehicle and a crew are sent to a pick-up
point. Goods are then loaded and the vehicle moves to a delivery point. Finally, the
vehicle is unloaded and the driving team is asked to move empty to a new location
(either a new pick-up point or a staging point). Hence, vehicle routes are built in an on-
going fashion as customer requests arrive. In consolidation-type transportation, such
as LTL trucking and liner cargo shipping, service is not individualized. A vehicle may
therefore move freight of different shippers with possibly different origin“destination
pairs. Carriers establish regular routes, each of which is characterized by a given
frequency. For instance, a route may be a container ship line operated once a month
from Rotterdam (The Netherlands) to Mumbay (India) with an intermediate stop at
Cape Town (South Africa). A consolidation-type transportation system is made up
of a network of terminals connected by physical (e.g. roads or rail tracks) or virtual
(e.g. air or sea lines) links. End-of-line terminals are places where small shipments
are brought (usually by a ¬‚eet of trucks) and consolidated into larger shipments.
Moreover, in end-of-line terminals, incoming consolidated shipments are broken and
delivered to their ¬nal destinations by a ¬‚eet of vans. In breakbulk terminals, freight
traf¬c from several end-of-line terminals is sorted (or classi¬ed) and consolidated.

6.2 Relevant Costs
Before illustrating the main decision problems arising in freight transportation, it is
useful to describe the various motion costs. Motion costs can be classi¬ed as trans-
portation costs and handling costs.

The cost of operating a ¬‚eet. The main costs in operating a ¬‚eet of vehicles are
related to crews™ wages, fuel consumption, vehicle depreciation, maintenance, insur-


ance, administration and occupancy. Wages and insurance are time dependent, fuel
consumption and maintenance are distance dependent, depreciation depends on both
time and distance, while administration and occupancy costs are customarily allocated
as a ¬xed annual charge.

The cost paid by a carrier for transporting a shipment. The cost paid by a carrier
for transporting a shipment is somewhat arbitrary because different shipments usually
share some common costs. For example, in LTL trucking where several shipments
are moved jointly by the same vehicle, it is unclear how much of a trip cost has to
be assigned to each shipment. Similarly, in TL trucking, a shipment cost is not well
de¬ned because of empty trips necessary to move trucks from each delivery point to
the subsequent pick-up point.

The cost paid for hiring a vehicle. Hire charges include, in addition to the costs
paid by the carrier, an undisclosed mark-up.

The cost of a shipment when a public carrier is used. When a shipper uses a
public carrier, the cost for transporting a shipment can be calculated on the basis of
the rates published by the carrier. For customized transportation, the cost of a full load
depends on both the origin and destination of the movement, as well as on the size
and equipment of the vehicle required. For consolidation-based transportation, each
shipment is given a rating (called a class) which depends on the physical character-
istics (weight, density, etc.) of the goods. For example, in North America the railway
classi¬cation includes 31 classes, while the National Motor Freight Classi¬cation
(NMFC) comprises 23 classes. Rates (i.e. the transportation cost per unit of weight)
depend on the origin and the destination of the movement, as well as on the shipment
weight and its class (see Figures 6.1“6.3). Rates are usually reported in tables, or
can be calculated through rating engines available on the Internet. In Table 6.1, the
LTL rates published by a USA carrier for two NMFC classes are shown. Costs often
present discontinuities, as illustrated in Figure 6.4 (cost may decrease by adding extra

Handling costs. Handling costs are incurred when inserting individual items into
a bin (e.g. a pallet or a container), loading the bin onto an outbound vehicle, and
reversing these operations at destination.

6.3 Classi¬cation of Transportation Problems
In principle, managing a transportation system gives rise to several decision problems.
However, the way these issues are addressed is greatly in¬‚uenced by the nature of
the operational constraints. A typical example is the vehicle and crew scheduling
problem, which amounts to ¬nding a least-cost allocation over time of vehicles and
crews to transportation tasks in such a way that rules and regulations on vehicle



Figure 6.1 Transportation rates for parcels.



Figure 6.2 Transportation rates for LTL trucking.



Figure 6.3 Transportation rates for TL trucking.


Table 6.1 LTL rates (dollars per 100 pounds) from New York to Los Angeles published by
the USA National Classi¬cation Committee (classes 55 and 70 correspond to products having
densities higher than 15 and 35 pounds per cubic feet, respectively).

Weight (W ) Class 55 Class 70

W < 500
0 129.57 153.82
W < 1000
500 104.90 124.60
W < 2000
1000 89.43 106.10
W < 5000
2000 75.17 89.24
W < 10 000
5000 64.82 76.95
W < 20 000
10 000 53.13 63.05
W < 30 000
20 000 46.65 55.37
W < 40 000
30 000 40.15 47.67
W 40 000 37.58 44.64


Tabled rates

Real rates

Rate Rate Rate Rate
zone 1 zone 2 zone 3 zone 4


Figure 6.4 Transportation rates for LTL trucking.

maintenance and crew rests are satis¬ed. In air and rail transportation, where regular
lines are usually operated, vehicle and crew scheduling is a tactical problem solved
a few times a year. On the other hand, in TL trucking both vehicles and crews are
allocated to tasks in an on-going fashion as customer requests arrive. As a result,
freight transportation planning and management problems come in a large number
of variants. Some of them are common to all transportation systems, while others are
speci¬c to a transportation mode or to a way of operating the system.

Common decision problems. Common decision problems include, at the strate-
gic level, a broad de¬nition of the operating strategy of the system, the design of
the physical network (if any exists) and the acquisition of expensive resources, such
as airplanes. The tactical level covers the allocation of existing resources (vehicles,


crews, etc.) as well as the purchase of additional capacity to cope with variations in
demand. At the operational level, the focus is on adjusting vehicle and crew sched-
ules in order to take into account last-minute events, such as order modi¬cations,
equipment failures, strikes and unfavourable weather conditions.

Privately operated transportation systems. The decisions to be made are rela-
tively simple. If demand varies over the year, one must determine the optimal mix
between owned and hired vehicles (see Section 6.4). Moreover, on a short-term basis,
decisions have to be made on order consolidation and on shipment scheduling (see
Section 6.7). The objective is usually to minimize total cost while meeting a pre-
established service level.

Consolidation-based transportation systems. At the strategic level, a carrier has
to decide what kind of commodities to transport and which origin“destination pairs to
serve. Moreover, the number of terminals (e.g. crossdocks or railway terminals) to be
used and their locations must be determined. This class of problems may be tackled
by using the methods illustrated in Chapter 3. In addition, the features of the terminals
(shape, number of doors, etc.) have to be determined (see Section 6.8). At the tactical
level, an important decision is the design of the network on which transportation
services will be offered (the service network). This problem consists of determining
the characteristics (frequency, number of intermediate stops, etc.) of the routes to be
operated, the way traf¬c is routed, the operating rules for each terminal, as well as
the repositioning of empty vehicles and containers (see Sections 6.5 and 6.6).

Tailored transportation systems. At the strategic level, one must decide the most
suitable ¬‚eet and the required number of crews. At the tactical level, the price of full-
load trips must be determined. At the operational level, important decisions relate to
the dynamic allocation of resources such as tractors, trailers, containers and crews,
without a full knowledge of future requests. Once a resource is allocated to a request,
it is no longer available for a certain interval. Then, when it becomes available again, it
is usually located in a different place. Therefore, in such settings one must also decide
which requests have to be accepted and which have to be rejected, as well as how the
accepted requests have to be serviced and how idle resources (e.g. idle tractors, empty
trailers and empty containers) have to be repositioned (see Sections 6.9 and 6.10).
A further operational problem is spot pricing, i.e. the pricing of unallocated vehicle
capacity. In both tailored and consolidation-based transportation, a carrier aims at
maximizing the expected pro¬t over a pre-established planning horizon.

6.4 Fleet Composition
When demand varies over the year, carriers usually cover the baseload of demand
through an owned ¬‚eet, while using hired vehicles to cover peak periods. In what
follows, the least-cost mix of owned and hired vehicles is determined under the






Figure 6.5 Fleet composition when demand varies over the year.

assumption that all vehicles are identical. Let n be the number of time periods into
which the time horizon of a year is decomposed (for example, n = 52 if the time
period corresponds to a week); v be the decision variable corresponding to the number
of owned vehicles; vt , t = 1, . . . , n, be the required number of vehicles at time period
t; m be the number of time periods per year in which vt > v. Moreover, let cF and cV
be the ¬xed and variable cost per time period of an owned vehicle, respectively, and
let cH be the cost per time period of hiring a vehicle (clearly, cF + cV < cH ). Then,
the annual transportation cost as a function of the number of owned vehicles is
C(v) = ncF v + cV min(vt , v) + cH (vt ’ v), (6.1)
t:vt >v

where the right-hand side is the sum of the annual ¬xed cost, the annual variable cost
of the owned vehicles and the annual cost of hiring vehicles to cover peak demand.
The minimum annual transportation cost is achieved when the derivative of C(v) with
respect to v is zero. As the two summations in Equation (6.1) are equal to the areas
below and above the line vt = v, respectively (see Figure 6.5), then their derivatives
are equal to m and ’m, respectively. Consequently, C(v) is minimal when

ncF + cV m ’ cH m = 0.

Hence, the optimal ¬‚eet size can be determined by requiring that
m=n . (6.2)
cH ’ cV


Table 6.2 Weekly number of vans used by Fast Courier during 2002.

t vt t vt t vt t vt

1 12 14 18 27 23 40 25
2 15 15 17 28 22 41 25
3 16 16 16 29 24 42 24
4 17 17 14 30 26 43 22
5 17 18 13 31 27 44 22
6 18 19 13 32 28 45 19
7 20 20 14 33 30 46 20
8 20 21 15 34 32 47 18
9 21 22 16 35 32 48 17
10 22 23 17 36 30 49 16
11 24 24 19 37 29 50 16
12 22 25 21 38 28 51 14
13 20 26 22 39 26 52 13

Fast Courier is a USA transportation company located in Wichita (Kansas), spe-
cializing in door-to-door deliveries. The company owns a ¬‚eet of 14 vans and turns
to third parties for hiring vans when service demand exceeds ¬‚eet capacity. In 2002,
the number of vans used weekly for meeting all the transportation demand is reported
in Table 6.2. For 2003, the company has decided to redesign the ¬‚eet composition,
with the aim of reducing the annual transportation cost. Assuming that cF = $350,
cV = $150 and cH = $800, Equation (6.2) gives m = 28. Hence, the number
of owned vehicles is v — = 19, which corresponds to an annual transportation cost
C(v — ) = $606 600. The saving with respect to the previously adopted solution is
$31 850.

6.5 Freight Traf¬c Assignment Problems
Freight traf¬c assignment problems (TAPs) consist of determining a least-cost routing
of goods over a network of transportation services from their origins (e.g. manufactur-
ing plants) to their destinations (e.g. retail outlets). In a sense, the demand allocation
problems illustrated in Chapter 3 are particular freight TAPs. From a mathematical
point of view, TAPs can be cast as NF problems. NF problems include, as special
cases, several remarkable network optimization problems, such as the shortest-path
problem and the transportation problem.

Classi¬cation. TAPs can be classi¬ed as static or dynamic. Static models are suit-
able when the decisions to be made are not affected explicitly by time. They are


formulated on a directed graph (or multigraph) G = (V , A), where the vertex set V
often corresponds to a set of facilities (terminals, plants, warehouses) and the arcs in
the set A represent possible transportation services linking the facilities. Some vertices
represent origins of transportation demand for one or several products, while others
are destinations, or act as a transshipment points. Let K be the set of traf¬c classes (or
simply, commodities). With each arc is associated a cost (possibly dependent on the
amount of freight ¬‚ow on the arc) and a capacity. Cost functions may represent both
monetary costs (see, for example, Figures 6.1“6.3) and congestion effects arising at
In dynamic models, a time dimension is explicitly taken into account by modelling
the transportation services over a given planning horizon through a time-expanded
directed graph. In a time-expanded directed graph, the horizon is divided into a number
of time periods t1 , t2 , . . . , and the physical network (containing terminals and other
material resources) is replicated in each time period. Then, temporal links are added.
A temporal link connecting two representations of the same terminal at two different
time periods may represent freight waiting to be loaded onto an incoming vehicle,
or the time required for freight classi¬cation at the terminal. On the other hand, a
temporal link connecting two representations of different terminals may describe a
transportation service. Further vertices and arcs may be added to model the arrival of
commodities at destinations and impose penalties in case of delays. With each link
may be associated a capacity and a cost, similar to those used in static formulations.
An example of static transportation service network is shown in Figure 6.6, while an
associated time-expanded network is reported in Figure 6.7. In the static network there
are three terminals (A, B, C) and four transportation services operating from A to B,
from B to A, from B to C and from C to A. The travel durations are 2, 2, 1 and 1 days,
respectively. If the planning horizon includes four days, a dynamic representation has
four vertices for each terminal (Ai , i = 1, . . . , 4, describes terminal A at the ith day).
Some arcs (such as (A1 , B3 )) represent transportation services, while others (such as
(B1 , B2 )) describe commodities standing idle at terminals. In addition, there may be
supersinks for some terminals (such as terminal C in Figure 6.7), in which case the
costs on the arcs entering the supersinks re¬‚ect service penalties.

6.5.1 Minimum-cost ¬‚ow formulation
Let O(k), k ∈ K, be the set of origins of commodity k; D(k), k ∈ K, the set of
destinations of commodity k; T (k), k ∈ K, the set of transshipment points with
respect to commodity k; oi , i ∈ O(k), k ∈ K, the supply of commodity k of vertex

i; dik , i ∈ D(k), k ∈ K, the demand of commodity k of vertex i; uij , (i, j ) ∈ A, the
capacity of arc (i, j ) (i.e. the maximum ¬‚ow that arc (i, j ) can carry); uk , (i, j ) ∈
A, k ∈ K, the maximum ¬‚ow of commodity k on arc (i, j ). The variables xij , k

(i, j ) ∈ A, k ∈ K, represent the ¬‚ow of commodity k on arc (i, j ). Moreover, let
Cij (xij ), (i, j ) ∈ A, k ∈ K, be the cost for transporting xij ¬‚ow units of commodity
k k k

k on arc (i, j ).




Figure 6.6 A static representation of a three-terminal transportation system.

A1 B1 C1

Supersink for
terminal C
A2 B2 C2


A3 B3 C3

A4 B4 C4

Figure 6.7 Dynamic network representation of the transportation system
illustrated in Figure 6.6.

In the following, G is assumed to be a strongly connected directed graph. The
extension to the case where G is a multigraph, or a collection of strongly connected
directed subgraphs, is straightforward. A quite general multicommodity minimum-
cost ¬‚ow (MMCF) formulation is as follows:

k k
Cij (xij ) (6.3)
k∈K (i,j )∈A


subject to
oi , if i ∈ O(k),

k k
xij ’ = ’di i ∈ V , k ∈ K,
k , if i ∈ D(k),
xj i

{j ∈V :(i,j )∈A} {j ∈V :(j,i)∈A} if i ∈ T (k),
uk , (i, j ) ∈ A, k ∈ K,
xij (6.5)
(i, j ) ∈ A,
xij uij , (6.6)
(i, j ) ∈ A, k ∈ K.
xij 0,
The objective function (6.3) is the total cost, constraints (6.4) correspond to the
¬‚ow conservation constraints holding at each vertex i ∈ V and for each commodity
k ∈ K. Constraints (6.5) impose that the ¬‚ow of each commodity k ∈ K does not
exceed capacity uk on each arc (i, j ) ∈ A. Constraints (6.6) (bundle constraints)
require that, for each (i, j ) ∈ A, the total ¬‚ow on arc (i, j ) is not greater than the
capacity uij .
It is worth noting that oi , k ∈ K, i ∈ O(k) and dik , k ∈ K, i ∈ D(k), must satisfy

the following conditions:
dik ,
oi = k ∈ K,
i∈O(k) i∈D(k)

otherwise the problem is infeasible.
In the remainder of this section some of the most relevant solution methods for
some special cases of the MMCF problem are illustrated.

6.5.2 Linear single-commodity minimum-cost ¬‚ow problems
The linear single-commodity minimum-cost ¬‚ow (LMCF) model can be formulated
as follows.
cij xij (6.7)
(i,j )∈A
subject to
oi , if i ∈ O,

xij ’ = ’di , if i ∈ D, i ∈ V,
xj i (6.8)

{j ∈V :(i,j )∈A} {j ∈V :(j,i)∈A} if i ∈ T ,

(i, j ) ∈ A,
xij uij , (6.9)
(i, j ) ∈ A.
xij 0, (6.10)


2 i j
oi (or ’di) oj (or ’dj)
’20 10

’20 ’10
1 3


5 4
’40 50

Figure 6.8 A spanning tree (full line arcs) and the associated (infeasible) basic solution
(x12 = ’20, x23 = 10, x45 = 50, x52 = 10, all other variables are equal to 0).

The LMCF model is a structured LP problem and, as such, can be solved through
the simplex algorithm or any other LP procedure. Instead of using a general-purpose
algorithm, it is common to employ a tailored procedure, the (primal) network simplex
algorithm, a specialized version of the classical simplex method, which takes advan-
tage of the particular structure of the coef¬cient matrix associated with constraints
(6.8) (corresponding to the vertex-arc incidence matrix of the directed graph G).
We ¬rst examine the case where there are no capacity constraints (6.9). In such a
case, it is useful to exploit the following characterization of the basic solutions of the
system of equations (6.8), which is stated without proof.

Property. The basic solutions of the system of equations (6.8) have |V | ’ 1 basic
variables. Moreover, each basic solution corresponds to a tree spanning G and vice
In order to ¬nd a basic solution of problem (6.7), (6.8), (6.10) it is therefore suf¬cient
to select a tree spanning G, set to zero the variables associated with the arcs which
are not part of the tree, and then solve the system of linear equations (6.8). The latter
step can be easily accomplished through a substitution method. Of course, the basic
solution associated with a spanning tree is not always feasible, since the nonnegativity
constraints (6.10) may be violated (see Figure 6.8).
The network simplex algorithm has the same structure as the standard simplex
procedure. However, the optimality test and the pivot operations are performed in a
simpli¬ed way.
Step 1. Find an initial basic feasible solution x (0) . Set h = 0.

Step 2. Determine the reduced costs c (h) associated with x (h) .

0, (i, j ) ∈ A, STOP, x (h) is an optimal solution; otherwise choose
Step 3. If cij
a variable xvw such that cvw < 0.
Step 4. Select a variable xpq coming out of the basis, make a pivot in order to sub-
stitute xpq for xvw in the basis; set h = h + 1 and go back to Step 2.
The particular structure of problem (6.7), (6.8), (6.10) and of its dual,
oi πi ’ d i πi
i∈O i∈D
subject to
πi ’ πj (i, j ) ∈ A,
cij ,
enables the execution of Steps 2“4 as follows. At Step 2, the reduced costs can be
computed through the formula:
(h) (h) (h)
= cij ’ πi + πj , (i, j ) ∈ A,
cij (6.11)
where π (h) ∈ R|V | can be determined by requiring that the reduced costs of the basic
variables be zero:
cij = cij ’ πi(h) + πj = 0,
(h) (h) (h)
(i, j ) ∈ A : xij is a basic variable.
(h) (h) (h)
0, (i, j ) ∈ A, then πi ’ πj cij , (i, j ) ∈ A, i.e. solution
At Step 3, if cij
(h) ∈ R|V | , is feasible for the dual problem. Then, x (h) and π (h) are optimal for the
primal and the dual problems, respectively.
On the other hand, if there is a variable xvw whose reduced cost is negative at
iteration h, then arc (v, w) does not belong to the spanning tree associated with
iteration h. It follows that, by adding (v, w) to the tree, a single cycle Ψ is created.
In order to decrease the objective function value as much as possible, the ¬‚ow on arc
(v, w) has to be increased as much as possible while satisfying constraints (6.8) and
Let Ψ + be the set of arcs in Ψ oriented as (v, w), and let Ψ ’ be the set of the arcs
in Ψ oriented in the opposite direction (obviously, Ψ = Ψ + ∪ Ψ ’ ). If the ¬‚ow on arc
(v, w) is increased by t units, then constraints (6.8) require that the ¬‚ow on all arcs
(i, j ) ∈ Ψ + be increased by t units, and the ¬‚ow on all arcs (i, j ) ∈ Ψ ’ be decreased
by the same amount.
The maximum increase of ¬‚ow on (v, w) is therefore equal to the minimum ¬‚ow
on the arcs oriented in the opposite direction as (v, w), i.e.
t= min {xij }.
(i,j )∈Ψ ’

The arc (p, q) ∈ Ψ ’ for which such a condition holds determines which variable
xpq will come out from the basis.
The previous description shows that an iteration of the network simplex algorithm
requires only a few additions and subtractions. As a result, this procedure is much


faster than the standard simplex method and, in addition, does not make rounding
In order to ¬nd a feasible solution (if any exists), the big M method can be used.
A new vertex i0 ∈ T and |V | dummy arcs between vertex i0 and all the other vertices
i ∈ V are introduced. If i ∈ O, then a dummy arc (i, i0 ) is inserted. Otherwise, an arc
(i0 , i) is added. Let A(a) be the set of dummy arcs. With each dummy arc is associated
an arbitrarily large cost M.
The dummy problem is as follows.
cij xij + M xii0 + M xi0 i (6.12)
(i,j )∈A (i,i0 )∈A(a) (i0 ,i)∈A(a)

subject to
oi , if i ∈ O,

xij ’ = ’di , if i ∈ D, i ∈ V ∪ {i0 },
xj i

if i ∈ T ,
{j ∈V :(i,j )∈A∪A(a) } {j ∈V :(j,i)∈A∪A(a) } 0,
(i, j ) ∈ A ∪ A(a) .
xij 0, (6.14)
Of course, the |V | dummy arcs make up a spanning tree of the modi¬ed directed
graph, corresponding to the following basic feasible solution to problem (6.12)“(6.14)
(see Figure 6.9):
xii0 = oi , i ∈ O;
xi0 i = di , i ∈ D;
xi0 i = 0, i ∈ T;
xij = 0, (i, j ) ∈ A.
By solving the dummy problem (6.12)“(6.14), a basic feasible solution to the
original problem (6.7), (6.8), (6.10) is then obtained.

NTN is a Swiss intermodal carrier located in Lausanne. When a customer has to
transport goods between an origin and a destination, NTN supplies it with one or
more empty containers in which the goods can be loaded. Once arrived at destina-
tion, the goods are unloaded and the empty containers have to be transported to the
pick-up points of new customers. As a result, NTN management needs to reallocate
the empty containers periodically (in practice, on a weekly basis). Empty container
transportation is very expensive (its cost is nearly 35% of the total operating cost).
Last 13 May, several empty ISO 20 containers had to be reallocated among the termi-
nals in Amsterdam (The Netherlands), Berlin (Germany), Munich (Germany), Paris


2 i j
oi (or ’di) oj (or ’dj)


’20 ’10
1 3
20 10



40 50

5 4
’40 50

Figure 6.9 Dummy directed graph for the original directed graph in Figure 6.8 (0 is the
dummy vertex. Full line arcs belong to the spanning tree. For each basic variable, the associated
¬‚ow is reported).

cij = cji
i j
’10 2 20
oi (or ’di) oj (or ’dj)
20 55 3 Munich
Paris 4
5 Milan

’10 25

Figure 6.10 Graph representation of the empty container allocation problem.

(France), Milan (Italy), Barcelona (Spain) and Madrid (Spain). The number of empty
containers available or demanded at the various terminals is reported, along with
transportation costs (in euros/container), in Figure 6.10.
The problem can be formulated as follows.


i j
xij 2
’10 1
oi (or ’di) oj (or ’dj) 10

3 50
20 4


10 ’50

’10 7

Figure 6.11 Optimal solution for the NTN empty container allocation problem. (Full line
arcs belong to the spanning tree. For each basic variable, the associated ¬‚ow is reported. The
optimal cost is equal to ‚¬3900.)

30x12 + 30x21 + 40x13 + 40x31 + 20x14 + 20x41 + 30x23 + 30x32
+ 55x34 + 55x43 + 30x35 + 30x53 + 30x45 + 30x54 + 50x46
+ 50x64 + 70x47 + 70x74 + 30x56 + 30x65 + 25x67 + 25x76

subject to

x12 + x13 + x14 ’ x21 ’ x31 ’ x41 = ’10,
x21 + x23 ’ x12 ’ x32 = 20,
x31 + x32 + x34 + x35 ’ x13 ’ x23 ’ x43 ’ x53 = 50,
x41 + x43 + x45 + x46 + x47 ’ x14 ’ x34 ’ x54 ’ x64 ’ x74 = 20,
x53 + x54 + x56 ’ x35 ’ x45 ’ x65 = ’50,
x64 + x65 + x67 ’ x46 ’ x56 ’ x76 = ’20,
x74 + x76 ’ x47 ’ x67 = ’10,
x12 , x21 , x13 , x31 , x14 , x41 , x23 , x32 , x34 , x43 , x35 ,
x53 , x45 , x54 , x46 , x64 , x47 , x74 , x56 , x65 , x67 , x76 0.
Using the network simplex method, the optimal solution illustrated in Figure 6.11
is obtained.

The above procedure can be easily adapted to the case of capacitated arcs. To this


Table 6.3 Transportation costs (in euros) per item from the warehouses to
the sales districts in the Boscheim problem.

London Birmingham Leeds Edinburgh

Bristol 9.6 7.0 15.2 28.5
Middlesborough 19.5 13.3 5.0 11.3

purpose, constraints (6.9) are rewritten by introducing auxiliary variables γij 0:
xij + γij = uij , (i, j ) ∈ A.
If the variable xij is equal to uij , then the associated auxiliary variable γij takes the
value zero and is therefore out of the basis (if the solution is not degenerate). Based
on this observation, the following optimality conditions can be derived (the proof is
omitted for the sake of brevity).
Theorem 6.1. A basic feasible solution x (h) is optimal for problem (6.7)“(6.10) if,
for each nonbasic variable xij , (i, j ) ∈ A, the following conditions hold,
(h) (h)
xij = 0, if cij 0,
(h) (h)
xij = uij , if cij 0,
where cij are the reduced costs de¬ned by (6.11).
Let x (h) be the basic feasible solution at iteration h of the network simplex method
(for simplicity, x (h) is assumed to be nondegenerate). If the value of a nonbasic
variable xij , (i, j ) ∈ A is increased, the objective function value increases if the
(h) (h)
reduced cost cij is negative. On the other hand, if xij = uij , then a decrease in the
objective function value is obtained if the reduced cost cij is positive.
Let xvw be the variable entering the basis at iteration h (Step 4). If xvw = 0, then
cvw < 0 and arc (v, w) ∈ A is not part of the spanning tree associated with x (h) . By
adding the arc (v, w) to the tree, a single cycle Ψ is formed. In the new basic feasible
solution, the variable xvw will take a value t equal to
(h) (h)
t = min min {uij ’ xij }, min {xij } . (6.15)
(i,j )∈Ψ + (i,j )∈Ψ ’
Let (p, q) be the arc outgoing the basis according to (6.15). Then, xpq = upq ,
if (p, q) ∈ Ψ + , or xpq = 0, if (p, q) ∈ Ψ ’ . Observe that the outgoing arc (p, q)

may be the same as the outgoing (v, w) if t = uvw .

Boscheim is a German company manufacturing electronics convenience goods. Its
VCR-12 video recorder is speci¬cally designed for the British market. The VCR-
12 is assembled in a plant near Rotterdam (The Netherlands), then stocked in two


warehouses located in Bristol and Middlesborough and ¬nally transported to the
retailer outlets. The British market is divided into four sales districts whose centres of
gravity are in London, Birmingham, Leeds and Edinburgh. Yearly demands amount
to 90 000, 80 000, 50 000 and 70 000 items, respectively. The transportation costs
per item from the assembly plant of Rotterdam to the warehouses of Bristol and
Middlesborough are ‚¬24.5 and ‚¬26.0, respectively, whereas the transportation costs
per item from the warehouses to the sales districts are reported in Table 6.3. Both
warehouses have an estimated capacity of 15 000 items and are supplied 10 times a
year. Consequently their maximum yearly throughput is 150 000 items.
The annual minimum cost distribution plan can be obtained by solving the following
LMCF problem (see Figure 6.12).
24.5x12 + 26.0x13 + 9.6x24 + 7.0x25 + 15.2x26
+ 28.5x27 + 19.5x34 + 13.3x35 + 5.0x36 + 11.3x37
subject to
x12 + x13 = 290 000,
x24 + x25 + x26 + x27 ’ x12 = 0,
x34 + x35 + x36 + x37 ’ x13 = 0,
’x24 ’ x34 = ’90 000,
’x25 ’ x35 = ’80 000,
’x26 ’ x36 = ’50 000,
’x27 ’ x37 = ’70 000,

x12 150 000,
x13 150 000,
x12 , x13 , x24 , x25 , x26 , x27 , x34 , x35 , x36 , x37 0.
By using the network simplex method, the optimal solution is determined:
— — — —
x12 = 150 000, x13 = 140 000, x24 = 90 000, x25 = 60 000,
— — —
x35 = 20 000, x36 = 50 000, x37 = 70 000
(as usual, only nonzero variables are reported). It is worth noting that the district of
London will be entirely served by the warehouse of Bristol, while the sales districts
of Leeds and Edinburgh will be served by the Middlesborough warehouse. The sales
district of Birmingham is supplied by both the warehouse of Bristol (75%) and the
warehouse of Middlesborough (25%). The total transportation cost is ‚¬9 906 000 per


i j
1 290 000
oi (or ’di) oj (or ’dj)

24.5 26.0

Bristol 2 0 Middlesborough 3 0
28.5 19.5

9.6 7.0 5.0 11.3
15.2 13.3

’90 000 ’80 000 ’50 000 ’70 000
4 5 6 7

London Birmingham Leeds Edinburgh

Figure 6.12 Graph representation of the Boscheim problem.

6.5.3 Linear multicommodity minimum-cost ¬‚ow problems
The linear multicommodity minimum-cost ¬‚ow (LMMCF) problem can be formu-
lated as the following LP model.
cij xij
k∈K (i,j )∈A

subject to
oi , if i ∈ O(k),

k k
’ = ’dik , i ∈ V , k ∈ K,
if i ∈ D(k),
xij xj i

{j ∈V :(i,j )∈A} {j ∈V :(j,i)∈A} if i ∈ T (k),
uk , (i, j ) ∈ A, k ∈ K,
xij ij
(i, j ) ∈ A,
xij uij , (6.16)
(i, j ) ∈ A, k ∈ K.
xij 0,

The LMMCF problem can be solved ef¬ciently through a tailored Lagrangian pro-
cedure. Let »ij ( 0) be the multipliers attached to constraints (6.16). The Lagrangian
relaxation of the LMMCF problem is as follows.
kk k
cij xij + xij ’ uij
»ij (6.17)
k∈K (i,j )∈A k∈K
(i,j )∈A


subject to
oi , if i ∈ O(k),

k k
xij ’ = ’dik , if i ∈ D(k), i ∈ V , k ∈ K,
xj i

{j ∈V :(i,j )∈A} {j ∈V :(j,i)∈A} if i ∈ T (k),
uk , (i, j ) ∈ A, k ∈ K,
xij (6.19)
(i, j ) ∈ A, k ∈ K.
xij 0, (6.20)

The relaxation (6.17)“(6.20), referred in the sequel to as the r-LMMCF problem, is
made up of |K| independent single-commodity minimum-cost ¬‚ow problems, since
the sum (i,j )∈A »ij uij in the objective function (6.17) is constant for a given set
of multipliers »ij , (i, j ) ∈ A. Therefore, the kth LMCF subproblem, k ∈ K, is as
k k
(cij + »ij )xij (6.21)
(i,j )∈A

subject to
oi , if i ∈ O(k),

k k
xij ’ = ’di i ∈ V,
k , if i ∈ D(k),
xj i (6.22)

{j ∈V :(i,j )∈A} {j ∈V :(j,i)∈A} if i ∈ T (k),
uk , (i, j ) ∈ A,
xij (6.23)
(i, j ) ∈ A,
xij 0, (6.24)

LMCF (»), k ∈ K, be
can be solved through the network simplex algorithm. Let LBk
the optimal objective function value of the kth subproblem (6.21)“(6.24) and let
LBr-LMMCF (») be the lower bound provided by solving the r-LMMCF problem. For
a given set of multipliers, LBr-LMMCF (») is given by

LBr-LMMCF (») = LMCF (») ’ »ij uij .
k∈K (i,j )∈A

Of course, LBr-LMMCF (») varies as the multiplier » changes. The Lagrangian relax-
ation attaining the maximum lower bound value LBr-LMMCF (») as » varies is called
the dual Lagrangian relaxation. The following property follows from LP theory.

Property. The lower bound provided by the dual Lagrangian relaxation is equal to
the optimal objective function value of the LMMCF model, i.e.

max{LBr-LMMCF (»)} = zLMMCF .


Moreover, the dual Lagrangian multipliers »— , (i, j ) ∈ A, are equal to the optimal

dual variables πij , (i, j ) ∈ A, associated with the relaxed constraints (6.16).
In order to compute the dual Lagrangian multipliers, or at least a set of multipliers
associated with a ˜good™ lower bound, the classical subgradient procedure, already
illustrated in Chapter 3, can be used.
Step 0. (Initialization). Let H be a pre-established maximum number of subgradient
iterations. Set LB = ’∞, h = 1 and »ij = 0, (i, j ) ∈ A. Set UB equal to the
cost of the best feasible solution if any is available, or set UB = ∞, otherwise.
Step 1. (Calculation of a new lower bound). Solve the r-LMMCF problem using »(h)
as a vector of multipliers. If LBr-LMMCF (»(h) ) > LB, set LB = LBr-LMMCF (»(h) ).
Step 2. (Checking the stopping criterion). If solution xij , (i, j ) ∈ A, k ∈ K, of
the r-LMMCF problem satis¬es the relaxed constraints (6.16), and

»(h) k,(h)
’ uij = 0, (i, j ) ∈ A,
— k,(h)
STOP, the solution found is optimal (zLMMCF = LB). If xij , (i, j ) ∈ A, k ∈ K,
satis¬es the relaxed constraints (6.16), update UB if necessary. If UB = LB, STOP,
the feasible solution attaining UB is proved to be optimal. If h = H , STOP, LB

represents the best lower bound available for zLMMCF .
Step 3. (Updating the multipliers). Determine, for each (i, j ) ∈ A, the subgradient
of the relaxed constraint:
(h) k,(h)
sij = ’ uij , (i, j ) ∈ A.

Then set
(h+1) (h) (h)
= max(0, »ij + β (h) sij ), (i, j ) ∈ A,
where β (h) is a suitable coef¬cient
β (h) = (i, j ) ∈ A,
, (6.25)
with ± arbitrarily chosen in the interval (0, 2]. Alternatively, if a feasible solution
the problem is available, set
±(UB ’ LBLMCF (»(h) ))
β (h) = (i, j ) ∈ A,
(i,j )∈A (sij )

with UB equal to the objective function value of the best feasible solution available.
Set h = h + 1 and go back to Step 1.

The subgradient method converges to zLMMCF provided that the variations of the
multipliers are ˜small enough™ (this assumption is satis¬ed if, for example, Equation
(6.25) is used). However, this assumption makes the algorithm very slow.


Demand (in tons) dkt , k = 1, 2, t = 1, 2, in the Exofruit problem.
Table 6.4

t =1 t =2

k=1 18 000 18 000
k=2 12 000 14 000

Maximum amounts available (in tons) okt , k = 1, 2, t = 1, 2,
Table 6.5
in the Exofruit problem.

t =1 t =2

k=1 26 000 20 000
k=2 14 000 13 000

Purchase prices (in euros/ton) pkt , k = 1, 2, t = 1, 2, in the Exofruit problem.
Table 6.6


. 9
( 15)