. 11
( 15)


GL), pp. 141“295. Elsevier Science, Amsterdam.
Several aspects related to the design and operation of a crossdock are illustrated in
the following articles:
6. Bartholdi III JJ and Gue KR 2000 The best shape for a crossdock. Techni-
cal Report, Department of Systems Management Naval Postgraduate School
Monterey, California, USA.
7. Gue KR 1999 The effects of trailer scheduling on the layout of freight terminals.
Transportation Science 33, 419“428.
8. Bartholdi III JJ and Gue KR 2000 Reducing labour costs in an LTL crossdocking
terminal. Operations Research 48, 823“832.


Planning and Managing
Short-Haul Freight

7.1 Introduction
Short-haul freight transportation concerns the pick-up and delivery of goods in a
relatively small area (e.g. a city or a county) using a ¬‚eet of trucks. As a rule, vehicles
are based at a single depot, and vehicle tours are performed in a single work shift and
may include several pick-up and delivery points.

Classi¬cation of short-haul transportation services. Short-haul transportation is
relevant to distribution companies that have to supply retail outlets or customer orders
from a warehouse using small vans (see Figure 7.1a). It is also crucial to local fast
couriers transporting loads between origin“destination pairs situated in the same area.
Similarly, long-haul carriers need to collect locally outbound parcels before sending
them to a remote terminal as a consolidated load, and to locally distribute loads
coming from remote terminals (see Figure 7.1b). Short-haul transportation problems
also arise in garbage collection, mail delivery, appliance repair services, dial-a-ride
systems (providing transportation services to the elderly and the handicapped), and
emergency services (including ¬re ¬ghting and ambulance services).

Decision problems. Short-haul transportation often involves a large number of
users. For instance, in soft drink and beer distribution, the average number of cus-
tomers visited daily can be up to 600, while in sanitation applications the number
of sites visited daily is often between 200 and 1000. At a strategic level, the main
decision is related to warehouse location. For this purpose, the methods illustrated
in Chapter 3 can be used, although some adaptations are sometimes needed in order
to take vehicle routes into account explicitly (see Section 7.8). At a tactical level,
the main issue is ¬‚eet sizing (see Section 6.4). Finally, at an operational level, the

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)


Pickup routes based
at terminal A

Terminal A

Warehouse 1 Warehouse 2 Terminal B

Terminal C

Delivery routes based
at terminal B

Delivery routes based Delivery routes based
at warehouse 1 at warehouse 2
(a) (b)

Figure 7.1 (a) Delivery routes based at warehouses. (b) Pickup and
delivery routes based at terminals of a long-haul carrier.

main problem (usually referred to as the vehicle routing and scheduling problem
(VRSP)) is to build vehicle routes in order to satisfy user requests. At this stage, a
number of operational constraints have to be taken into account. In some settings,
vehicle routes can be planned on a regular basis as all data are known beforehand.
This is the case of a company devising daily its distribution plan on the basis of the
customer orders collected the day before. Another example arises in sanitation appli-
cations, where vehicle routes are designed two or three times a year as the amount
of garbage to be collected daily is the same over several months. In contrast to such
static environments, there are settings where vehicle routes are built in an on-going
fashion as customer requests arrive. This is the case, for example, of long-distance
carriers whose pick-up requests arise during the day of operations and have to be
serviced the same day whenever possible. Due to recent advances in information
and communication technologies, vehicle ¬‚eets can now be managed easily in real-
time. When jointly used, devices like GIS, GPS, traf¬c ¬‚ow sensors and cellular
telephones are able to provide relevant real-time data, such as current vehicle loca-
tions, new customer requests and up-to-date estimates of road travel times. If suitably
processed, these data can be used to devise revised vehicle routes. The main features
of such vehicle routing and dispatching problems (VRDPs) are brie¬‚y illustrated in
Section 7.7.
A slightly different class of operational problems arises in vendor-managed dis-
tribution systems which are quite common in the petrochemical and gas industry as
well as in the soft drink business. Vendor-managed resupplying (VMR) requires that
the distribution companies estimate customer inventory levels so that replenishment
can occur before they run out of stock. Such systems are discussed in Section 7.9.



4 8

5 9
Street A Street B
1 10



Street C

Figure 7.2 (a) A road network where 10 customers (represented by black dots)
are to be served. Streets A and C are two-way. Street B is one-way.

7.2 Vehicle Routing Problems
VRPs consist of determining the routes to be used by a ¬‚eet of vehicles to serve a set
of users. VRPs can be de¬ned on a mixed graph G = (V , A, E), where V is a set of
vertices, A is a set of arcs and E is a set of edges. A vertex 0 represents the depot at
which m vehicles are based, while a subset U ⊆ V of required vertices and a subset
R ⊆ A ∪ E of required arcs and required edges represent the users. VRPs amount to
determining a least-cost set of m tours based at a depot, and including the required
vertices, arcs and edges.
In this graph representation, arcs and edges correspond to road segments, and
vertices correspond to road intersections. Isolated users are represented by required
vertices, whereas subsets of customers distributed almost continuously along a set of
customers are modelled as required arcs or edges (this is often the case of mail delivery
and solid waste collection in urban areas). See Figures 7.2 and 7.3 for an example. If
R = …, the VRP is called a node routing problem (NRP), while if U = … it is called
an arc routing problem (ARP). NRPs have been studied more extensively than ARPs
and are usually referred to simply as VRPs. However, for the sake of clarity, in this
textbook we use the appellation NRPs. If m = 1 and there are no side constraints,
the NRP is the classical travelling salesman problem, which consists of determining
a single circuit spanning the vertices of G, whereas the ARP is the rural postman
problem (RPP), which amounts to designing a single circuit including the arcs and
edges of R. The RPP reduces to the Chinese postman problem (CPP) if every arc and
edge has to be serviced (R = A ∪ E).


