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 .)

TLFeBOOK

196 DESIGNING AND OPERATING A WAREHOUSE

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

TLFeBOOK

DESIGNING AND OPERATING A WAREHOUSE 197

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.

TLFeBOOK

198 DESIGNING AND OPERATING A WAREHOUSE

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,

507“521.

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.

TLFeBOOK

6

Planning and Managing

Long-Haul Freight

Transportation

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)

TLFeBOOK

200 LONG-HAUL FREIGHT TRANSPORTATION

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-

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 201

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

weight).

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

TLFeBOOK

202 LONG-HAUL FREIGHT TRANSPORTATION

Cost

Weight

Figure 6.1 Transportation rates for parcels.

Cost

Weight

Figure 6.2 Transportation rates for LTL trucking.

Cost

Weight

Figure 6.3 Transportation rates for TL trucking.

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 203

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

Cost

Tabled rates

Real rates

Rate Rate Rate Rate

zone 1 zone 2 zone 3 zone 4

Weight

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,

TLFeBOOK

204 LONG-HAUL FREIGHT TRANSPORTATION

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

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 205

vt

Hired

vehicles

v

Owned

vehicles

t

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

n

C(v) = ncF v + cV min(vt , v) + cH (vt ’ v), (6.1)

t:vt >v

t=1

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

cF

m=n . (6.2)

cH ’ cV

TLFeBOOK

206 LONG-HAUL FREIGHT TRANSPORTATION

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

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 207

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

terminals.

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

k

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 ) ∈

ij

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 ).

TLFeBOOK

208 LONG-HAUL FREIGHT TRANSPORTATION

A

B C

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

A1 B1 C1

Supersink for

terminal C

A2 B2 C2

Time

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:

Minimize

k k

Cij (xij ) (6.3)

k∈K (i,j )∈A

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 209

subject to

±

oi , if i ∈ O(k),

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),

0,

(6.4)

k

uk , (i, j ) ∈ A, k ∈ K,

xij (6.5)

ij

k

(i, j ) ∈ A,

xij uij , (6.6)

k∈K

k

(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)

ij

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

k

the following conditions:

k

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.

Minimize

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 ,

0,

(i, j ) ∈ A,

xij uij , (6.9)

(i, j ) ∈ A.

xij 0, (6.10)

TLFeBOOK

210 LONG-HAUL FREIGHT TRANSPORTATION

20

2 i j

xij

oi (or ’di) oj (or ’dj)

’20 10

’20 ’10

1 3

10

5 4

50

’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

versa.

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) .

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 211

(h)

0, (i, j ) ∈ A, STOP, x (h) is an optimal solution; otherwise choose

Step 3. If cij

(h)

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,

Maximize

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

(6.10).

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.

(h)

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

TLFeBOOK

212 LONG-HAUL FREIGHT TRANSPORTATION

faster than the standard simplex method and, in addition, does not make rounding

errors.

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.

Minimize

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,

(6.13)

(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):

(0)

xii0 = oi , i ∈ O;

(0)

xi0 i = di , i ∈ D;

(0)

xi0 i = 0, i ∈ T;

(0)

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

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 213

20

2 i j

(0)

xij

oi (or ’di) oj (or ’dj)

20

’20 ’10

1 3

20 10

0

0

40 50

5 4

50

’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).

Berlin

Amsterdam

cij = cji

i j

30

’10 2 20

1

oi (or ’di) oj (or ’dj)

40

30

20

20 55 3 Munich

Paris 4

50

30

30

70

5 Milan

50

’50

30

6

’20

7

’10 25

Barcelona

Madrid

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.

TLFeBOOK

214 LONG-HAUL FREIGHT TRANSPORTATION

20

i j

*

xij 2

’10 1

oi (or ’di) oj (or ’dj) 10

10

3 50

20 4

60

10 ’50

5

10

10

6

’10 7

’20

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.)

Minimize

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

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 215

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,

(h)

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,

(h)

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

(h)

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

(h)

objective function value is obtained if the reduced cost cij is positive.

(h)

Let xvw be the variable entering the basis at iteration h (Step 4). If xvw = 0, then

(h)

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 )∈Ψ ’

(h+1)

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)

(h+1)

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

TLFeBOOK

216 LONG-HAUL FREIGHT TRANSPORTATION

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).

Minimize

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

year.

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 217

Rotterdam

i j

cij

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.

Minimize

kk

cij xij

k∈K (i,j )∈A

subject to

±

oi , if i ∈ O(k),

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),

0,

k

uk , (i, j ) ∈ A, k ∈ K,

xij ij

k

(i, j ) ∈ A,

xij uij , (6.16)

k∈K

k

(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.

Minimize

kk k

cij xij + xij ’ uij

»ij (6.17)

k∈K (i,j )∈A k∈K

(i,j )∈A

TLFeBOOK

218 LONG-HAUL FREIGHT TRANSPORTATION

subject to

±

oi , if i ∈ O(k),

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),

0,

(6.18)

k

uk , (i, j ) ∈ A, k ∈ K,

xij (6.19)

ij

k

(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

follows.

Minimize

k k

(cij + »ij )xij (6.21)

(i,j )∈A

subject to

±

oi , if i ∈ O(k),

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),

0,

k

uk , (i, j ) ∈ A,

xij (6.23)

ij

k

(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

LBk

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 .

»0

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 219

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

ij

—

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

(h)

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) ).

k,(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,

xij

ij

k∈K

— 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.

xij

k∈K

Then set

(h+1) (h) (h)

= max(0, »ij + β (h) sij ), (i, j ) ∈ A,

»ij

where β (h) is a suitable coef¬cient

±

β (h) = (i, j ) ∈ A,

, (6.25)

h

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,

,

(h)

2

(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.

TLFeBOOK

220 LONG-HAUL FREIGHT TRANSPORTATION

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