t =1 t =2

k=1 500 700

k=2 600 400

k,(h)

If the solution xij , (i, j ) ∈ A, k ∈ K, of the r-LMMCF problem satis¬es the

relaxed constraints (6.16), it is not necessarily the optimal solution for the LMMCF

problem. A suf¬cient (but not necessary) condition for it to be optimal is given by the

complementary slackness conditions:

(h) k,(h)

’ uij = 0, (i, j ) ∈ A.

»ij xij (6.26)

k∈K

k,(h)

If relations (6.26) are not satis¬ed, then the feasible solution xij , (i, j ) ∈ A,

k ∈ K, is a simply a candidate optimal solution.

If h = H , the solution attaining LB could be infeasible for the LMMCF, or, if

feasible, may not satisfy the complementarity slackness conditions. In any case, if

subproblems (6.21)“(6.24) are solved by means of the network simplex method, a

basic (feasible or infeasible) solution for the LMMCF model is available. In fact, the

basic variables of the |K| subproblems (6.21)“(6.24) make up a basis of the LMMCF

problem. The basic solution obtained this way can be used as the starting solution for

the primal or dual simplex method depending on whether the solution is feasible for

the LMMCF problem or not. If initialized this way, the simplex method is particularly

ef¬cient since the initial basic solution provided by the subgradient algorithm is a good

approximation of the optimal solution.

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 221

1 5

3

4

2 6

Figure 6.13 Graph representation of the Exofruit problem.

Exofruit Ltd imports to the EU countries several varieties of tropical fruits, mainly

coming from Northern Africa, Mozambique and Central America. The company pur-

chases the products directly from farmers and transports them by sea to its warehouses

in Marseille (France). The goods are then stored in refrigerated cells or at room tem-

perature. As purchase and selling prices varies during the year, Exofruit has to decide

when and how much to buy in order to satisfy demand over the year. The problem

can be modelled as an LMMCF problem. In what follows, a simpli¬ed version of the

problem is examined. It is assumed that a single source exists, products are grouped

into two homogeneous groups (macro-products), and the planning horizon is divided

into two semesters. Let dkt and okt , k = 1, 2, t = 1, 2, be the demand and the

maximum amount (in tons) of macro-product k available in semester t, respectively

(see Tables 6.4 and 6.5). Purchase prices (in euros/tons) pkt , k = 1, 2, t = 1, 2, of

macro-product k in semester t are reported in Table 6.6.

The transportation cost v of 1 ton of a macro-product is equal to ‚¬100, while

the stocking cost w of 1 ton of a macro-product is ‚¬100 per semester. Finally, the

maximum quantity q of goods that can be stored in a semester is 8000 tons.

The problem can be formulated as an LMMCF problem with two commodities

(one for each macro-product) on the directed graph shown in Figure 6.13. In such a

representation,

• vertices 1 and 5 represent the source and the destination of macro-product 1,

respectively;

• vertices 2 and 6 represent the source and the destination of macro-product 2,

respectively;

• vertices 3 and 4 represent the warehouse in the ¬rst and in the second semester,

respectively;

TLFeBOOK

222 LONG-HAUL FREIGHT TRANSPORTATION

• arc (1,3) has a cost per unit of ¬‚ow equal to c13 = p11 + v = 600 euros/ton

1

and a capacity equal to u13 = o11 = 26 000 tons;

• arc (1,4) has a cost per unit of ¬‚ow equal to c14 = p12 + v = 800 euros/ton

1

and a capacity equal to u14 = o12 = 20 000 tons;

• arc (2,3) has a cost per unit of ¬‚ow equal to c23 = p21 + v = 700 euros/ton

2

and a capacity equal to u23 = o21 = 14 000 tons;

• arc (2,4) has a cost per unit of ¬‚ow equal to c24 = p22 + v = 500 euros/ton

2

and a capacity equal to u24 = o22 = 13 000 tons;

• arc (3,4) represents the storage of goods for a semester and is therefore associ-

ated with a cost per unit of ¬‚ow equal to c34 = c34 = w = 100 euros/ton and

1 2

a capacity of u34 = q = 8000 tons;

• arc (3,5) has a zero cost per unit of ¬‚ow and a capacity equal to u35 = d11 =

18 000 tons;

• arc (4,5) has a zero cost per unit of ¬‚ow and a capacity equal to u45 = d12 =

18 000 tons;

• arc (3,6) has a zero cost per unit of ¬‚ow and a capacity equal to u36 = d21 =

12 000 tons;

• arc (4,6) has a zero cost per unit of ¬‚ow and a capacity equal to u46 = d22 =

14 000 tons.

The problem is formulated as follows.

Minimize

600x13 + 800x14 + 100x34 + 700x23 + 500x24 + 100x34

1 1 1 2 2 2

subject to

x35 + x45 = 36 000,

1 1

x13 ’ x34 ’ x35 = 0,

1 1 1

x14 + x34 ’ x45 = 0,

1 1 1

x36 + x46 = 26 000,

2 2

x23 ’ x36 ’ x34 = 0,

2 2 2

x24 + x34 ’ x46 = 0,

2 2 2

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 223

1

x13 26 000,

1

x14 20 000,

1

x35 18 000,

1

x45 18 000,

2

x23 14 000,

2

x24 13 000,

2

x36 12 000,

2

x46 14 000,

x34 + x34

1 2

8000,

1 1 1 1 1 2 2 2 2 2

x13 , x14 , x34 , x35 , x45 , x23 , x24 , x34 , x36 , x46 0.

By relaxing in a Lagrangian fashion the constraint x34 + x34 8000 with a multi-

1 2

plier »34 , the problem decomposes into two single-commodity linear minimum-cost

(0)

¬‚ow problems. By initializing the subgradient algorithm with »34 = 0 and using the

