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.

TLFeBOOK

TLFeBOOK

7

Planning and Managing

Short-Haul Freight

Transportation

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)

TLFeBOOK

248 SHORT-HAUL FREIGHT TRANSPORTATION

Pickup routes based

Plant

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.

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 249

3

4 8

2

5 9

Street A Street B

1 10

6

7

Street C

(a)

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

TLFeBOOK

250 SHORT-HAUL FREIGHT TRANSPORTATION

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

capacity;

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

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 251

B B

L

L

B

L

Depot

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,

TLFeBOOK

252 SHORT-HAUL FREIGHT TRANSPORTATION

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

analysis.

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.

cij

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.

Minimize

cij xij

(i,j )∈A

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 253

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

Minimize

cij xij

i∈V j ∈V

subject to

xij = 1, j ∈V ,

i∈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 .

TLFeBOOK

254 SHORT-HAUL FREIGHT TRANSPORTATION

—

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

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 255

i j 20 23

dij

0.2 0.7

0.2 1.4

8

1.0

6 1.0

1.9 19

0.5

22

7 16

3 0.7 0.5

0.5 1.0

0.6

17 21

5 0.6 0.9

0.5

1.6 9 1.0

0.5 2.0

0.9

0.9 15

0.7 10

1.8 12 18

4

2 0.5

0.4 11

0.5 1.3

1.1 0.5

1.6

2.1 14 0.9

1.0

13

1 0

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

cij

2.3

2.3

22

3

3.2

1.6 9

18

4

4.1

1.3

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.

TLFeBOOK

256 SHORT-HAUL FREIGHT TRANSPORTATION

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

2.3

22

3

9

3.3

1.6

18

4 4.2

4.1

1.3

2.1

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

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 257

i j 20

cij

2.3

2.9

22

3

9

3.0

1.6

18

4 4.2

4.1

1.3

2.1

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,

—

zATSP ’ zAP

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

TLFeBOOK

258 SHORT-HAUL FREIGHT TRANSPORTATION

Minimize

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 .

xij

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

Minimize

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:

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 259

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

Betteville Bolbec Dieppe F´ camp Le Havre Luneray Rouen Valmont

e

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.

Minimize

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

TLFeBOOK

260 SHORT-HAUL FREIGHT TRANSPORTATION

i j 2

cij

18.8

5

3 34.0

12.2

7

51.6

21.6

1

28.8

0

27.9

30.9

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

j

j

where

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

k

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

1

βk = k = 1, . . . .

,

k

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 261

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 ;

j

β 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

zSTSP ’ LB

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

TLFeBOOK

262 SHORT-HAUL FREIGHT TRANSPORTATION

i j 2

cij

18.8

5

3 12.2

60.4

7

39.4

21.6

77.2

1

0

27.9

30.9

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

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 263

1 1

0

0

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

zSTSP ’ LB

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

TLFeBOOK

264 SHORT-HAUL FREIGHT TRANSPORTATION

i j 2

cij

18.8

5

3 34.0

12.2

60.4

12.2 7

21.6

1

28.8

0

27.9

28.8

30.9

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

cij

18.8

5

3 34.0

12.2

60.4

7

25.6

1

28.8

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

(0)

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.

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 265

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

that

TLFeBOOK

266 SHORT-HAUL FREIGHT TRANSPORTATION

i j 2

cij

18.8

5

3 34.0

12.2

7

60.4

39.4

1

0

27.9

28.8

30.9

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

constraints);

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

Minimize

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

/ /

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 267

—

xij + S ⊆ V \ {0}, |S|

xj i 2, tSTSP (S) > T ,

4,

(i,j )∈E :i∈S,j ∈S (j,i)∈E :i∈S,j ∈S

/ /

(7.20)

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.

Minimize

ck yk

k∈K

subject to

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

k∈K

yk = m, (7.22)

k∈K

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

q

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

TLFeBOOK

268 SHORT-HAUL FREIGHT TRANSPORTATION

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

consequence,

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

k∈K

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.

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 269

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

Minimize

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

illustrated.

˜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

TLFeBOOK

270 SHORT-HAUL FREIGHT TRANSPORTATION

i j

cij

5

40 2

80

100

1

20

90

3

0

10

80

4

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