1 2 1 2

3 to 10 3 to 7 8 to 10

(b) (c)

Figure 7.3 (b) A graph representation in case a vehicle traversing road B can serve the
customers on both sides. (c) A graph representation in case a vehicle traversing road B can
serve the customers on a single side. Bold vertices, arcs and edges are required.

Operational constraints. The most common operational constraints are
• the number of vehicles m can be ¬xed or can be a decision variable, possibly
subject to an upper bound constraint;
• the total demand transported by a vehicle at any time must not exceed its
• the duration of any route must not exceed a work shift duration;
• customers require to be served within pre-established time windows;
• some customers must be served by speci¬c vehicles;
• the service of a customer must be performed by a single vehicle or may be
shared by several vehicles;
• customers are subject to precedence relations.
When customers impose service time windows or when travel times vary during
the day, time issues have to be considered explicitly in the design of vehicle routes,
in which case VRPs are often referred to as VRSPs.
Precedence constraints arise naturally whenever some goods have to be transported
between speci¬ed pairs of pick-up and delivery points. In such problems, a pick-up
and delivery pair is to be serviced by the same vehicle (no transshipment is allowed
at the depot) and each pick-up point must be visited before the associated delivery
point. Another kind of precedence relation has to be imposed whenever vehicles have
¬rst to perform a set of deliveries (linehaul customers) and then a set of pick-ups
(backhaul customers), as is customary in some industries (VRPs with backhauls, see
Figure 7.4).






Figure 7.4 Vehicle routing with backhauls (L, linehaul customer; B, backhaul customers).

Objective. With each arc and edge (i, j ) ∈ A ∪ E are associated a travel time tij
and a travel cost cij . In addition, with each vehicle may be associated a ¬xed cost.
The most common objective is to minimize the cost of traversing the arcs and edges
of the graph plus the sum of the ¬xed costs associated with using the vehicles.

Travel time estimate. While the computation of distances in a road network is
straightforward, the accurate estimation of travel times is often dif¬cult. A rough
evaluation of the travel time along a road segment can be obtained by dividing road
length by the average speed at which the road segment can normally be traversed.
This method is fairly accurate for inter-city roads, for which a constant speed can be
kept for a long time, but performs poorly for intra-city streets. In such a case, average
travel times can be estimated by using a regression method. To this end, the factors
affecting travel time along a street are identi¬ed, and then a regression equation is used
to forecast the average travel time as a function of these factors. The most relevant
factors are the number of lanes, street width, whether the street is one-way or two-way,
parking regulations, traf¬c volume, the number of traf¬c lights, the number of stop
signs and the quality of the road surface.

In a school bus routing and scheduling study, the traversal times of the streets and
avenues of Manhattan (New York, USA) were computed by estimating vehicle speed
v through the following formula,
v = v + 2.07x1 + 7.52x2 + 1.52x3 + 1.36x4 ’ 3.26x5 + 4.04x6 ,
where v = 7.69 miles per hour is the average bus speed in normal conditions, x1 is
the total number of street lanes, x2 is the number of street lanes available for buses,
x3 is a binary constant, equal to 1 in case of one-way street, 0 otherwise, x4 is equal
to 1 in case of bad road surface conditions, 2 in case of good road surface conditions,


x5 takes into account the traf¬c volume (1 = low, 2 = medium, 3 = high), and x6 is the
time fraction of green lights. Variable coef¬cients were estimated through regression

In the remainder of the chapter, the emphasis is on heuristics, although some rel-
atively simple lower bounds are illustrated in order to gain some insight into the
mathematical structure of VRPs. This choice is motivated by two factors: ¬rst, exact
algorithms for VRPs are often quite complex tailored procedures able to solve only
small instances of speci¬c problems; second, feasible solutions usually have to be
generated in a small amount of time.

7.3 The Travelling Salesman Problem
In the absence of operational constraints, there always exists an optimal NRP solution
in which a single vehicle is used (see Problem 7.3). Hence, the NRP reduces to a TSP
which consists of ¬nding a least-cost tour including all the required vertices and the
depot. In any TSP feasible solution on graph G, each vertex of U ∪ {0} appears at
least once and two successive vertices of U ∪ {0} are linked by a least-cost path. As
a consequence, the TSP can be reformulated on an auxiliary complete directed graph
G = (V , A ), where V = U ∪ {0} is the vertex set and A is the arc set. With each
arc (i, j ) ∈ A is associated a cost cij equal to that of a least-cost path from i to j in
G. These costs satisfy the triangle inequality:
cik + ckj , ∀(i, j ) ∈ A , ∀k ∈ V , k = i, j.
Because of this property, there exists a TSP optimal solution which is a Hamiltonian
tour in G , i.e. a cycle in which each vertex in V appears exactly once. In what follows,
the search for an optimal or suboptimal TSP solution is restricted to Hamiltonian tours.
If cij = cj i for each pair of distinct vertices i, j ∈ V , the TSP is said to be
symmetric (STSP), otherwise it is called asymmetric (ATSP). The STSP is suitable
for inter-city transportation, while theATSP is recommended in urban settings because
of one-way streets. Of course, the solution techniques developed for the ATSP can
also be applied to the STSP. This approach could, however, be very inef¬cient, as
explained later. It is therefore customary to deal with the two cases separately.