updating formula (6.25) with ± = 0.05, the procedure provides, after 20 iterations,

(20)

a lower bound LB = ‚¬40 197 387 (»34 = 99.887). At the end, the procedure con-

verges to »— = 100, which corresponds to an optimal objective value zLMMCF equal

—

34

to ‚¬40 200 000. Subproblem k = 1 has, for »— , two optimal basic solutions

34

1,— 1,— 1,— 1,— 1,—

x13 = x14 = x35 = x45 = 18 000, x34 = 0

and

1,— 1,— 1,— 1,— 1,—

x13 = 26 000, x14 = 10 000, x34 = 8000, x35 = 18 000, x45 = 18 000,

while subproblem k = 2 has a single optimal solution equal to

2,— 2,— 2,— 2,— 2,—

x23 = x24 = 13 000, x34 = 1000, x36 = 12 000, x46 = 14 000.

By combining the two partial solutions, the following two solutions are obtained:

1,— 1,— 1,— 1,— 1,—

x13 = x14 = x35 = x45 = 18 000, x34 = 0,

2,— 2,— 2,— 2,— 2,—

x23 = x24 = 13 000, x34 = 1000, x36 = 12 000, x46 = 14 000

and

1,— 1,— 1,—

x13 = 26 000, x14 = 10 000, x34 = 8000,

1,— 1,— 2,— 2,—

x35 = 18 000, x45 = 18 000, x23 = x24 = 13 000,

2,— 2,— 2,—

x34 = 1000, x36 = 12 000, x46 = 14 000.

The former solution has an objective function value equal to ‚¬41 000 000 and is

feasible, but does not satisfy the complementarity slackness conditions (6.26), while

TLFeBOOK

224 LONG-HAUL FREIGHT TRANSPORTATION

End-of-line terminal End-of-line terminal

B C

Break-bulk terminal D

A C A B

End-of-line terminal End-of-line terminal End-of-line terminal End-of-line terminal

Figure 6.14 Two alternative service networks for a

three end-of-line terminal transportation system.

the latter is infeasible. It can be easy veri¬ed that the optimal solution is a convex

combination of the two previous solutions and corresponds to

1,— 1,— 1,— 1,— 1,—

x13 = 25 000, x14 = 11 000, x34 = 7000, x35 = 18 000, x45 = 18 000,

2,— 2,— 2,— 2,— 2,—

x23 = 12 000, x24 = 13 000, x34 = 1000, x36 = 12 000, x46 = 14 000.

6.6 Service Network Design Problems

The design of a network of transportation services is a tactical/operational decision

particularly relevant to consolidation-based carriers. Given a set of terminals, the

service network design problem consists of deciding on the characteristics (frequency,

number of intermediate stops, etc.) of the routes to be operated, the traf¬c assignment

along these routes, the operating rules at each terminal, and possibly the relocation

of empty vehicles and containers. The objective is the minimization of a generalized

cost taking into account a combination of carrier™s operating costs and customers™

expectations. Figure 6.14 shows two alternative service networks for a three-terminal

transportation system in which it is assumed that each arc is associated with a line

operated once a day. In the former network, each terminal is connected directly to

every other terminal (so that each shipment takes one day) but this comes at the

expense of a higher operating cost. In the latter network, operating costs are lower

but the transportation between certain origin“destination pairs may require two days

(unless all lines are synchronized).

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 225

Classi¬cation. Service network design models can be classi¬ed into two main cate-

gories: frequency-based and dynamic models. In frequency-based models the decision

variables express how often each transportation service is operated in a given time

horizon, while in dynamic models a time-expanded network is used to provide a more

detailed description of the system. In the remainder of this chapter, the focus is on basic

network design problems (namely, ¬xed-charge network design (FCND) problems)

and on dynamic service network design models. For a description of frequency-based

models, the reader should consult the references listed at the end of the chapter.

6.6.1 Fixed-charge network design models

FCND problems may be viewed as a generalization of NF problems in which a ¬xed

cost fij has to be paid for using each arc (i, j ) ∈ A. Therefore, FCND problems

amount to determining

• which arcs have to be employed;

• how to transport the commodities on the selected arcs.

Let xij , (i, j ) ∈ A, k ∈ K, be the ¬‚ow of commodity k on arc (i, j ), and let yij ,

k

(i, j ) ∈ A, be a binary design variable, equal to 1 if arc (i, j ) is used, 0 otherwise. A

quite general formulation of the FCND problem is as follows.

Minimize

k k

Cij (xij ) + fij yij (6.27)

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

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

k

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

xij (6.29)

ij

k

(i, j ) ∈ A,

xij uij yij , (6.30)

k∈K

k

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

xij 0,

yij ∈ {0, 1}, (i, j ) ∈ A.

The objective function (6.27) is the total transportation cost. Constraints (6.28)

correspond to the ¬‚ow conservation constraints holding at each vertex i ∈ V and for

each commodity k ∈ K; the constraints (6.29) impose that the ¬‚ow of each commodity

k ∈ K does not exceed capacity uk on each arc (i, j ) ∈ A; the constraints (6.30)

ij

(bundle constraints) require that, for each (i, j ) ∈ A, the total ¬‚ow on arc (i, j ) is

zero if the arc is not used, or not greater than capacity uij , otherwise.

TLFeBOOK

226 LONG-HAUL FREIGHT TRANSPORTATION

In practice, some side constraints may be needed to represent economic and topo-

logical restrictions. For example, when several links share a common resource, the

following budget constraint has to be added to the FCND model,

hij yij H,

(i,j )∈A

where hij , (i, j ) ∈ A, is the consumption of resource made by arc (i, j ) ∈ A, and H

is the total amount of resource available.

6.6.2 The linear ¬xed-charge network design model

