. 10
( 15)


t =1 t =2

k=1 500 700
k=2 600 400

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


1 5



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
• vertices 1 and 5 represent the source and the destination of macro-product 1,
• vertices 2 and 6 represent the source and the destination of macro-product 2,
• vertices 3 and 4 represent the warehouse in the ¬rst and in the second semester,


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

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

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

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

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.


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


x13 26 000,
x14 20 000,
x35 18 000,
x45 18 000,
x23 14 000,
x24 13 000,
x36 12 000,
x46 14 000,
x34 + x34
1 2
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
¬‚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,
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

to ‚¬40 200 000. Subproblem k = 1 has, for »— , two optimal basic solutions
1,— 1,— 1,— 1,— 1,—
x13 = x14 = x35 = x45 = 18 000, x34 = 0
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
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

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


Break-bulk terminal D


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


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 ,

(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.
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
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.29)
(i, j ) ∈ A,
xij uij yij , (6.30)
(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)
(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.


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
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.
cij xij + fij yij
k∈K (i,j )∈A (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 ij
(i, j ) ∈ A,
xij uij yij ,
(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.


cij xij + fij yij (6.31)
k∈K (i,j )∈A (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.33)
(i, j ) ∈ A,
xij uij yij , (6.34)
(i, j ) ∈ A, k ∈ K,
xij 0, (6.35)
(i, j ) ∈ A.
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:

yij = (i, j ) ∈ A.

Hence, the constraints (6.36) can be replaced by the following conditions:
(i, j ) ∈ A.
xij uij ,

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

fij k
cij + x (6.37)
uij ij
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.39)
(i, j ) ∈ A,
xij uij , (6.40)
(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

of the above relaxation.

The strong continuous relaxation
The strong continuous relaxation is obtained by adding the following valid inequalities
uk yij , (i, j ) ∈ A, k ∈ K,
xij (6.42)

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.
cij xij + fij yij (6.43)
k∈K (i,j )∈A (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 yij , (i, j ) ∈ A, k ∈ K,
xij (6.45)
(i, j ) ∈ A,
xij uij yij , (6.46)
(i, j ) ∈ A, k ∈ K,
xij 0, (6.47)
(i, j ) ∈ A.
0 1, (6.48)
Let LB— be the lower bound on zLFCND given by the optimal objective function

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
— , 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%
lower than LB— .


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.


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
cij = 0, (i, j ) ∈ A1 , k ∈ K,
fij = 0.4 dij , (i, j ) ∈ A1 ,
uij = 12, (i, j ) ∈ A1 ,
cij = 0, (i, j ) ∈ A2 , k ∈ K,
fij = 0.5, dij , (i, j ) ∈ A2 ,
uij = 18, (i, j ) ∈ A2 ,
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.
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
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),
i ∈ V , k ∈ K,

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

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


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

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


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


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.


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


Table 6.15 Characteristics of the most common terminal shapes.

Number of corners
(Inside ’ Outside)
Shape Centrality

4/2 = 2 0’4
4/2 = 2 1’5
6/2 = 3 2’6
8/2 = 4 4’8

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


Share of Congestion
floor space


Share of
floor space

I-shaped terminal.
Figure 6.18

No doors



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.



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


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


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


1 0 Dummy load

2 1

Drivers Loads



Figure 6.22 Driver assignment network.

cij xij
i∈D j ∈L

subject to

xij = 1, i ∈ D,
j ∈L

xij = 1, j ∈ L \ {0},
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

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


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


pallet as a function of shipment size for the case where one or two trailers are
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
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:


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


. 10
( 15)