7.3.1 The asymmetric travelling salesman problem
The ATSP can be formulated as follows. Let xij , (i, j ) ∈ A , be a binary decision
variable equal to 1 if arc (i, j ) is part of the solution, 0 otherwise.
cij xij
(i,j )∈A


subject to
xij = 1, j ∈V , (7.1)
i∈V \{j }

xij = 1, i∈V , (7.2)
j ∈V \{i}

xij ∈ X, (i, j ) ∈ A , (7.3)
xij ∈ {0, 1}, (i, j ) ∈ A .
Equations (7.1) and (7.2) are referred to as degree constraints. Constraints (7.1)
mean that a unique arc enters each vertex j ∈ V . Similarly, constraints (7.2) state
that a single arc exits each vertex i ∈ V . Constraints (7.3) specify that the xij values
must lie in a set X that will yield a feasible solution consisting of a single directed
tour (circuit). They can be formulated in two alternative ways, which are algebraically
equivalent (see Problem 7.10):
S ‚ V , |S|
xij 1, 2, (7.4)
i∈S j ∈S

|S| ’ 1, S ‚ V , |S|
xij 2. (7.5)
i∈S j ∈S

Inequalities (7.4) guarantee that the circuit has at least one arc coming out from each
proper and nonempty subset S of vertices in V (connectivity constraints). Inequalities
(7.5) prevent the formation of subcircuits containing less than |S| vertices (subcircuit
elimination constraints). It is worth noting that the number of constraints (7.4) (or,
equivalently, (7.5)) is 2|V | ’ |V | ’ 2. Constraints (7.4) and (7.5) are redundant for
|S| = 1 because of constraints (7.2).

A lower bound. The ATSP has been shown to be NP-hard. A good lower bound

on the ATSP optimal solution cost zATSP can be obtained by removing constraints
(7.3) from ATSP formulation. The relaxed problem is the following linear assignment
problem (AP).
cij xij
i∈V j ∈V
subject to
xij = 1, j ∈V ,

xij = 1, i∈V ,
j ∈V
xij ∈ {0, 1}, i, j ∈ V ,

where cii = ∞, i ∈ V , in order to force xii = 0, for all i ∈ V .


The optimal AP solution xAP corresponds to a collection of p directed subcircuits
C1 , . . . , Cp , spanning all vertices of the directed graph G . If p = 1, the AP solution
is feasible (and hence optimal) for the ATSP.
— —
As a rule, zAP is a good lower bound on zATSP if the cost matrix is strongly asym-
metric (in this case, it has been empirically demonstrated that the deviation from
— — —
the optimal solution cost (zATSP ’ zAP )/zAP is often less than 1%). On the contrary,
in the case of symmetric costs, the deviation is typically 30% or more. The reason
of this behaviour can be explained by the fact that for symmetric costs, if the AP
solution contains arc (i, j ) ∈ A , then the AP optimal solution is likely to include
arc (j, i) ∈ A too. As a result, the optimal AP solution usually shows several small
subcircuits and is quite different from the ATSP optimal solution.

Bontur is a pastry producer founded in Prague (Czech Republic) in the 19th cen-
tury. The ¬rm currently operates, in addition to four modern plants, a workshop in
Gorazdova street, where the founder began the business. The workshop serves Prague
and its surroundings. Every day at 6:30 a.m. a ¬‚eet of vans carries the pastries from
the workshop to several retail outlets (small shops, supermarkets and hotels). In par-
ticular, all outlets of the Vltava river district are usually served by a single vehicle.
For the sake of simplicity, arc transportation costs are assumed to be proportional to
arc lengths. In Figure 7.5 the road network is modelled as a mixed graph G(V , A),
where a length is associated with each arc/edge (i, j ). The workshop and the vehicle
depot are located in vertex 0. Last 23 March, seven shops (located at vertices 1, 3, 9,
18, 20 and 22) needed to be supplied. The problem can be formulated as an ATSP on
a complete directed graph G = (V , A ), where V is formed by the seven vertices
associated with the customers and by vertex 0. With each arc (i, j ) ∈ A is associ-
ated a cost cij corresponding to the length of the shortest path from i to j on G (see

Table 7.1). The optimal AP solution xAP is made up of the following three subcircuits
(see Figure 7.6):
C1 = {(1, 4), (4, 3), (3, 9), (9, 1)},
of cost equal to 11.0 km;
C2 = {(0, 18), (18, 0)},
of cost equal to 5.2 km;
C3 = {(20, 22), (22, 20)},

of cost equal to 4.6 km. Therefore, the AP lower bound zAP on the objective function
value of ATSP is equal to

zAP = 11.0 + 5.2 + 4.6 = 20.8 km.