The linear ¬xed-charge network design (LFCND) problem is a particular FCND

k

problem in which the transportation costs per ¬‚ow unit cij are constant (hence the

objective function (6.27) is linear).

More formally, the LFCND model can be formulated as follows.

Minimize

kk

cij xij + fij yij

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

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,

k

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

xij ij

k

(i, j ) ∈ A,

xij uij yij ,

k∈K

k

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

xij 0,

yij ∈ {0, 1}, (i, j ) ∈ A.

The LFCND problem is NP-hard and branch-and-bound algorithms can hardly

solve instances with a few hundreds of arcs and tens of commodities. Since instances

arising in applications are much larger, heuristics are often used. To evaluate the

quality of the solutions provided by heuristics, it is useful, as already observed in

—

Chapter 3, to compute lower bounds on the optimal objective function value zLFCND . In

the following, two distinct continuous relaxations and a simple heuristic are illustrated.

The weak continuous relaxation

The weak continuous relaxation is obtained by relaxing the integrality requirement

on the design variables.

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 227

Minimize

kk

cij xij + fij yij (6.31)

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

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

k

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

xij (6.33)

ij

k

(i, j ) ∈ A,

xij uij yij , (6.34)

k∈K

k

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

xij 0, (6.35)

(i, j ) ∈ A.

yij

0 1, (6.36)

It is easy to verify that every optimal solution of such a relaxation satis¬es each

constraint (6.34) as an equality since ¬xed costs fij , (i, j ) ∈ A, are nonnegative.

Therefore, design variables yij , (i, j ) ∈ A, can be expressed as a function of ¬‚ow

variables xij , (i, j ) ∈ A, k ∈ K:

k

k

xij

k∈K

yij = (i, j ) ∈ A.

,

uij

Hence, the constraints (6.36) can be replaced by the following conditions:

k

(i, j ) ∈ A.

xij uij ,

k∈K

The relaxed problem (6.31)“(6.36) can be therefore equivalently formulated as

follows.

Minimize

fij k

k

cij + x (6.37)

uij ij

k∈K (i,j )∈A

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

TLFeBOOK

228 LONG-HAUL FREIGHT TRANSPORTATION

k

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

xij (6.39)

ij

k

(i, j ) ∈ A,

xij uij , (6.40)

k∈K

k

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

xij 0, (6.41)

The model (6.37)“(6.41) is a minimum-cost ¬‚ow problem with |K| commodities.

Let LB— be the lower bound on zLFCND given by the optimal objective function value

—

w

of the above relaxation.

The strong continuous relaxation

The strong continuous relaxation is obtained by adding the following valid inequalities

k

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

xij (6.42)

ij

to the LFCND model and removing the integrality constraints on the design variables

yij , (i, j ) ∈ A. Taking into account the fact that constraints (6.6.2) are dominated by

constraints (6.42), and can therefore eliminated, the relaxed problem is as follows.

Minimize

kk

cij xij + fij yij (6.43)

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

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

k

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

xij (6.45)

ij

k

(i, j ) ∈ A,

xij uij yij , (6.46)

k∈K

k

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

xij 0, (6.47)

(i, j ) ∈ A.

yij

0 1, (6.48)

Let LB— be the lower bound on zLFCND given by the optimal objective function

—

s

value of the relaxation (6.43)“(6.48). Such problem has no special structure and can

therefore be solved by using any general purpose LP algorithm. By comparing the

two continuous relaxations, it is clear that LB— is always better than, or at least equal

s

— , i.e.

to, LBw

LB— LB— .

s w

This observation leads us to label the former relaxation as weak, and the latter as

strong. Computational experiments have shown that LB— can be as much as 40%

w

lower than LB— .

s

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 229

Table 6.7 Forecasted transportation demand of refrigerated goods

(pallets per day) in the FHL problem.

Bologna Genoa Milan Padua

Bologna ” 3 8 2

Genoa 0 ” 1 2

Milan 4 2 ” 1

Padua 3 1 1 ”

Table 6.8 Forecasted transportation demand of goods at room temperature

(pallets per day) in the FHL problem.

Bologna Genoa Milan Padua

Bologna ” 3 4 2

Genoa 1 ” 1 0

Milan 6 2 ” 2

Padua 1 1 1 ”

FHL is an Austrian fast carrier located in Lienz, whose core business is the trans-

portation of small-sized and high-valued refrigerated goods (such as chemical reagents

used by hospitals and laboratories). Goods are picked up from manufacturers™ ware-

houses by small vans and carried to the nearest transportation terminal operated by

the carrier. These goods are packed onto pallets and transported to destination termi-

nals by means of large trucks. Then, the merchandise is unloaded and delivered to

customers by small vans (usually the same vans employed for pick-up). In order to

make capital investment in equipment as low as possible, FHL makes use of one-way

rentals of trucks. Recently, the company has decided to enter the Italian fast parcel

transportation market by opening four terminals in the cities of Bologna, Genoa,

Padua and Milan. This choice made necessary a complete revision of the service net-

work. The decision was complicated by the need to transport the refrigerated goods

by special vehicles equipped with refrigerators, while parcels can be transported by

any vehicle. The forecasted daily average demand of the two kinds of products in the

next semester is reported in Tables 6.7 and 6.8.

Between each pair of terminals, the company can operate one or more lines (see

Figure 6.15). Vehicles are of two types:

• trucks with refrigerated compartments, having a capacity of 12 pallets and a

cost (inclusive of all charges) of ‚¬0.4 per kilometre;

• trucks with room-temperature compartments, having a capacity of 18 pallets

and a cost (inclusive of all charges) of ‚¬0.5 per kilometre.

TLFeBOOK

230 LONG-HAUL FREIGHT TRANSPORTATION

In addition, the company considers the possibility of transporting goods at room

temperature through another carrier, by paying ‚¬0.1 per kilometre for each pallet. A

directed graph representation of the problem is given in Figure 6.15.

Distances between terminals are reported in Table 6.9. The least-cost service net-

work can be obtained as the solution of an LFCND model with |K| = 22 commodities

(one for each combination of an origin“destination pair with positive demand and a

kind of product). Let A1 and A2 be the set of lines operated by means of trucks having

capacity equal to 12 pallets and 18 pallets, respectively, and let A3 be the set of lines

operated by an external carrier. Arc parameters are

k

cij = 0, (i, j ) ∈ A1 , k ∈ K,

fij = 0.4 dij , (i, j ) ∈ A1 ,

uij = 12, (i, j ) ∈ A1 ,

k

cij = 0, (i, j ) ∈ A2 , k ∈ K,

fij = 0.5, dij , (i, j ) ∈ A2 ,

uij = 18, (i, j ) ∈ A2 ,

k

cij = 0.1, dij , (i, j ) ∈ A3 , k ∈ K,

fij = 0, (i, j ) ∈ A3 ,

uij = ∞, (i, j ) ∈ A3 ,

where dij is the distance between terminals i and j .

The LFCND formulation is as follows.

Minimize

kk

cij xij + fij yij

k∈K (i,j )∈A1 ∪A2 ∪A3 (i,j )∈A1 ∪A2 ∪A3

subject to

±

oi , if i ∈ O(k),

k

k k

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

xj i

{j ∈V :(i,j )∈A1 ∪A2 ∪A3 } {j ∈V :(j,i)∈A1 ∪A2 ∪A3 } if i ∈ T (k),

0,

i ∈ V , k ∈ K,

k

(i, j ) ∈ A1 ∪ A2 ∪ A3 ,

xij ,

k∈K

k

(i, j ) ∈ A1 ∪ A2 ∪ A3 , k ∈ K

xij 0,

yij ∈ {0, 1}, (i, j ) ∈ A1 ∪ A2 ∪ A3 .

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 231

Milan Padua

3 4

2 1

Genoa Bologna

Figure 6.15 Graph representation of the FHL service network design problem (in order to

make the picture clean, a single edge is drawn for each pair of opposite arcs).

Table 6.9 Distances (in kilometres) between terminals in the FHL problem.

Bologna Genoa Milan Padua

Bologna 0 225 115 292

Genoa 225 0 226 166

Milan 115 226 0 362

Padua 292 166 362 0

The strong continuous relaxation gives a lower bound LB— = ‚¬534.60 per day. A

s

branch-and-bound algorithm based on the strong continuous relaxation generates 696

nodes. The least-cost solution is reported in Figure 6.16 and has a cost of ‚¬886.70 per

day. In the optimal solution, 7 lines are operated by 12-pallet trucks while a single line

is operated by an 18-pallet truck (travelling from Bologna to Milan with 5 pallets of

parcels). The number of pallets transported between each pair of terminals by means

of 12-pallet trucks and by the external carrier is reported in Tables 6.10 and 6.11.

Add“drop heuristics

Add“drop heuristics are simple constructive procedures in which at each step one

decides whether a new arc has to be used (add procedure) or an arc previously used

has to be left out (drop procedure). Several criteria can be employed to choose which

arc has to be added or dropped. In the following, a very simple drop procedure is

illustrated. In order to describe such an algorithm, it is worth noting that a candidate

optimal solution is characterized by the set A ⊆ A of selected arcs. A solution

TLFeBOOK

232 LONG-HAUL FREIGHT TRANSPORTATION

Table 6.10 Number of pallets of parcels/number of pallets of refrigerated goods

transported by means of 12-pallet trucks in the FHL problem.

Bologna Genoa Milan Padua

Bologna ” 4/8 ” 4/8

Genoa 0/7 ” 2/10 ”

Milan ” 5/7 ” ”

Padua 8/3 4/5 ” ”

Table 6.11 Number of pallets of parcels/number of pallets of refrigerated goods

transported by an external carrier in the FHL problem.

Bologna Genoa Milan Padua

Bologna ” 1/0 ” ”

Genoa ” ” 4/0 9/0

Milan ” ” ” ”

Padua ” ” ” ”

Milan Padua

3 4

2 1

Genoa Bologna

Figure 6.16 Transportation lines used in the optimal solution of the FHL problem.

is feasible if the LMMCF problem on the directed graph G(V , A ) induced by A is

feasible. If so, the solution cost is made up of the sum of the ¬xed costs fij , (i, j ) ∈ A ,

plus the optimal solution cost of the LMMCF problem. Moreover, it is worth noting

that the LFCND solution associated with A = A, if feasible, is characterized by a

large ¬xed cost and by a low transportation cost. On the other hand, a feasible solution

associated with a set A with a few arcs is expected to be characterized by a low ¬xed

cost and by a high variable cost. Consequently, an improved LFCND solution can be

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 233

Milan Padua

3 4

2 1

Genoa Bologna

Figure 6.17 Solution provided by the drop heuristic in the FHL problem.

obtained by iteratively removing arcs from the set A = A, while the current solution

is still feasible and the total cost decreases. The drop procedure is as follows.

k,(h)

Step 1. Set h = 0 and A(h) = A. Let xij , (i, j ) ∈ A, k ∈ K, be the optimal

solution (if any exists) of the LMMCF problem on the directed graph G(V , A(h) )

(h)

and let zLFCND be the cost of the associated LFCND problem. If the LMMCF

problem is infeasible, STOP, the LFCND problem is also infeasible.

Step 2. For each arc (i, j ) ∈ A(h) , set A (h) = A(h) \ {(i, j )} and solve the LMMCF