Patching heuristic. The patching heuristic works as follows. First, theAP relaxation
is solved. If a single circuit is obtained, the procedure stops (the AP solution is


i j 20 23
0.2 0.7
0.2 1.4
6 1.0
1.9 19
7 16
3 0.7 0.5
0.5 1.0
17 21
5 0.6 0.9
1.6 9 1.0
0.5 2.0
0.9 15
0.7 10
1.8 12 18
2 0.5
0.4 11
0.5 1.3
1.1 0.5
2.1 14 0.9
1 0

Figure 7.5 A graph representation of Bontur distribution problem (one-way street segments
are represented by arcs, while two-way street segments are modelled through edges).

i j 20


1.6 9

2.1 3.9

1 0

Figure 7.6 Optimal solution of the AP relaxation in the Bontur problem.

the optimal ATSP solution). Otherwise, a feasible ATSP solution is constructed by
merging the subcircuits of the AP solution. When merging two subcircuits, one arc
is removed from each subcircuit and two new arcs are added in such a way a single
connected subcircuit is obtained.

Step 0 (Initialization). Let C = {C1 , . . . , Cp } be the set of the p subcircuits in the AP
optimal solution. If p = 1, STOP. The AP solution is feasible (and hence optimal)
for the ATSP.

Step 1. Identify the two subcircuits Ch , Ck ∈ C with the largest number of vertices.


Table 7.1 Shortest-path length (in kilometres) from i to j , i, j ∈ V in the Bontur problem.

0 1 3 4 9 18 20 22

0 0.0 5.5 4.2 2.6 2.4 1.3 2.5 4.3
1 4.7 0.0 3.7 2.1 5.1 6.0 7.2 9.0
3 4.2 4.5 0.0 1.6 3.2 5.5 6.7 8.5
4 2.6 2.9 1.6 0.0 3.0 3.9 5.1 6.9
9 3.8 4.1 2.8 1.2 0.0 5.1 6.3 8.1
18 3.9 7.4 6.1 4.5 3.3 0.0 1.2 3.0
20 3.5 7.0 5.7 4.1 2.9 1.2 0.0 2.3
22 5.8 9.3 8.0 6.4 5.2 3.0 2.3 0.0

i j 20
cij 2.3



4 4.2

1 0

Figure 7.7 Partial solution at the end of the ¬rst iteration of
the patching algorithm in the Bontur problem.

Step 2. Merge Ch and Ck in such a way that the cost increase is kept at minimum.
Update C and let p = p ’ 1. If p = 1, STOP, a feasible solution ATSP has been
determined, otherwise go back to Step 1.

In order to ¬nd a feasible solution xATSP to the Bontur distribution problem, the
patching algorithm is applied to the AP solution shown in Figure 7.6. At the ¬rst
iteration, C1 and C2 are selected to be merged (alternatively, C3 could have been used
instead of C2 ). By merging C1 and C2 at minimum cost (through the removal of arcs
(3,9) and (18,0) and the insertion of arcs (3,0) and (18,9)), the following subcircuit
(having length equal to 16.6 km) is obtained (see Figure 7.7):
C4 = {(0, 18), (18, 9), ((9, 1), (1, 4), (4, 3), (3, 0))}.


i j 20



4 4.2

1 0

Figure 7.8 ATSP feasible solution generated by
the patching algorithm in the Bontur problem.

The partial solution, formed by the two subcircuits C3 and C4 , is depicted in
Figure 7.7. The total length increases by 0.4 km with respect to the initial solution.
At the end of the second iteration, the two subcircuits in Figure 7.7 are merged at the
minimum cost increase of 0.3 km through the removal of arcs (18,9) and (20,22) and
the insertion of arcs (18,22) and (20,9). This way, a feasible ATSP solution of cost
zATSP = 21.5 km is obtained (see Figure 7.8). In order to evaluate the quality of the
heuristic solution, the following deviation from the AP lower bound can be computed,

¯ 21.5 ’ 20.8
= = 0.0337,

zAP 20.8
which corresponds to a percentage deviation of 3.37%.

7.3.2 The symmetric travelling salesman problem
As explained in the previous section, the ATSP lower and upper bounding procedures
perform poorly when applied to the symmetric TSP. For this reason, several STSP
tailored procedures have been developed.
The STSP can be formulated on a complete undirected graph G = (V , E ), in
which with each edge (i, j ) ∈ E is associated a transportation cost cij equal to that of
a least-cost path between i and j in G. Hence, cij costs satisfy the triangle inequality,
and there exists an optimal solution which is a Hamiltonian cycle in G . Let xij ,
(i, j ) ∈ E , be a binary decision variable equal to 1 if edge (i, j ) ∈ E belongs to the
least-cost Hamiltonian cycle, and to 0 otherwise. The formulation of the STSP is as
follows (recall that i < j for each edge (i, j ) ∈ E ).


cij xij
(i,j )∈E

subject to
xij + xj i = 2, j ∈V , (7.6)
i∈V :(i,j )∈E i∈V :(j,i)∈E

xij + S‚V , 2 |S| |V |/2 , (7.7)
xj i 2,
(i,j )∈E :i∈S,j ∈S (j,i)∈E :i∈S,j ∈S
/ /

xij ∈ {0, 1}, (i, j ) ∈ E .
Equations (7.6) mean that exactly two edges must be incident to every vertex
j ∈ V (degree constraints). Inequalities (7.7) state that, for every vertex subset S,
there exist at least two edges with one endpoint in S ‚ V and the other endpoint in
V \ S (connectivity constraints). Since the connectivity constraints of a subset S and
that of its complement V \ S are equivalent, one has to consider only inequalities
(7.7) associated with subsets S ‚ V such that |S| |V |/2 . Constraints (7.7) are
redundant if |S| = 1 because of (7.6). Alternatively, the connectivity constraints (7.7)
can be replaced with the following equivalent subcycle elimination constraints:

|S| ’ 1, S‚V , 2 |S| |V |/2 .
(i,j )∈E :i∈S,j ∈S

A lower bound. The STSP is an NP-hard problem. A lower bound on the optimal

solution cost zSTSP can be obtained by solving the following problem (see Exer-
cise 7.5).
cij xij (7.8)
(i,j )∈E

subject to
xir + xri = 2, (7.9)
i∈V :(i,r)∈E i∈V :(r,i)∈E

xij + xj i 1,
(i,j )∈E :i∈S,i=r,j ∈S,j =r (j,i)∈E :i∈S,i=r,j ∈S,j =r
/ /
S‚V , 1 |S| |V |/2 , (7.10)
xij ∈ {0, 1}, (i, j ) ∈ E , (7.11)
where r ∈ V is arbitrarily chosen (root vertex). Model (7.8)“(7.11) corresponds to a
minimum-cost spanning r-tree problem (MSrTP), for which the optimal solution is
a least-cost connected subgraph spanning G and such that vertex r ∈ V has degree
2. The MSrTP can be solved in O(|V |2 )) steps with the following procedure:


Table 7.2 Shortest distances (in kilometres) between terminals in the Saint-Martin problem.

Betteville Bolbec Dieppe F´ camp Le Havre Luneray Rouen Valmont

Betteville 0.0 27.9 54.6 42.0 56.5 37.0 30.9 34.1
Bolbec 27.9 0.0 67.2 25.6 28.8 48.4 57.4 21.6
Dieppe 54.6 67.2 0.0 60.5 95.8 18.8 60.4 52.1
F´ camp
e 42.0 25.6 60.5 0.0 39.4 43.1 70.2 12.2
Le Havre 56.5 28.8 95.8 39.4 0.0 77.2 84.5 44.4
Luneray 37.0 48.4 18.8 43.1 77.2 0.0 51.6 34.0
Rouen 30.9 57.4 60.4 70.2 84.5 51.6 0.0 59.3
Valmont 34.1 21.6 52.1 12.2 44.4 34.0 59.3 0.0

Step 1. Determine a minimum-cost tree T — (V \ {r}, ET ) spanning V \ {r}.

Step 2. Insert in T — vertex r as well as the two least-cost edges incident to vertex r.

Saint-Martin distributes fresh ¬shing products in Normandy (France). Last 7 June,
the company received seven orders from sales points all located in northern Normandy.
It was decided to serve the seven requests by means of a single vehicle sited in
Betteville. The problem can be formulated as an STSP on a complete graph G (V , E ),
where V is composed of eight vertices corresponding to the sales points and of vertex
0 associated with the depot. With each edge (i, j ) ∈ E , is associated a cost cij equal
to the shortest distance between vertices i and j (see Table 7.2). The minimum-cost

spanning r-tree is depicted in Figure 7.9, to which corresponds a cost zMSrTP =
225.8 km.

The MSrTP lower bound can be improved in two ways. In the former approach,
the MSrTP relaxation is solved for more choices of the roots r ∈ V and then the
largest MSrTP lower bound is selected. In the latter method, r ∈ V is ¬xed but each
constraint (7.6) with the only exception of j = r is relaxed in a Lagrangian fashion.
Let »j , j ∈ V \ {r}, be the Lagrangian multiplier attached to vertex j ∈ V \ {r}. A
Lagrangian relaxation of the STSP is as follows.


cij xij + xij + xj i ’ 2
»j (7.12)
j ∈V \{r} i∈V :(i,j )∈E i∈V :(j,i)∈E
(i,j )∈E

subject to
xir + xri = 2, (7.13)
i∈V :(i,r)∈E i∈V :(r,i)∈E


i j 2


3 34.0




4 6

Figure 7.9 Minimum-cost spanning r-tree in the Saint-Martin problem.

xij + xj i 1,
(i,j )∈E :i∈S,i=r,j ∈S,j =r (j,i)∈E :i∈S,i=r,j ∈S,j =r
/ /
S‚V , 1 |S| |V |/2 , (7.14)

xij ∈ {0, 1}, (i, j ) ∈ E . (7.15)

Setting arbitrarily »r = 0, the objective function (7.12) can be rewritten as

(cij + »i + »j )xij ’ 2 »j . (7.16)
j ∈V
(i,j )∈E

To determine the optimal multipliers (or at least a set of ˜good™ multipliers), a
suitable variant of the subgradient method illustrated in Section 3.3.1 can be used. In
particular, at the kth iteration the updating formula of the Lagrangian multipliers is
the following,
»k+1 = »k + β k sj , j ∈ V \ {r},

k k k
sj = xij + xj i ’ 2, j ∈ V \ {r},
i∈V :(i,j )∈E i∈V :(j,i)∈E

xij , (i, j ) ∈ E , is the optimal solution of the Lagrangian relaxation MSrTP(») (7.16),

(7.13)“(7.15) at the kth iteration, and β k can be set equal to
βk = k = 1, . . . .


The results of the ¬rst three iterations of the subgradient method in the Saint-Martin
problem (r = 0) are

»1 = 0, j ∈ V \ {r}; zMSrTP(»1 ) = 225.8; s 1 = [1, ’1, ’1, ’1, 1, 0, 1]T ;