problem on the directed graph (G(V , A (h) ). If all the LMMCF problems are infea-

k,(h)

sible, STOP, the set of the arcs A(h) and the ¬‚ow pattern xij , (i, j ) ∈ A(h) , k ∈ K,

are associated with the best feasible solution found; otherwise, let (v, w) be the

arc whose removal from A(h) allows us to attain the least-cost LFCND feasible

solution.

Step 3. Set A(h+1) = A(h) \ (v, w), h = h + 1 and go back to Step 2.

The number of iterations of the algorithm is no more than the number of arcs and,

at each iteration, Step 2 requires the solution of O(|A|) LMMCF problems.

By applying the drop heuristic to the FHL problem, a solution having a cost equal

to ‚¬899 per day is obtained (see Figure 6.17).

6.7 Shipment Consolidation and Dispatching

In this section, we examine a consolidation and dispatching problem often faced by

manufacturers. A producer has to choose the best way of delivering timely a set of

TLFeBOOK

234 LONG-HAUL FREIGHT TRANSPORTATION

orders to its customers over a planning horizon made up of T days. The producer

must decide

• the best mode of transportation for each shipment;

• how orders have to be consolidated;

• the features of owned vehicle schedules (start times, intermediate stops (if any),

the order in which stops are visited, etc.).

Each order k ∈ K is characterized by a destination ik ∈ N, a weight wk 0, a

release time rk (the day in which order k is ready for delivery), and a deadline dk

(the day within which order k must be delivered to ik ). The company may transport

its products by renting ˜one-way™ truck trips, or by using an LTL carrier. A rented

truck may follow any route r of a pre-established set R. With each route r ∈ R are

associated a set of stops Sr (visited in a given order), a (¬xed) cost fr , and a capacity

qr (the maximum weight that the vehicle operating route r can carry). Moreover, let

„kr , k ∈ K, r ∈ R, be the number of travel days needed to deliver order k on route r.

Transporting order k to its destination by common carrier costs gk and takes „k days.

The decision variables are xkrt , k ∈ K, r ∈ R, t = 1, . . . , T , of a binary type, having

a value equal to 1 if order k is assigned to route r starting on day t, 0 otherwise; yrt ,

r ∈ R, t = 1, . . . , T , a binary variable equal to 1 if route r is operated on day t, 0

otherwise; wk , a binary variable equal to 1 if order k is transported by the common

carrier, 0 otherwise (such a variable is de¬ned only if rk + „k dk ).

Minimize

T

fr yrt + gk wk (6.49)

r∈R t=1 k∈K

subject to

r ∈ R, t = 1, . . . , T ,

wk xkrt qr yrt , (6.50)

k:rk t dk ’„kr ,ik ∈Sr

xkrt + wk = 1, k ∈ K, (6.51)

r:ik ∈Sr t:rk t dk ’„kr

xkrt ∈ {0, 1}, k ∈ K, r ∈ R, t = 1, . . . , T , (6.52)

yrt ∈ {0, 1}, r ∈ R, t = 1, . . . , T , (6.53)

wk ∈ {0, 1}, k ∈ K. (6.54)

The objective function (6.49) is the total cost paid to transport orders. Constraints

(6.50) state that, for each route r ∈ R and for each day t = 1, . . . , T the total weight

carried on route r, on day t, must not exceed capacity qr if yrt is equal to 1, and is

equal to 0, otherwise. Constraints (6.51) impose that each order is assigned to a route

operated by a rented truck or to the common carrier. It is easy to show that formulation

(6.49)“(6.54) can be transformed into a network design model on a time-expanded

directed graph.

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 235

Table 6.12 Trip ¬xed costs (in euros) in the Oxximet problem.

Trip Fixed cost

Bari“Marseille 800

Bari“Milan 750

Bari“Ancona 400

Bari“Ancona“Milan 780

Bari“Ancona“Marseille 830

Bari“Milan“Marseille 830

Bari“Ancona“Milan“Marseille 860

Table 6.13 Customers orders (in hundreds of kilograms) in the Oxximet problem.

Order Customer location Release time Deadline Weight

1 Marseille 16 June 3 July 15.44

2 Ancona 14 June 15 June 242.65

3 Ancona 14 June 16 June 102.54

4 Milan 13 June 13 June 100.46

5 Marseille 14 June 15 June 154.79

6 Marseille 14 June 14 June 78.53

7 Marseille 13 June 13 June 56.89

8 Marseille 14 June 14 June 45.42

9 Marseille 13 June 13 June 39.55

10 Marseille 11 June 15 June 207.34

11 Marseille 11 June 16 June 19.05

12 Marseille 11 June 16 June 19.59

13 Marseille 11 June 16 June 35.23

14 Marseille 11 June 16 June 61.54

15 Milan 11 June 16 June 38.31

Oxximet manufactures semi-¬nished chemical products in a plant located close to

Bari (Italy). The main customers are located in Marseille (France), Milan (Italy) and

Ancona (Italy). Oxximet rents ˜one-way™ truck trips visiting one or more customers.

No common carrier is used. Trip ¬xed costs are reported in Table 6.12. Truck capacity

is 260 hundred kilograms. Last 11 June, 15 customer orders were waiting to be satis¬ed

(Table 6.13). Oxximet solved model (6.49)“(6.54) with a six-day horizon (T = 6)

and gk = ∞. No trips were allowed on the subsequent Saturday and Sunday. The

optimal solution is reported in Table 6.14. It is worth noting that no truck trip was

rented on 12 June.

TLFeBOOK

236 LONG-HAUL FREIGHT TRANSPORTATION

Table 6.14 Optimal trip schedule in the Oxximet problem.

Day Trip Orders

11 June Bari“Marseille 10, 13

12 June ” ”

13 June Bari“Milan“Marseille 4, 7, 9, 11, 15

Bari“Marseille 5, 6, 12

14 June Bari“Ancona 2

Bari“Ancona“Marseille 3, 8, 14

17 June Bari“Marseille 1

6.8 Freight Terminal Design and Operations

Freight terminals are places where shipments are classi¬ed, consolidated, possibly

stored for a short time, and moved from incoming to outgoing vehicles. These include

LTL terminals, crossdocks, package-handling terminals (such as those of UPS and

FedEx) as well as rail, port and airport terminals. These facilities share several features

and consequently their design and management can be approached using common

methodologies. However, there are also signi¬cant differences among them. In this

section the analysis is restricted to terminals where material handling is labour inten-

sive (e.g. loads are moved by forklifts). This is the case, e.g. of LTL terminals and

crossdocks, where, as packages often have different sizes, it is dif¬cult to make use

of automatic equipment.

6.8.1 Design issues

The ¬rst design decision that has to be made is how many doors (or gates) a terminal

should have. Crossdocks have two kinds of doors: receiving doors and shipping doors

(see Chapter 1). In both cases, a door is assigned a share of ¬‚oor space (see Fig-

ure 6.18). The numbers of receiving and shipping doors are customarily set equal to

the number of destinations that have to be served, although high-volume destinations

may be assigned more than one door in order to accommodate multiple trucks at the

same time. In LTL terminals, the number of doors may be estimated by means of

simple formulae like those used in Chapter 5 for calculating the number of docks of

a warehouse. A better evaluation can be done through simulation models once other

design variables have been set.

Another key design decision is related to the choice of the terminal shape. Terminals

may have hundreds of doors so that distances travelled by workers in a trip may

exceed several hundred metres. It is then crucial to choose a shape that minimizes

the expected overall workload for a given number of doors. In practice, docks in the

shape of an I, L, T and H are quite common. In order to compare the different shapes,

two performance measures (named the diameter and the centrality of a terminal) have

been introduced. The diameter of a terminal is the largest distance between any pair

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 237

Table 6.15 Characteristics of the most common terminal shapes.

Number of corners

(Inside ’ Outside)

Shape Centrality

4/2 = 2 0’4

I

4/2 = 2 1’5

L

6/2 = 3 2’6

T

8/2 = 4 4’8

H

of doors. The centrality is the rate at which the diameter grows as the number of door

increases. For an I-shaped terminal the diameter is 2. In fact, if two doors are added

at each end, the diameter increases by two doors so that the centrality is 4/2 = 2.

The centrality of the most common shapes are reported in Table 6.15. Larger values

of centrality are better for two reasons: the workload is smaller and the forklift traf¬c

congestion is lighter. For example, for an I-shape, forklift traf¬c may be very heavy

in the middle of the terminal (in fact, it varies with the square of the number of the

doors) while for an H-shape it is much lighter ceteris paribus. On the other hand,

designs different from the I-shape show a deterioration in ef¬ciency due to the higher

number of corners. Corners reduce the potential number of doors along the perimeter

for two reasons (see Figures 6.18 and 6.19). First, each door needs a suitable amount

of ¬‚oor space, otherwise there is an interference between adjacent doors. Second,

where orthogonal segments of a terminal join, doors are unusable because vehicles

would overlap otherwise. As a result, for a given number of doors, the terminal has

to be larger if the number of corners increases.

The previous considerations suggest discarding L-shape designs because they have

the same value of centrality as the I-shape but more corners. Simulation-based studies

have shown that the I-shape is best for small to mid-sized terminals. The T-shape is

best for terminals with about 150 to 250 doors, while for larger terminals the H-shape

should be selected. Figure 6.20 illustrates qualitatively the expected workloads for

the I, T and H-shapes. The exact breakpoints depend on the material ¬‚ow pattern and

on how vehicles are assigned to doors.

6.8.2 Tactical and operational issues

At a tactical or operational level, one must decide how vehicles should be assigned to

gates. Such a decision is in¬‚uenced mostly by the type of terminal. In rail terminals

and airports, vehicles are dynamically assigned to doors, while in crossdocks doors

are permanently labelled as receiving or shipping doors. Moreover, in a crossdock,

doors do not usually change designations because this allows workers to be more

ef¬cient when handling freight.

For a crossdock, a good quality assignment can be obtained through the following

constructive heuristic (alternating heuristic), possibly followed by a local search

procedure.

TLFeBOOK

238 LONG-HAUL FREIGHT TRANSPORTATION

Share of Congestion

floor space

Congestion

Share of

floor space

I-shaped terminal.

Figure 6.18

No doors

Congestion

Congestion

L-shaped terminal (unusable doors are shadowed).

Figure 6.19

Step 1. Sort doors by nondecreasing average distance to all other doors.

Step 2. Sort outbound trailers by nonincreasing freight ¬‚ows.

Step 3. Assign alternatively the busiest inbound vehicle (trailer) and the busiest out-

bound trailer to the best locations still available. If there exist some more trailers

to allocate, repeat Step 3, otherwise STOP.

Blue Freight has a T-shaped crossdock with 200 doors in Denver (Colorado, USA).

By applying the alternating heuristic the solution shown in Figure 6.21 is obtained.

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 239

Workload

I T H

Doors

100 200 300 400

Figure 6.20 Expected workloads for the I, T and H-shapes.

Incoming trailers

Incoming trailers

Incoming trailers

Figure 6.21 Trailer allocation provided by the alternating heuristic in

the Blue Freight crossdock (receiving doors are bold).

6.9 Vehicle Allocation Problems

Vehicle allocation problems (VAPs) are faced by carriers that generate revenue by

transporting full loads over long distances, as in TL trucking and container shipping.

Once a vehicle delivers a load, it becomes empty and has to be moved to the pick-

up point of another load, or has to repositioned in anticipation of future demands.

A VAP amounts to deciding which loads have to be accepted and which ones have

to be rejected, as well as repositioning empty vehicles. In what follows, the VAP is

modelled as a minimum-cost ¬‚ow problem on a time-expanded directed graph for

the case where all demands are known in advance. For the sake of simplicity, we

TLFeBOOK

240 LONG-HAUL FREIGHT TRANSPORTATION

examine the case where a single vehicle type exists, while the extension to the multi-

vehicle type case is left to the reader as an exercise (see Problem 6.9). The case in

which demands are random is much more complex and is currently under study by the

scienti¬c community. The planning horizon is assumed to comprise a ¬nite number

{1, . . . , T } of time periods. Let N be the set of points (e.g. cities) where the (full)

loads have to picked up and delivered; dij t , i ∈ N , j ∈ N, t = 1, . . . , T , the number

of loads available at time period t to be moved from origin i to destination j ; „ij ,

i ∈ N, j ∈ N, the travel time from point i to point j ; pij , i ∈ N, j ∈ N , the pro¬t

(revenue minus direct operating costs) derived from moving a load from point i to

point j ; cij , i ∈ N , j ∈ N , the cost of moving an empty vehicle from point i to

point j . Moreover, denote by mit , i ∈ N, t = 1, . . . , T , the number of vehicles that

enter the system in period t at point i. The following decision variables are used: xij t ,

i ∈ N , j ∈ N, t = 1, . . . , T , representing the number of vehicles that start moving

a load from point i to point j at time period t; yij t , i ∈ N, j ∈ N, t = 1, . . . , T ,

representing the number of vehicles that start moving empty from point i to point j

at time period t. The deterministic single-vehicle VAP can be formulated as follows.

Maximize

T

(pij xij t ’ cij yij t ) (6.55)

t=1 i∈N j ∈N,j =i

subject to

(xij t + yij t ) ’ (xki(t’„ki ) + yki(t’„ki ) ) ’ yiit’1 = mit ,

j ∈N k∈N,k=i:t>„ki

i ∈ V , t ∈ {1, . . . , T }, (6.56)

i ∈ N, j ∈ N, t ∈ {1, . . . , T },

xij t dij t , (6.57)

i ∈ N, j ∈ N, t ∈ {1, . . . , T },

xij t 0,

i ∈ N, j ∈ N, t ∈ {1, . . . , T }.

yij t 0,

The objective function (6.55) is the total discounted pro¬t over the planning horizon.

Constraints (6.56) impose ¬‚ow conservation at the beginning of each time period,

while constraints (6.57) state that the number of loaded movements is bounded above

by the demand. It is worth noting that the dij t ’ xij t differences, i ∈ N, j ∈ N, t =

1, . . . , T , represent the loads that should be rejected, while yiit variables, i ∈ N, t =

1, . . . , T , represent vehicles staying idle (the so-called inventory movements). It is

easy to recognize that the VAP can be modelled as a minimum-cost ¬‚ow problem

on a time-expanded directed graph in which vertices are associated with (i, t) pairs,

i ∈ N, j ∈ N, and arcs represent loaded, empty and inventory movements. Therefore,

integrality constraints on xiit and yiit variables, i ∈ N , j ∈ N, t = 1, . . . , T , are

implicitly satis¬ed. Since there exists a pair of arcs between each pair of distinct

nodes, such a network is a directed multigraph.

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 241

Table 6.16 Travel times (in days) between terminals in the Murty problem.

Ananthapur Chittoor Ichapur Khammam Srikakulam

Ananthapur 0 1 2 2 2

Chittoor 1 0 2 2 2

Ichapur 2 2 0 2 1

Khammam 2 2 2 0 2

Srikakulam 2 2 1 2 0

Murty is a motor carrier operating in the Andhraachuki region (India). Last 11 July,

four TL transportation requests were made: from Chittoor to Khammam on 11 July,

from Srikakulam to Ichapur on 11 July, from Ananthapur to Chittoor on 13 July (two

loads). On 11 July, one vehicle was available in Chittoor and one in Khammam. A fur-

ther vehicle was currently transporting a previously scheduled shipment and would be

available in Chittoor on 12 July. Transportation times between terminals are shown in

Table 6.16. The revenue provided by a truck carrying a full load is 1.8 times the trans-

portation cost of a deadheading truck. Let T = {11 July, 12 July, 13 July} = {1, 2, 3}

and N = {Ananthapur, Chittoor, Ichapur, Khammam, Srikakulam} = {1, 2, 3, 4, 5}.

The optimal VAP solution is x141 = 1, x123 = 1, y441 = 1, y443 = 2, while the

remaining variables are zero. It is worth noting that the requests from Srikakulam to

Ichapur on 11 July and from Ananthapur to Chittoor on 13 July are not satis¬ed.

6.10 The Dynamic Driver Assignment Problem

The dynamic driver assignment problem (DDAP) arises in TL trucking where full-

load trips are assigned to drivers in an on-going fashion. In TL trucking a trip may take

several days (a four-day duration is not unusual both in Europe and in North America)

and customer service requests arrive at random. Consequently, each driver is assigned

a single trip at a time. Let D = {1, . . . , n} be the set of drivers waiting to be assigned

a task and let L = {1, . . . , n} be the current set of full-load trips to be performed.

When the number of drivers exceed the number of loads, a dummy load 0 is inserted

in L, while if the number of loads exceed the number of drivers, a dummy driver

0 is inserted in D. The DDAP can be formulated as a particular single-commodity

uncapacitated minimum-cost ¬‚ow problem (a classical transportation problem) and

can be solved ef¬ciently through the network simplex method or a tailored algorithm.

The cost cij , i ∈ D, j ∈ L, of assigning driver i to load j is set equal to the cost of

moving empty from the current location of driver i to the pick-up point of load j . Let

xij , i ∈ D, j ∈ L, be a binary variable equal to 1 if driver i is assigned to load j ,

0 otherwise. If the number of drivers exceed the number of loads, the DDAP can be

formulated as follows (see Figure 6.22).

TLFeBOOK

242 LONG-HAUL FREIGHT TRANSPORTATION

1 0 Dummy load

2 1

Drivers Loads

2

3

4

Figure 6.22 Driver assignment network.

Minimize

cij xij

i∈D j ∈L

subject to

xij = 1, i ∈ D,

j ∈L

xij = 1, j ∈ L \ {0},

i∈D

xij ∈ {0, 1}, i ∈ D, j ∈ L.

Costs ci0 , i ∈ D, can be set equal to 0. In practice, the previous model is reoptimized

as vehicle locations and customer requests are revealed during the planning horizon

(this explains the dynamic component of the model). In addition, penalties or bonuses

may have added to arc costs cij , i ∈ D, j ∈ L, to re¬‚ect the cost of taking drivers

home after a given number of weeks. A dispatcher who wants to take a driver i ∈ D

home at a given point in time can simply reduce the cost of the assignment of that

particular driver to loads j ∈ L whose delivery points are close to the driver home

location. This can be accomplished by subtracting a suitable quantity from such cij

costs.

Planet Transport Ltd is an Illinois (USA) motor carrier specializing in TL trucking.

Last 26 January, the company had to solve the problem of assigning four full-load

trips each three days long. The pick-up points were in Champaign, Danville, Peoria

and Spring¬eld. At that time six drivers were available. The ¬rst four were located

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 243

Table 6.17 Distance (in miles) between driver locations and trip pick-up points in

the Planet Transport problem.

Champaign Danville Peoria Spring¬eld

Bloomington 51.9 84.1 42.0 67.4

Decatur 46.8 83.3 107.0 40.0

Mason City 97.0 129.1 51.2 47.5

Pekin 95.4 127.6 13.1 69.4

Spring¬eld 85.5 121.9 74.3 0.0

Table 6.18 Optimal driver assignment in the Planet Transport problem.

Driver Location driver Trip Trip pick-up point

1 Bloomington 2 Danville

2 Decatur 1 Champaign

3 Mason City ” ”

4 Pekin 3 Peoria

5 Spring¬eld 4 Spring¬eld

6 Spring¬eld ” ”

in Bloomington, Decatur, Mason City and Pekin, the last two in Spring¬eld. The

company formulated and solved a DDAP model with |D| = 6, and a dummy load 0.

Costs cij , i ∈ D, j ∈ L \ {0}, were assumed to be proportional to distances between

driver locations i and full-load trip pick-up points j (see Table 6.17). The optimal

driver assignment is reported in Table 6.18. It is worth noting that the driver located

in Mason City and one of the two drivers situated in Spring¬eld were not assigned.

6.11 Questions and Problems

6.1 Assuming that the transportation rates for parcel, LTL trucking and TL trucking

are those depicted in Figures 6.1, 6.2, 6.3, respectively, draw the most conve-

nient rate as a function of load weight.

6.2 Canberra Freight is in charge of transporting auto parts for a US car manufac-

turer in Australia. Every week a tractor and one or two trailers move from the

port of Melbourne to a warehouse located 430 km away. A tractor costs $75

per day, a trailer $30, a driver $7.5 per hour while running costs are $0.75 per

kilometre. A trailer can contain 36 pallets. Derive the transportation cost per

TLFeBOOK

244 LONG-HAUL FREIGHT TRANSPORTATION

pallet as a function of shipment size for the case where one or two trailers are

used.

6.3 Truckload trucking rates from Boston (Massachusetts, USA) to Miami (Florida,

USA) are usually higher than those from Miami to Boston. Why?

6.4 Class 55 rates is cheaper than analogous class 70 rates (see Table 6.1). Why?

6.5 Extend Equation (6.2) to the case where two types of vehicles are available.

6.6 Devise a local search heuristic for the service network design problem in which

at each step an existing arc is removed or a new arc is added.

6.7 Why should U-shapes be avoided when designing a crossdock?

6.8 Apply the alternating heuristic to an H-shaped terminal. How are shipping doors

located?

6.9 Show that the deterministic VAP with multiple vehicle types can be modelled

as an LMMCF problem on a time-expanded directed graph.

6.10 Show that, in the DDAP, costs ci0 , i ∈ D, can be set equal equivalently to ∞.

6.12 Annotated Bibliography

An broad introduction to operations research methods for planning freight transporta-

tion is:

1. Crainic TG and Laporte G 1997 Planning models for freight transportation.

European Journal of Operational Research 97, 409“438.

For a survey on long-haul freight transportation, including a review of strategic plan-

ning activities performed by governments and international organizations, see:

2. Crainic TG 1998 A survey of optimization models for long-haul freight trans-

portation. Technical Report CRT-98-67, Centre de recherche sur les transports,

Montr©al, Canada.

A recommended textbook on network optimization problems is:

3. Ahuja RK, Magnanti TL and Orlin JB 1993 Network Flows: Theory, Algorithms,

and Applications. Prentice Halll, Englewood Cliffs, New Jersey.

An introductory article to network design problems is:

4. Magnanti TL and Wong RT 1984 Network design and transportation planning:

models and algorithms. Transportation Science 18, 1“55.

A good description of a number of issues related to dynamic models in transportation

and logistics is provided in:

TLFeBOOK

LONG-HAUL FREIGHT TRANSPORTATION 245

5. Powell WB, Jaillet P and Odoni AR 1995 Stochastic and dynamic networks

and routing. In Handbooks in Operations Research and Management Science,

8: Network Routing (ed. Ball MO, Magnanti TL, Monma CL and Nemhauser