β 1 = 1;

»2 = [1, ’1, ’1, ’1, 1, 0, 1]T ; zMSrTP(»2 ) = 231.8;
s 2 = [1, ’1, ’1, ’1, 1, 0, 1]T ; β 2 = 0.5;

»3 = [ 2 , ’ 2 , ’ 2 , ’ 2 , 2 , 0, 2 ]T ; zMSrTP(»3 ) = 234.8.
3 3 3 33 3

Nearest-neighbour heuristic. The nearest-neighbour heuristic is a simple con-
structive procedure that builds a Hamiltonian path by iteratively linking the vertex
inserted at the previous iteration to its nearest unrouted neighbour. Finally, a Hamil-
tonian cycle is obtained by connecting the two endpoints of the path. The nearest-
neighbour heuristic often provides low-quality solutions, since the edges added in the
¬nal iterations may be very costly.
Step 0. Set C = {r}, where r ∈ V , is a vertex chosen arbitrarily, and set h = r.
Step 1. Identify the vertex k ∈ V \ S such that chk = minj ∈V \C {chj }. Add k at the
end of C.
Step 2. If |C| = |V |, add r at the end of C, STOP (C corresponds to a Hamiltonian
cycle), otherwise let h = k and go back to Step 1.

In order to ¬nd a feasible solution xSTSP to the Saint-Martin distribution problem,
the nearest-neighbour heuristic is applied (r = 0), and the following Hamiltonian
cycle is obtained (see Figure 7.10),
C = {(0, 1), (1, 7), (3, 7), (3, 4), (4, 5), (2, 5), (2, 6), (0, 6)},
whose cost is 288.4 km. The deviation of this solution cost from the available lower
bound LB = 234.8 is
¯ 288.4 ’ 234.8
= = 22.8%.
LB 234.8

The Christo¬des heuristic. The Christo¬des heuristic is a constructive procedure
that works as follows.
Step 1. Compute a minimum-cost tree T = (V , ET ) spanning the vertices of

G (V , E ). Let zMSTP be the cost of this tree.


i j 2


3 12.2



4 6

Figure 7.10 STSP feasible solution generated by the nearest-neighbour
algorithm in the Saint-Martin problem.

Step 2. Compute a least-cost perfect matching M(VD , ED ) among the vertices of

odd degree in the tree T (|VD | is always an even number). Let zM be the optimal
matching cost. Let H (V , EH ) be the Eulerian subgraph (or multigraph) of G
induced by the union of the edges of T and M (EH = ET ∪ ED ).
Step 3. If there is a vertex j ∈ V of degree greater than 2 in subgraph H , eliminate
from ES two edges incident in j and in vertices h ∈ V and k ∈ V , with h = k.
Insert in EH edge (h, k) ∈ E (or the edge (k, h) ∈ E if (h, k) ∈ E ) (the shortcuts
method, see Figure 7.11). Repeat Step 3 until all vertices in V have a degree of 2
in subgraph H .
Step 4. STOP, the set EH is a Hamiltonian cycle.
It is worth stressing that the substitution of a pair of edges (h, j ) and (j, k) with
edge (h, k) (Step 3 of the algorithm) generally involves a cost reduction since the
triangle inequality holds. It can be shown that the cost of the Christo¬des solution is
at most 50% higher than the optimal solution cost. The proof is omitted for brevity.

The Saint-Martin distribution problem is solved by means of the Christo¬des algo-
rithm. The minimum-cost spanning tree is made up of edges {(0,1), (0,6), (1,4), (1,7),
(2,5), (3,7), (5,7)}, and has a cost of 174.2 km. The optimal matching of the odd-
degree vertices (1, 2, 3, 4, 6 and 7) is composed of edges (1,4), (2,6) and (3,7), and
has a cost of 101.4 km. The Eulerian multigraph generated at the end of Step 2 is
illustrated in Figure 7.12. Edges (1,7) and (3,7) are substituted for edge (1,3), edges
(0,1) and (1,4) are substituted for edge (0,4). At this stage a Hamiltonian cycle of


1 1

2 2

3 3

4 4

5 6 5 6

(a) (b)

Figure 7.11 The Christo¬des algorithm. (a) Partial solution at the end of Step 2 (mini-
mum-cost spanning tree edges are continuous lines while matching edges are dashed lines).
(b) The Hamiltonian cycle obtained after Step 3 (where the degree of vertex 2 is reduced by
removing edges (0,2) and (2,1) and by inserting edge (0,1), and the degree of vertex 4 is reduced
by removing edges (1,4) and (4,6) and by inserting edge (1,6)).

cost equal to 267.2 km is obtained (see Figure 7.13). The deviation from the available
lower bound LB is
¯ 267.2 ’ 234.8
= = 13.8%.
LB 234.8

Local search algorithms. Local search algorithms are iterative procedures that try
to improve an initial feasible solution x (0) . At the kth step, the solutions contained in
a ˜neighbourhood™ of the current solution x (k) are enumerated. If there are feasible
solutions less costly than the current solution x (k) , the best solution of the neigh-
bourhood is taken as the new current solution x (k+1) and the procedure is iterated.
Otherwise, the procedure is stopped (the last current solution is a local optimum).

Step 0. (Initialization). Let x (0) be the initial feasible solution and let N(x (0) ) be its
neighbourhood. Set h = 0.

Step 1. Enumerate the feasible solutions belonging to N(x (h) ). Select the best fea-
sible solution x (h+1) ∈ N (x (h) ).

Step 2. If the cost of x (h+1) is less than that of x (h) , set h = h + 1 and go back to
Step 1; otherwise, STOP, x (h) is the best solution found.


i j 2


3 34.0
12.2 7


4 6

Figure 7.12 Eulerian multigraph generated by the Christo¬des heuristic in the Saint-Martin
problem (minimum cost spanning tree edges are full lines and minimum-cost matching edges
are dashed lines).

i j 2


3 34.0


56.5 30.9
4 6

Figure 7.13 Hamiltonian cycle provided by the Christo¬des algorithm
in the Saint-Martin problem.

For the STSP, N (x (h) ) is commonly de¬ned as the set of all Hamiltonian cycles
that can be obtained by substituting k edges (2 k |V |) of x (h) for k other edges
in E (k-exchange) (Figure 7.14).
Step 0. Let C (0) be the initial Hamiltonian cycle and let zSTSP be the cost of C (0) .
Set h = 0.

Step 1. Identify the best feasible solution C (h+1) that can be obtained through a
(h+1) (h)
k-exchange. If zSTSP < zSTSP , STOP, C (h) is a Hamiltonian cycle for the STSP.


Figure 7.14 A feasible 3-exchange (dotted edges are removed, dashed edges are inserted).

Step 2. Let h = h + 1 and go back to Step 1.
In a local search algorithm based on k-exchanges, k can be constant or can be
dynamically increased in order to intensify the search when improvements are likely
to occur. If k is constant, each execution of Step 1 requires O(|V |k ) operations. In
general, k is set equal to 2 or 3 at most, in order to limit the computational effort.

If a 2-exchange procedure is applied to the solution provided by the Christo¬des
heuristic in the Saint-Martin problem, a less costly Hamiltonian cycle (see Figure 7.15)
is obtained at the ¬rst iteration by replacing edges (0,4) and (1,3) with edges (0,1)
and (3,4). As a consequence, the solution cost decreases by 14.8 km.

7.4 The Node Routing Problem with Capacity and
Length Constraints
As illustrated in Section 7.2, in several settings operational constraints come into
play when designing vehicle routes. These restrictions lead to a large number of
variants and the algorithms described in the literature are often dependent on the type
of constraint. For this reason, in the remainder of the chapter the most important
constrained NRPs are examined and a limited number of techniques, representative
of the most-used approaches, are described. As usual, the interested reader should
consult the references listed at the end of the chapter for further information.
The node routing problem with capacity and length constraints (NRPCL) consists
of designing a set of m least-cost vehicle routes starting and ending at the depot, such


i j 2


3 34.0



4 6

Figure 7.15 Best 2-exchange neighbour of the STSP feasible solution in Figure 7.13.

• each customer is visited exactly once;
• with each customer i is associated a demand pi (demands are either collected
or delivered, but not both); then the total demand of each vehicle cannot exceed
a given vehicle capacity q (vehicles are assumed to be identical) (capacity
• with each customer is associated a service time si ; then the total duration of
each route, including service and travel times, may not exceed a given work
shift duration T .
This problem can be formulated on a complete directed graph G = (V , A ) or on
a complete undirected graph G = (V , E ) depending on whether the cost matrix is
asymmetric or symmetric. In both cases, the vertex set V is composed of the depot
0 and the customers in U . In what follows, the focus is on the symmetric version of
the problem.
The NRPCL can be formulated by suitably modifying the STSP model.
cij xij
(i,j )∈E

subject to
xij + xj i = 2, j ∈ U, (7.17)
i∈V :(i,j )∈E i∈V :(j,i)∈E

x0i = 2m, (7.18)
i∈V :(0,i)∈E

xij + S ⊆ V \ {0}, |S|
xj i 2±(S), 2, (7.19)
(i,j )∈E :i∈S,j ∈S (j,i)∈E :i∈S,j ∈S
/ /


xij + S ⊆ V \ {0}, |S|
xj i 2, tSTSP (S) > T ,
(i,j )∈E :i∈S,j ∈S (j,i)∈E :i∈S,j ∈S
/ /
xij ∈ {0, 1}, (i, j ) ∈ E .
Constraints (7.17) state that two edges are incident to each customer j ∈ U (cus-
tomer degree constraints). Similarly, constraints (7.18) guarantee that 2m edges are
incident to vertex 0 (depot degree constraints). Capacity constraints (7.19) impose
that the number of vehicles serving customers in S is at least a lower bound ±(S) on the
optimal solution value of a 1-BP problem with |S| items having weights pi , i ∈ S and
bins of capacity q. In practice, it is common to use ±(S) = ( i∈S pi )/q . Length
constraints (7.20) state that a single route is not suf¬cient to serve all the customers in

S whenever the duration tSTSP (S) of a least-cost Hamiltonian cycle spanning S ∪ {0}
exceeds T .

Set partitioning formulation. An alternative formulation of the NRPCL can be
obtained as follows. Let K be the set of routes in G satisfying the capacity and length
constraints and let ck , k ∈ K, be the cost of route k. De¬ne aik , i ∈ V , k ∈ K, as
a binary constant equal to 1 if vertex i is included into route k, and to 0 otherwise.
Let yk , k ∈ K, be a binary decision variable equal to 1 if route k used in an optimal
solution, and to 0 otherwise. The NRPCL can be reformulated as a set partitioning
problem (NRPSP) in the following way.
ck yk

subject to

aik yk = 1, i∈V , (7.21)

yk = m, (7.22)
yk ∈ {0, 1}, k ∈ K.

Constraints (7.21) establish that each customer i ∈ V must be served, while
constraint (7.22) requires that exactly m vehicles are used.
The NRPSP is very ¬‚exible as it can be easily modi¬ed in order to include additional
operational constraints. Its main weakness is the large number of variables, especially
for ˜weakly constrained™ problems. For example, if pi = 1, i ∈ U , and the length
constraints are not binding, |K| = O( h=1 |V |/ h). Consequently, even if |U | = 50
and q = 10, there can be several billion variables. However, in some applications
the characteristics of the operational constraints can considerably reduce |K|. This
happens very often, for example, in fuel distribution where the demand of a user
i ∈ U (a gas pump) is customarily a small part (usually a half or a third) of a vehicle


Table 7.3 Orders (in hectolitres) received by Bengalur Oil.

Gas station Orders

1 50
2 75
3 50
4 50
5 75

Table 7.4 Distance (in kilometres) between the gas stations and the ¬rm™s depot
in the Bengalur Oil problem (depot corresponds to vertex 0).

0 1 2 3 4 5

0 0 90 100 90 80 80
1 90 0 10 20 10 30
2 100 10 0 10 20 40
3 90 20 10 0 10 30
4 80 10 20 10 0 20
5 80 30 40 30 20 0

capacity. Therefore, the customers visited in each route can be three at most. As a
|V | |V | |V |
|K| = O + + = O(|V |3 ).
3 2 1
It is easy to show (see Problem 7.6) that constraints (7.21) can be replaced with the
following relations,
aik yk 1, i ∈ V ,

in which case an easier-to-solve set covering formulation (NRPSC) is obtained.
Finally, both the NRPSP and NRPSC models can be used to generate a heuristic
solution by including only a limited number K ‚ K of feasible routes in the model.

Bengalur Oil manufactures and distributes fuel to ¬lling stations in the Karnataka
region (India). Last 2 July, the ¬rm received ¬ve orders (see Table 7.3). The distances
between the gas stations and the ¬rm™s depot are reported in Table 7.4. The vehicles
have a capacity of 150 hectolitres. In order to formulate the problem as an NRPSC,
the feasible routes are enumerated (Table 7.5).
The NRPSC model is as follows.


Table 7.5 Feasible routes in the Bengalur Oil problem (costs are expressed in kilometres).

Route Vertices Cost Route Vertices Cost

{0,1,0} {0,1,5,0}
1 180 9 200
{0,2,0} {0,2,3,0}
2 200 10 200
{0,3,0} {0,2,4,0}
3 180 11 200
{0,4,0} {0,2,5,0}
4 160 12 220
{0,5,0} {0,3,4,0}
5 160 13 180
{0,1,2,0} {0,3,5,0}
6 200 14 200
{0,1,3,0} {0,4,5,0}
7 200 15 180
{0,1,4,0} {0,1,3,4,0}
8 180 16 200


180y1 + 200y2 + 180y3 + 160y4 + 160y5 + 200y6 + 200y7 + 180y8
+ 200y9 + 200y10 + 200y11 + 220y12 + 180y13 + 200y14 + 180y15 + 200y16
subject to
y1 + y6 + y7 + y8 + y9 + y16 1,
y2 + y6 + y10 + y11 + y12 1,
y3 + y7 + y10 + y13 + y14 + y16 1,
y4 + y8 + y11 + y13 + y15 + y16 1,
y5 + y9 + y12 + y14 + y15 1,
y1 , y2 , y3 , y4 , y5 , y6 , y7 , y8 , y9 , y10 , y11 , y12 , y13 , y14 , y15 , y16 ∈ {0, 1}.
— —
In the optimal solution, the 12th and the 16th routes are used (y12 = y16 = 1) (see
Figure 7.16), and the total distance covered by the vehicles is 420 km.

7.4.1 Constructive heuristics
In the remainder of this section, some constructive procedures for the NRPCL are

˜Cluster ¬rst, route second™ heuristics. Cluster ¬rst, route second heuristics at-
tempt to determine a good NRPCL solution in two steps. First, customers are par-
titioned into subsets Uk ‚ V \ {0}, each of which is associated with a vehicle
k = 1, . . . , m. Second, for each vehicle k = 1, . . . , m, the STSP on the complete
subgraph induced by Uk ∪ {0} is solved (exactly or heuristically). The partitioning of
the customer set can be made visually or by more formalized procedures (as the one


i j

40 2





Figure 7.16 Optimal solution of the Bengalur Oil problem.

proposed by Fisher and Jaikumar). Readers interested in a deeper examination of this
subject are referred to the references listed at the end of the chapter.

In the Bengalur Oil problem, customers can be partitioned into two clusters:

U1 = {2, 5},
U2 = {1, 3, 4}.

Then, two STSPs are solved on the complete subgraphs induced by U1 ∪ {0} and
U2 ∪ {0}, respectively. The result of this ˜cluster ¬rst, route second™ procedure is
shown in Figure 7.16 (the total transportation cost is equal to 420 km).

˜Route ¬rst, cluster second™ heuristics. Route ¬rst, cluster second heuristics at-
tempt to determine an NRPCL solution in two stages. First, a single Hamiltonian


. 11
( 15)