STSP algorithm. Then, the cycle is decomposed into m feasible routes, originating

and terminating at the depot. The route decomposition can be performed visually

or by means of formalized procedures, like the one proposed by Beasley. Readers

interested in this method should consult the references listed at the end of the chapter.

Applying a ˜route ¬rst, cluster second™ procedure to the Bengalur Oil problem, a

Hamiltonian cycle, having cost equal to 240 km, is generated (Figure 7.17). At the

second stage, the cycle is decomposed into two feasible routes, which are the same

as those illustrated in Figure 7.16.

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 271

i j

40

5 cij

2

10

80

1

20

3

0

10

80

4

Figure 7.17 Hamiltonian cycle generated at the ¬rst step of the ˜route ¬rst, cluster second™

procedure in the Bengalur Oil problem.

Savings heuristic. The savings heuristic is an iterative procedure that initially gen-

erates |U | distinct routes each of which serves a single customer. At each subsequent

iteration, the algorithm attempts to merge a pair of routes in order to obtain a cost

reduction (a saving). The cost saving sij achieved when servicing customers i and j ,

i, j ∈ U on one route, as opposed to servicing them individually, is (see Figure 7.18)

sij = c0i + c0j ’ cij , i, j ∈ V \ {0}}, i = j. (7.23)

It is worth noting that sij , i, j ∈ V \ {0}, are nonnegative since the triangle inequality

holds for all costs cij , i, j ∈ E . The savings formula still holds if i ∈ U is the last

customer of the ¬rst route involved in a merge, and j ∈ U is the ¬rst customer of the

second route. The algorithm stops when it is no more possible to merge feasibly a

pair of routes.

Step 0. (Initialization). Let C be the set of |U | initial routes Ci = {0, i, 0}, i ∈

V \ {0}. For each pair of vertices i, j ∈ V \ {0}, i = j , compute the saving sij

by using Equations (7.23). Let L be the list of savings sorted in a nonincreasing

fashion (since sij = sj i , i, j ∈ V \ {0}, i = j , then the list L contains only one

saving value for each pair of different customers).

Step 1. Extract from the top of list L a saving sij . If vertices i and j belong to two

separate routes of C in which i and j are directly linked to the depot (Figure 7.19),

and if the route obtained by replacing edges (0, i) and (0, j ) with edge (i, j ) is

feasible, then merge the two routes and update C.

Step 2. If L = …, STOP, it is not possible to merge further pairs of routes. If L = …,

go back to Step 1.

The computational complexity of the algorithm is determined by the saving sorting

phase and is therefore O(|V |2 log |V |2 ) = O(|V |2 log |V |). In practice, the algo-

TLFeBOOK

272 SHORT-HAUL FREIGHT TRANSPORTATION

j j

c0j c0j c0j cij

c0i

i i

0 0

c0i c0i

(a) (b)

Figure 7.18 Computation of saving sij : (a) the cost of the two individual routes is

2c0i + 2c0j ; (b) the cost of the merged route is c0i + c0j ’ cij .

j j

cij

c0j

i i

c0i

0

0

(a) (b)

Figure 7.19 Merging two routes in a single route (the saving sij = c0i + c0j ’ cij ).

rithm is very fast as it takes less than a second on the most common computers to

solve a problem with hundreds of customers. However, the quality of the solutions

can be poor. According to extensive computational experiments, the error made by

the savings algorithm is typically in the 5“20% range.

The savings method is very ¬‚exible since it can easily be modi¬ed to take into

account additional operational constraints (such as customer time window restric-

tions). However, with such variations, solution quality can be very poor. For this

reason, tailored procedures are usually employed when dealing with constraints dif-

ferent from capacity and length constraints.

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 273

Table 7.6 Savings sij , i, j ∈ V \ {0}, i = j , in the Bengalur Oil problem.

1 2 3 4 5

1 ” 180 160 160 140

2 ” 180 160 140

3 ” 160 140

4 ” 140

5 ”

By applying the savings algorithm to the Bengalur Oil problem, ¬ve individual

routes are initially generated:

C1 = {0, 1, 0},

C2 = {0, 2, 0},

C3 = {0, 3, 0},

C4 = {0, 4, 0},

C5 = {0, 5, 0}.

Then savings sij , i, j ∈ V \ {0}, i = j , are calculated (see Table 7.6) and list L is

initialized:

L = {s12 , s23 , s13 , s14 , s24 , s34 , s15 , s25 , s35 , s45 }.

Subsequently, routes C1 and C2 are merged while savings s23 , s13 , s14 , s24 are dis-

carded. Then, saving s34 is implemented by merging routes C3 and C4 . At this stage

there are no further feasible route merges. The ¬nal solution has a cost of 540 km (see

Figure 7.20).

7.5 The Node Routing and Scheduling Problem with

Time Windows

In several settings, customers need to be serviced within speci¬ed time windows.

This is the case, for example, with retail outlets that cannot be replenished during

busy periods. In the simplest version of the node routing and scheduling problem

with time windows (NRSPTW), each customer speci¬es a single time window, while

in other variants each customer can set multiple time windows (e.g. a time window

in the morning and one in the afternoon). Let ei , i ∈ U , be the earliest time at which

service can start at customer i, and let li , i ∈ U , be the latest time (or deadline) at

which service must start at customer i. Similarly, let e0 be the earliest time at which

TLFeBOOK

274 SHORT-HAUL FREIGHT TRANSPORTATION

i j

cij

5

2

10

80

80 100

1

90

90 3

0

10

80

4

Figure 7.20 Solution provided by the savings algorithm for the Bengalur Oil problem.

vehicles can leave the depot, and let l0 be the deadline within which vehicles must

return to the depot. In the NRSPTW, the service starting time at each customer i ∈ U ,

is a decision variable bi . If a vehicle arrives too early at a customer j ∈ U , it has to

wait. Therefore, bj , j ∈ U , is given by

bj = max{ej , bi + si + tij }, j ∈ U,

where i is the customer visited just before j , tij is the quickest travel time between

customers i and j and si is the service time of customer i.

It is worth noting, that, even though travel costs and times are symmetric, a solution

is made up of a set of circuits, because of the time windows that do not allow reversals

of route orientations.

In the remainder of this section, a constructive procedure is illustrated for the

NRSPTW, while in Subsection 7.5.2 a tabu search procedure capable of providing

high-quality solutions to a large number of constrained NRPs is described.

7.5.1 An insertion heuristic

Insertion-type heuristics are among the most ef¬cient for the NRSPTW. In this section,

the I1 Solomon heuristic is described. The procedure builds a feasible solution by

constructing one route at a time. At each iteration the procedure decides which new

customer u— ∈ U has to be inserted in the current solution, and between which adjacent

customers i(u— ) and j (u— ) the new customer u— has to be inserted on the current route.

When choosing u— , the algorithm takes into account both the cost increase associated

with the insertion of u— , and the delay in service time at customers following u— on

the route.

¯ ¯

Step 0. (Initialization). The ¬rst route is initially C1 = {0, i, 0}, where i is the cus-

tomer with the earliest deadline. Set k = 1.

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 275

Step 1. Let Ck = {i0 , i1 , . . . , im } be the current route, where i0 = im = 0. Set

u

f1 (ip’1 , u, ip ) = ±(cip’1 u + cuip ’ µcip’1 ip ) + (1 ’ ±)(bip ’ bip ), (7.24)

u

± 1, µ 0 and bip is the time when service begins at customer

where 0

ip provided that customer u is inserted between ip’1 and ip . For each unrouted

customer u, compute its best feasible insertion position in route Ck as

f1 (i(u), u, j (u)) = min f1 (ip’1 , u, ip ),

p=1,...,m

where i(u) and j (u) are the two adjacent vertices of the current route between

which u should to be inserted. Determine the best unrouted customer u— to be

inserted yielding

f2 (i(u— ), u— , j (u— )) = max{f2 (i(u), u, j (u)},

u

where

f2 (i(u), u, j (u)) = »c0u ’ f1 (i(u), u, j (u)) (7.25)

with » 0.

Step 2. Insert customer u— in route Ck between i(u— ) and j (u— ) and go back to Step 1.

If u— does not exist, but there are still unrouted customers, set k = k + 1, initialize

a new route Ck (as in Step 0) and go back to Step 1. Otherwise, STOP, a feasible

solution of the NRSPTW has been found.

The insertion heuristic tries to maximize the bene¬t obtained when servicing a

customer on the current route rather than on an individual route. For example, when

µ = ± = » = 1, Equation (7.25) corresponds to the saving in distance from servicing

customer u on the same route as customers i and j rather than using an individual

route. The best feasible insertion place of an unrouted customer is determined by

minimizing a measure, de¬ned by Equation (7.24), of the extra distance and the extra

time required to visit it. Different values of the parameters µ, ± and » lead to different

possible criteria for selecting the customer to be inserted and its best position in the

current route.

McNish is a chain of supermarkets located in Scotland. Last 13 October, the ware-

house situated in Aberdeen was required to serve 12 sales points located in Banchory,

Clova, Cornhill, Dufftown, Fyvie, Huntly, Newbyth, Newmill, Peterhead, Strichen,

Towie and Turriff. The number of requested pallets and the time windows within

which service was allowed are reported in Table 7.7, whereas distances and travel

times on the fastest routes between the cities are reported in Tables 7.8“7.11. Each

vehicle had a capacity of 30 pallets.

Each vehicle leaves the warehouse at 9:00 a.m. and must return to the warehouse

by 2:00 p.m. Service time (time needed for unloading a vehicle) can be assumed to

TLFeBOOK

276 SHORT-HAUL FREIGHT TRANSPORTATION

Table 7.7 Number of pallets and time windows for the sales point in the McNish problem.

Sales point Vertex Number of pallets Time window

Banchory 1 9 9:00 a.m. “ 11:30 a.m.

Clova 2 7 9:00 a.m. “ 12:30 a.m.

Cornhill 3 5 9:00 a.m. “ 12:30 a.m.

Dufftown 4 4 11:00 a.m. “ 2:30 a.m.

Fyvie 5 8 9:00 a.m. “ 12:30 a.m.

Huntly 6 8 11:00 a.m. “ 1:30 p.m.

Newbyth 7 7 9:00 a.m. “ 12:30 a.m.

Newmill 8 6 10:00 a.m. “ 12:30 a.m.

Peterhead 9 6 9:00 a.m. “ 10:30 a.m.

Strichen 10 6 9:00 a.m. “ 11:15 a.m.

Towie 11 4 10:00 a.m. “ 12:45 a.m.

Turriff 12 6 10:00 a.m. “ 12:30 a.m.

Table 7.8 Distance (in kilometres) between cities computed on the fastest route in

the McNish problem (Part I).

Aberdeen Banchory Clova Cornhill Dufftown Fyvie Huntly

Aberdeen 0.0 28.4 58.1 84.7 83.4 41.1 63.0

Banchory 28.4 0.0 48.1 89.7 76.1 52.7 67.9

Clova 58.1 48.1 0.0 46.3 34.1 48.6 24.5

Cornhill 84.7 89.7 46.3 0.0 36.8 34.9 23.2

Dufftown 83.4 76.1 34.1 36.8 0.0 53.8 21.8

Fyvie 41.1 52.7 48.6 34.9 53.8 0.0 33.4

Huntly 63.0 67.9 24.5 23.2 21.8 33.4 0.0

Newbyth 59.5 75.3 66.1 35.1 63.4 22.7 42.9

Newmill 31.8 36.8 48.6 55.2 64.4 21.0 43.9

Peterhead 51.5 82.5 95.3 70.0 100.4 50.2 79.9

Strichen 56.7 87.8 80.0 47.0 77.3 34.8 56.8

Towie 62.1 47.5 13.0 53.3 41.0 55.5 31.4

Turriff 55.1 66.7 51.9 21.0 49.2 14.2 28.7

be 15 min on average for every sales point, regardless of demand. For the sake of

simplicity, time is computed in minutes starting at 9:00 a.m. (for example, 11:00 a.m.

corresponds to 120 min). The I1 insertion procedure (with parameters ± = 0.9; µ =

» = 1) gave the following results. At the ¬rst iteration,

C1 = {0, 9, 0}.

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 277

Table 7.9 Distance (in kilometres) between cities computed on the fastest route in

the McNish problem (Part II).

Newbyth Newmill Peterhead Strichen Towie Turriff

Aberdeen 59.5 31.8 51.5 56.7 62.1 55.1

Banchory 75.3 36.8 82.5 87.8 47.5 66.7

Clova 66.1 48.6 95.3 80.0 13.0 51.9

Cornhill 35.1 55.2 70.0 47.0 53.3 21.0

Dufftown 63.4 64.4 100.4 77.3 41.0 49.2

Fyvie 22.7 21.0 50.2 34.8 55.5 14.2

Huntly 42.9 43.9 79.9 56.8 31.4 28.7

Newbyth 0.0 43.5 39.8 16.9 72.9 15.1

Newmill 43.5 0.0 50.3 43.9 52.7 34.9

Peterhead 39.8 50.3 0.0 24.7 100.6 47.8

Strichen 16.9 43.9 24.7 0.0 86.9 28.4

Towie 72.9 52.7 100.6 86.9 0.0 58.8

Turriff 15.1 34.9 47.8 28.4 58.8 0.0

Table 7.10 Travel times (in minutes) on the fastest routes between cities in

the McNish problem (Part I).

Aberdeen Banchory Clova Cornhill Dufftown Fyvie Huntly

Aberdeen 0 34 74 89 87 51 65

Banchory 34 0 58 96 87 63 72

Clova 74 58 0 56 42 70 31

Cornhill 89 96 56 0 43 42 27

Dufftown 87 87 42 43 0 65 26

Fyvie 51 63 70 42 65 0 43

Huntly 65 72 31 27 26 43 0

Newbyth 70 90 80 38 74 27 51

Newmill 37 44 61 68 67 28 44

Peterhead 58 88 117 80 113 63 90

Strichen 62 92 97 52 91 43 68

Towie 67 54 19 61 47 75 36

Turriff 67 79 64 27 58 16 35

For each unrouted customer u, its best feasible insertion position in route C1 is com-

puted, as reported in Table 7.12. Based on these evaluations, it is decided to insert

vertex 10 in C1 as follows:

C1 = {0, 9, 10, 0}.

TLFeBOOK

278 SHORT-HAUL FREIGHT TRANSPORTATION

Table 7.11 Travel times (in minutes) on the fastest routes between cities in

the McNish problem (Part II).

Newbyth Newmill Peterhead Strichen Towie Turriff

Aberdeen 70 37 58 62 67 67

Banchory 90 44 88 92 54 79

Clova 80 61 117 97 19 64

Cornhill 38 68 80 52 61 27

Dufftown 74 67 113 91 47 58

Fyvie 27 28 63 43 75 16

Huntly 51 44 90 68 36 35

Newbyth 0 54 49 21 84 18

Newmill 54 0 63 57 63 44

Peterhead 49 63 0 30 118 59

Strichen 21 57 30 0 102 35

Towie 84 63 118 102 0 69

Turriff 18 44 59 35 69 0

Then, two more customers are accommodated in route C1 :

C1 = {0, 9, 10, 7, 12, 0}.

At this stage the length of C1 is 163.3 km. Hence, a new route C2 is initialized:

C2 = {0, 1, 0}.

After three more iterations, C2 is

C2 = {0, 1, 8, 5, 3, 0},

with a distance of 205.8 km. Finally, route C3 is constructed,

C3 = {0, 11, 2, 4, 6, 0},

with a distance of 194.0 km. The ¬nal solution covers 563.1 km and corresponds to

the schedule reported in Tables 7.13“7.15.

7.5.2 A uni¬ed tabu search procedure for constrained node

routing problems

In recent years the ¬eld of heuristics has been transformed by the development of

tabu search (TS). This is essentially a local search method that generates a sequence

of solutions in the hope of generating better local optima. TS differs from classical

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 279

Table 7.12 Best feasible insertion positions in route C1 for each unrouted customer in

the McNish problem at the ¬rst iteration of the I1 algorithm.

u f1 (i, u, j ) i(u) j (u) f2 (i, u, j )

’48.41

2 106.51 9 0

’20.78

3 105.48 9 0

’51.37

4 134.77 9 0

’1.82

5 42.92 9 0

’30.46

6 93.46 9 0

7 50.62 9 0 8.88

’1.44

8 33.24 9 0

9 ” ” ” ”

10 31.81 9 0 24.89

’52.18

11 114.28 9 0

12 54.56 9 0 0.54

Table 7.13 Schedule of the ¬rst route in the McNish problem.

City Arrival Departure Cumulated load

Aberdeen ” 9:00 a.m. 0

Peterhead 9:58 a.m. 10:13 a.m. 6

Strichen 10:43 a.m. 10:58 a.m. 12

Newbyth 11:19 a.m. 11:34 a.m. 19

Turriff 11:52 a.m. 12:07 p.m. 25

Aberdeen 1:14 p.m. ”

Table 7.14 Schedule of the second route in the McNish problem.

City Arrival Departure Cumulated load

Aberdeen ” 9:00 a.m. 0

Banchory 9:34 a.m. 9:49 a.m. 9

Newmill 10:33 a.m. 10:48 a.m. 15

Fyvie 11:16 a.m. 11:31 a.m. 23

Cornhill 12:13 a.m. 12:28 a.m. 28

Aberdeen 1:57 p.m. ”

methods in that the successive solutions it examines do not necessarily improve upon

each other. A key concept at the heart of TS is that of neighbourhood. The neighbour-

hood N(s) of a solution s is the set of all solutions that can be reached from s by

performing a simple operation. For example, in the context of the NRP, two common

TLFeBOOK

280 SHORT-HAUL FREIGHT TRANSPORTATION

Table 7.15 Schedule of the third route determined for the McNish problem.

City Arrival Departure Cumulated load

Aberdeen ” 9:00 a.m. 0

Towie 10:07 a.m. 10:22 a.m. 4

Clova 10:41 a.m. 10:56 a.m. 11

Dufftown 11:38 a.m. 11:53 a.m. 15

Huntly 12:19 a.m. 12:34 a.m. 23

Aberdeen 1:39 p.m. ”

neighbourhood structures are obtained by moving a customer from its current route

to another route or by swapping two customers between two different routes. The

standard TS mechanism is to move from s to the best neighbour in N(s). This way of

proceeding may, however, induce cycling. For example, s may be the best neighbour

of s which, in turn, is the best neighbour of s . To avoid cycling the search process is

prevented from returning to solutions processing some attributes of solutions already

considered. Such solutions are declared tabu for a number of iterations. For example,

if a customer v is moved from route r to route r at iteration t, then moving v back

to route r will be declared tabu until iteration t + θ, where θ is called the length

of the tabu tenure (typically θ is chosen between 5 and 10). When the tabu tenure

has expired, v may be moved back to route r at which time the risk of cycling will

most likely have disappeared because of changes that have occurred elsewhere in the

solution.

Not only is it possible to accept deteriorating solutions in TS, but it may also be

interesting to consider infeasible solutions. For example, in the sequence of solutions

s, s , s , both s and s may be feasible while s is infeasible. If s cannot be reached

directly from s, but only from s , and if it improves upon s, then it pays to go through the

infeasible solution s . This can occur if, for example, s contains a route r that violates

vehicle capacity due to the inclusion of a new customer in that route. Feasibility may

be restored at the next iteration if a customer is removed from route s . A practical way

of handling infeasible solutions in TS is to work with a penalized objective function.

If f (s) is the actual cost of solution s, then the penalized objective is de¬ned as

f (s) = f (s) + ±Q(s) + βD(s) + γ W (s), (7.26)

where Q(s), D(s), W (s) are the total violations of the vehicle capacity constraints,

route duration constraints and time window constraints, respectively. Other types of

constraints can of course be handled in the same way. The parameters ±, β and γ are

positive weights associated with constraint violations. These parameters are initially

set equal to 1 and self-adjust during the course of the search to produce a mix of

feasible and infeasible solutions. For example, if at a given iteration s is feasible with

respect to the vehicle capacity constraint, then dividing ± by a factor 1 + δ (where

δ > 0) will increase the likelihood of generating an infeasible solution at the next

iteration. Conversely, if s is infeasible, multiplying ± by 1 + δ will help the search

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 281

move to a feasible solution. A good choice of δ is typically 0.5. The same principle

applies to β and γ .

The algorithm repeatedly performs these operations starting from an initial solution

which may be infeasible. It stops after a preset number of iterations. As is common

in TS, this number can be very large (e.g. several thousands).

The article by Cordeau, Laporte and Mercier quoted at the end of this chapter

illustrates how this implementation of TS has been employed to generate high-quality

solutions for a large class of dif¬cult NRPs.

7.6 Arc Routing Problems

According to the de¬nition given in Section 7.2, an ARP consists of designing a least-

cost set of vehicles routes in a graph G(V , A, E), such that each arc and edge in a

subset R ⊆ A ∪ E should be visited. Unlike NRPs (which are formulated and solved

on an auxiliary complete graph G ), ARPs are generally modelled directly on G.

In this section, unconstrained ARPs, namely the CPP and the RPP, are examined.

Constrained ARPs can be approached using the algorithmic ideas employed for the

constrained NRPs along with the solution procedures for the CPP and the RPP. For

example, the ARP with capacity and length constraints, whose applications arise in

garbage collection and mail delivery, can be heuristically solved using a ˜cluster ¬rst,

route second™ approach: in a ¬rst stage, the required arcs and edges are divided into

clusters, each of which is assigned to a vehicle, while at a second stage an RPP is

solved for each cluster. In this textbook, constrained ARPs are not tackled for the sake

of brevity.

7.6.1 The Chinese postman problem

The CPP is to determine a minimum-cost route traversing all arcs and all edges of a

graph at least once. Its main applications arise in garbage collection, mail delivery,

network maintenance, snow removal and meter reading in urban areas.

The CPP is related to the problem of determining whether a graph G(V , A, E) is

Eulerian, i.e. whether it contains a tour traversing each arc and each edge of the graph

exactly once. Obviously, in an Eulerian graph with nonnegative arc and edge costs,

each Eulerian tour constitutes an optimal CPP solution. In a nonEulerian graph, an

optimal CPP solution must traverse at least one arc or edge twice.

Necessary and suf¬cient conditions for the existence of an Eulerian tour depend

on the type of graph G considered (directed, undirected or mixed), as stated in the

following propositions, whose proofs are omitted for brevity.

Property. A directed and strongly connected graph G is Eulerian if and only if it is

symmetric, i.e. for any vertex the number of incoming arcs (incoming semi-degree)

is equal to the number of outgoing arcs (outgoing semi-degree) (symmetric vertex).

TLFeBOOK

282 SHORT-HAUL FREIGHT TRANSPORTATION

i j

Figure 7.21 A mixed Eulerian graph which is not symmetric.

Property. An undirected and connected graph G is Eulerian if and only if it is even,

i.e. each vertex has an even degree (even vertex).

Property. A mixed and strongly connected graph G is Eulerian if and only if

(a) the total number of arcs and of edges incident to any vertex is even (even graph);

(b) for each set S of vertices (S ‚ V and S = …), the difference between the

number of the arcs traversing the cut (S, V \ S) in the two directions is less

than or equal to the number of edges of the cut (balanced graph).

Furthermore, since an even and symmetric graph is balanced, the following propo-

sition holds.

Property. A mixed, strongly connected, even and symmetric graph G is Eulerian.

This condition is suf¬cient, but not necessary, as illustrated in the example reported

in Figure 7.21.

The solution of the CPP can be decomposed in two steps.

Step 1. De¬ne a least-cost set of arcs A(a) and of edges E (a) such that the multigraph

G(a) = (V , A ∪ A(a) , E ∪ E (a) ) is Eulerian (if G is itself Eulerian, then A(a) = …

and E (a) = … and, therefore, G = G(a) ).

Step 2. Determine an Eulerian tour in G(a) .

The ¬rst step of the procedure can be executed in polynomial time if G is a directed

or undirected graph, while it results in an NP-hard algorithm if G is mixed. The second

step can be performed in O(|A ∪ E|) time with the following end-pairing procedure.

Step 1. Determine a covering of the edges and arcs of G(a) through a set C of tours,

in such a way that an edge/arc is traversed exactly once.

Step 2. If |C| = 1, STOP, the tour obtained is Eulerian.

Step 3. Determine two tours in C which contain at least one common vertex. Merge

the two tours, update C and go back to step 1.

In step 1, a tour in G(a) can be obtained by visiting the multigraph randomly until

the initial vertex is included twice. Then, the edges/arcs of the tour are removed. In

the new multigraph a new tour can be looked for.

In the sequel it is shown how to determine G(a) in the cases where G is directed or

undirected.

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 283

Directed Chinese postman problem. When G is directed, in an optimal solution

the arcs in A(a) form a set of least-cost paths connecting the asymmetric vertices.

Therefore A(a) can be obtained by solving a minimum-cost ¬‚ow problem (a trans-

portation problem, see Section 3.4) on a bipartite directed graph suitably de¬ned.

Let V + and V ’ be the subsets of V whose vertices have a positive and a negative

difference between the incoming semi-degree and the outgoing semi-degree, respec-

tively. The bipartite directed graph is GT (V + ∪ V ’ , AT ), where AT = {(i, j ) : i ∈

V + , j ∈ V ’ }.

With each arc (i, j ) ∈ AT is associated a cost wij equal to that of a least-cost

path in G from vertex i to vertex j . Let also oi (> 0), i ∈ V + , be the supply of the

vertex i, equal to the difference between its incoming semi-degree and its outgoing

semi-degree. Similarly, let di (> 0), i ∈ V ’ , be the demand of vertex i, equal

to the difference between its outgoing semi-degree and its incoming semi-degree.

Furthermore, let sij , (i, j ) ∈ AT , be the decision variable associated with the ¬‚ow

along arc (i, j ). The transportation problem is as follows.

Minimize

wij sij

minimize (7.27)

(i,j )∈AT

subject to

i ∈ V +,

sij = oi , (7.28)

j ∈V ’

j ∈ V +,

sij = dj , (7.29)

i∈V +

(i, j ) ∈ AT .

sij 0, (7.30)

Of course, i∈V + oi = j ∈V ’ dj , so that problem (7.27)“(7.30) is feasible. Let

— (i, j ) ∈ AT , be an optimal (integer) solution of the transportation problem. A(a)

sij ,

is formed by the arcs (r, s) ∈ A belonging to the least-cost paths associated with the

—

arcs (i, j ) ∈ AT such that sij > 0 ((r, s) is taken sij times).

In the directed graph G(V , A) shown in Figure 7.22, the differences between the

incoming and outgoing semi-degrees of vertices 0, 1, 2, 3, 4 and 5 are ’1, 0, 1, 0,

1, ’1, respectively. The least-cost paths from vertex 2 to vertex 0 and from vertex

2 to vertex 5 are given by the sequences of arcs {(2,3), (3,4), (4,5), (5,0)} (of cost

equal to 109) and {(2,3), (3,4), (4,5)} (of cost equal to 86), respectively. Similarly,

the least-cost path from vertex 4 to vertex 0 is formed by {(4,5), (5,0)}, of cost 51,

while the least-cost path from vertex 4 to vertex 5 is given by arc (4,5) whose cost is

equal to 28. We can therefore formulate the transportation problem on the bipartite

directed graph GT (V + ∪ V ’ , AT ) represented in Figure 7.23. The optimal solution

to the transportation problem is

— — — —

s20 = 0, s25 = 1, s40 = 1, s45 = 0.

TLFeBOOK

284 SHORT-HAUL FREIGHT TRANSPORTATION

10

1 2 i j

cij

37

18

3

43

0

26

21

23

28

5 4

25

Figure 7.22 A directed graph G(V , A).

i j

wij

’dj

oi

109

2 0

’1

1

86 51

’1

1

4 5

28

Figure 7.23 Bipartite directed graph GT (V + ∪ V ’ , AT ) associated

with graph G in Figure 7.22.

Therefore, set A(a) is formed by the arcs of the least-cost paths from vertex 2 to

vertex 5 and from vertex 4 to vertex 0. Adding such arcs to the directed graph G,

a least-cost Eulerian multigraph is obtained (Figure 7.24). Hence, an optimal CPP

solution of cost 368 is de¬ned by the following arcs:

{(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0), (0, 4),

(4, 2), (2, 3), (3, 4), (4, 5), (5, 4), (4, 5), (5, 0)}.

In this solution some arcs are traversed more than once (for example, arc (4,5)), but

on these arcs it is performed only once.

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 285

10

1 2 i j

cij

37

18

3

0 43

26

21

23

28

5 4

25

Figure 7.24 Least-cost Eulerian multigraph associated with

the directed graph G in Figure 7.22.

Undirected Chinese postman problem. When G is undirected, the set E (a) can

be obtained as a solution of a matching problem on an auxiliary graph GD (VD , ED ).

VD is the set of odd vertices in G (VD is formed by an even number of vertices) and

ED = {(i, j ) : i ∈ VD , j ∈ VD , i = j }. With each edge (i, j ) ∈ ED is associated a

cost wij equal to that of a least-cost chain in G between vertices i and j . The set E (a)

is therefore obtained as the union of the edges which are part of the least-cost chains

associated with the edges of the optimal matching on GD .

Welles is in charge of maintaining the road network of Wales (Great Britain).Among

other things, the company has to monitor periodically the roads in order to locate craps

and potholes in the asphalt. To this purpose, the road network has been divided into

about 10 subnetworks, each of which has to be visited every 15 days by a dedicated

vehicle. The graph representing one such subnetwork is shown in Figure 7.25. In

order to determine the optimal undirected CPP solution, a minimum-cost matching

problem between the odd-degree vertices (vertices 2, 3, 6, 7, 9 and 11) is solved. The

optimal matching is 2“3, 6“7, 9“11. The associated set of chains in G is (2,3), (6,7)

and (9,11) (total cost is 7.5 km). Adding these edges to G, the Eulerian multigraph in

Figure 7.26 is obtained.

Finally, by using the end-pairing procedure, the optimal undirected CPP solution

is obtained:

{(0, 1), (1, 3), (3, 2), (2, 5), (5, 4), (4, 3), (3, 2), (2, 0),

(0, 6), (6, 7), (7, 8), (8, 5), (5, 6), (6, 7), (7, 9), (9, 11),

(11, 10), (10, 8), (8, 9), (9, 11), (11, 12), (12, 9), (9, 0)}

(total cost is 52.8 km, the cost of the edges of G, plus 7.5 km). In this solution, edges

(2, 3), (6, 7) and (9, 11) are traversed twice.

TLFeBOOK

286 SHORT-HAUL FREIGHT TRANSPORTATION

1 i j

cij

1.0

2.7 4

3

3.5

10

1.3

1.0

1.1

2.5

5 2.9

2 11

3.5

1.5 8

1.5

2.4 4.1 1.3

6 7 1.5

2.4

1.5

2.7

0 9 12

1.6 5.3

Figure 7.25 Graph representation used in the Welles problem.

Costs cij , (i, j ) ∈ E, are in kilometres.

1 i j

cij

1.0

4

2.7

3

3.5

10

1.3

1.0

1.0

1.1

2.5 5 2.9

2 11

3.5

1.5 8

4.1

1.5

2.4 1.3

2.4 4.1

6 7 1.5

2.4

1.5

2.7

0 9 12

1.6 5.3

Figure 7.26 Least-cost Eulerian multigraph in the Welles problem.

7.6.2 The rural postman problem

The RPP is to determine in a graph G(V , A, E) a least-cost route traversing a subset

R ⊆ A ∪ E of required arcs and edges at least once. Its applications arise in garbage

collection, mail delivery, network maintenance, snow removal and meter reading in

scarcely populated areas.

Let G1 (V1 , A1 , E1 ), . . . , Gp (Vp , Ap , Ep ) be the p connected components of

graph G(V , R) induced by the required arcs and edges (see Figures (7.27) and (7.28)).

The RPP solution can be obtained in two steps.

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 287

5

4 6

1 2 3 8

7

0

Figure 7.27 A mixed graph G(V , A, E).

6

1 2 8

7

0

Figure 7.28 Connected components induced by the required arcs and

edges of graph G in Figure 7.27.

Step 1. Determine a least-cost set of arcs A(a) and edges E (a) such that the multigraph

G(a) = (V , (R © A) ∪ A(a) , (R © E) ∪ E (a) ) is Eulerian (see Figure 7.29).

Step 2. Determine an Eulerian tour in G(a) .

The ¬rst step is NP-hard even for directed and undirected graphs, if p > 1. For

p = 1, the RPP can be reduced to a CPP. The second step can be solved in polynomial

time with the end-pairing procedure. In what follows, the ¬rst stage of two constructive

heuristics is illustrated for directed and undirected graphs.

Directed rural postman problem. A heuristic solution to the directed RPP can be

obtained through the ˜balance-and-connect™ heuristic.

Step 1. Using the procedure employed for the directed CPP, construct a directed

symmetric graph G (a) (V , R ∪ A (a) ), by adding to G(V , R) a suitable set of least-

TLFeBOOK

288 SHORT-HAUL FREIGHT TRANSPORTATION

6

1 2 8

0 7

Figure 7.29 Least-cost Eulerian multigraph associated with graph G(V , R) of Figure 7.27.

cost paths between nonsymmetric vertices. If G (a) (V , R ∪ A (a) ) is connected,

STOP, G (a) = G(a) is Eulerian.

p) be the number of connected components of G (a) (V , R ∪

Step 2. Let p (1 < p

A (a) ). Construct an auxiliary undirected graph G(c) = (V (c) , E (c) ), in which there

is a vertex h ∈ V (c) for each connected component of G (a) , and, between each pair

of vertices h, k ∈ V (c) , h = k, there is an edge (h, k) ∈ E (c) . With edge (h, k) is

associated a cost ghk equal to

ghk = {wij + wj i },

min

i∈Vh ,j ∈Vk

where wij and wj i are the costs of the least-cost paths from vertex i to vertex

j and from vertex j to vertex i in G, respectively. Compute the minimum-cost

(c)

tree T (c) = (V (c) , ET ) spanning the vertices of graph G(c) . Construct a sym-

metric, connected and directed graph G(a) (V , R ∪ A (a) ∪ A (a) ) by adding to

G (a) (V , R ∪ A (a) ) the set of arcs A (a) belonging to the least-cost paths cor-

(c)

responding to the edges ET of the tree T (c) .

Step 3. Apply, when possible, the shortcuts method (see the Christo¬des algorithm

for the STSP) in order to reduce the solution cost.

The ˜balance and connect™ algorithm is applied to problem represented in Fig-

ure 7.30. The directed graph G(V , R) has ¬ve connected components of required

arcs. At the end of Step 1 (see Figure 7.31), A (a) is formed by arcs (2,1) (the least-

cost path from vertex 1 to vertex 2), (3,4) (the least-cost path from vertex 3 to vertex 4),

(5,6) (the least-cost path from vertex 5 to vertex 6), (8,9) and (9,11) (the least-cost

path from vertex 8 to vertex 11), and (10,7) (the least-cost path from vertex 10 to

vertex 7). At Step 2, V (c) = {1, 2, 3}, and the least-cost paths from vertex 1 to vertex

4 (arc (1,4) and vice versa (arc (4,1)), and from vertex 6 to vertex 7 (arc (6,7)) and vice

versa (arcs (7,2), (2,3) and (3,6)) are added to the partial solution (see Figure 7.32).

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 289

5 i j

cij

23

23

4 6

23 16

27

15

19 22 3 8 11

16

34 17

24

24

21

20

1 2 9

19

17

18

14 19

23 22

7 10

0

Figure 7.30 Directed graph G(V , A).

5 i j

cij

23 23

4 6

27 23

3 8 11

16 17

24

1 2 9

20 21

18 17

22

7 10

0

Figure 7.31 Directed graph G (a) (V , R ∪ A (a) ) obtained at the end of Step 1 of

the ˜balance and connect™ algorithm.

Finally, using the end-pairing procedure, the following circuit of cost 379 is obtained:

{(0, 2), (2, 1), (1, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9), (9, 11),

(11, 10), (10, 7), (7, 2), (2, 3), (3, 6), (6, 3), (3, 4), (4, 1), (1, 0)}.

It can be shown that in this case the ˜balance and connect™ solution is optimal.

TLFeBOOK

290 SHORT-HAUL FREIGHT TRANSPORTATION

5 i j

cij

23

23

4 6

23

27

15

19 22 3 8 11

16 17

34

24

24

21

20

1 2 9

18 17

14

22

0 7 10

Figure 7.32 Symmetric and connected directed graph G(a) (V , R ∪ A (a) ∪ A (a) )

obtained at the end of Step 2 of the ˜balance and connect™ algorithm.

Undirected rural postman problem. A heuristic solution to the undirected RPP

can be obtained through the Frederickson procedure.

Step 1. Using the matching procedure illustrated for the undirected CPP, construct

an even graph G (a) (V , R ∪ E (a) ). If G (a) (V , R ∪ E (a) ) is also connected, STOP,

G (a) = G(a) is Eulerian.

p) be the number of connected components of G (a) (V , R ∪

Step 2. Let p (1 < p

E (a) ). Construct an auxiliary undirected graph G(c) (V (c) , E (c) ), in which there is

a vertex h ∈ V (c) for each connected component of G (a) , and between each couple

of vertices h, k ∈ V (c) , h = k, there is an edge (h, k) ∈ E (c) . With each edge (h, k)

is associated a cost ghk equal to

ghk = {wij },

min

i∈Vh ,j ∈Vk

where wij is the cost of the least-cost path between vertices i and j in G. Com-

(c)

pute a minimum-cost tree T (c) = (V (c) , ET ) spanning the vertices of graph G(c) .

Construct an even and connected graph G(a) (V , R ∪ E (a) ∪ E (a) ) by adding to

R ∪ E (a) the set of edges E (a) (each of which taken twice) belonging to the

(c)

least-cost chains corresponding to the edges ET of tree T (c) .

Step 3. Apply, if possible, the shortcuts method (see the Christo¬des algorithm for

the STSP) in order to reduce solution cost.

Tracon distributes newspapers and milk door-to-door all over Wales. In the same

road subnetwork as in the Welles problem, customers are uniformly distributed along

some roads (represented by continuous lines in Figure 7.33). The entire demand of the

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 291

1 i j

cij

1.0

4

2.7

3

3.5

10

1.3

1.0

1.1

2.5

5 2.9

2 11

3.5

1.5 8

1.5

2.4 1.3

4.1

6 7 1.5

2.4

1.5

2.7

0 9 12

1.6 5.3

Figure 7.33 Graph G(V , E) associated with the Tracon problem (costs are in kilometres).

subnetwork can be served by a single vehicle. By applying the Frederickson heuris-

tic, the even and connected multigraph G(a) (V , R ∪ E (a) ) shown in Figure 7.34 is

obtained. Finally, by using the end-pairing procedure, the following cycle is gener-

ated:

{(0, 9), (9, 12), (12, 11), (11, 10), (10, 8), (8, 7), (7, 6),

(6, 5), (5, 4), (4, 3), (3, 1), (1, 3), (3, 2), (2, 5), (5, 6), (6, 0)

(total cost is 31.3 km). It is worth noting that edge (5,6) is traversed twice without

being served. It can be shown that the Frederickson solution is optimal.

7.7 Real-Time Vehicle Routing and Dispatching

As pointed out in Section 7.2, there exist several important short-haul transportation

problems that must be solved in real time. In this section, the main features of such

problems are illustrated.

In real-time VRDPs, uncertain data are gradually revealed during the operational

interval, and routes are constructed in an on-going fashion as new data arrive. The

events that lead to route modi¬cations can be

• the arrival of new user requests,

• the arrival of a vehicle at a destination,

• the update of travel times.

TLFeBOOK

292 SHORT-HAUL FREIGHT TRANSPORTATION

1 i j

cij

1.0

2.7 4

1.0

3

10

1.3

1.0

1.1

2.5

5 2.9

2 11

1.5 8

1.5

1.5

1.3

6 7

2.4

2.7

0 9 12

1.6 5.3

Figure 7.34 Even and connected multigraph G(a) (V , R ∪ E (a) ), obtained at the end of

Step 2 of the Frederickson algorithm applied to the Tracon problem.

Every event must be processed according to the policies set by the company or orga-

nization operating the ¬‚eet of vehicles. As a rule, when a new request is received, one

must decide whether it can be serviced on the same day, or whether it must be delayed

or rejected. If the request is accepted, it is assigned temporarily to a position in a vehi-

cle route. The request is effectively serviced as planned if no other event occurs in the

meantime. Otherwise, it can be assigned to a different position of the same vehicle

route, or even dispatched to a different vehicle. It is worth noting that at any time each

driver just needs to know his next stop. Hence, when a vehicle reaches a destination

it has to be assigned a new destination. Because of the dif¬culty of estimating the

current position of a moving vehicle, reassignments could not easily made until quite

recently. However, due to advances in vehicle positioning and communication tech-

nologies, route diversions and reassignments are now a feasible option and should

take place if this results in a cost saving or in an improved service level. Finally, if an

improved estimation of vehicle travel times is available, it may be useful to modify

the current routes or even the decision of accepting a request or not. For example, if

an unexpected traf¬c jam occurs, some user services can be deferred. If the demand

rate is low, it is sometimes useful to relocate idle vehicles in order to anticipate future

demands or to escape a forecasted traf¬c congestion.

Real-time problems possess a number of particular features, some of which have

just been described. In the following, the remaining characteristics are outlined.

Quick response. Algorithms for solving real-time VRDPs must provide a quick

response so that route modi¬cations can be transmitted timely to the ¬‚eet. To this

end, two approaches can be used: simple policies (like the FCFS), or more involved

algorithms running on parallel hardware. The choice between them depends mainly

on the objective, the degree of dynamism and the demand rate.

TLFeBOOK

SHORT-HAUL FREIGHT TRANSPORTATION 293

Denied or deferred service. In some applications it is valid to deny service to

some users, or to forward them to a competitor, in order to avoid excessive delays or

unacceptable costs. For instance, requests that cannot be serviced within a given time

windows are rejected.

Congestion. If the demand rate exceeds a given threshold, the system becomes

saturated, i.e. the expected waiting time of a request goes to in¬nity.

The degree of dynamism. Designing an algorithm for solving real-time VRDPs

depends to a large extent on how dynamic the problem is. To quantify this concept,

the degree of dynamism of a problem has been de¬ned. Let [0, T ] be the operational

interval and let ns and nd be the number of static and dynamic requests, respectively

(ns + nd = |U |). Moreover, let ti ∈ [0, T ] be the occurrence time of service request

of customer i ∈ U . Static requests are such that ti = 0, i ∈ U , while dynamic ones

have ti ∈ (0, T ], i ∈ U . The degree of dynamism δ can be simply de¬ned as

nd

δ=

ns + nd

and may vary between 0 and 1. Its meaning is straightforward. For instance, if δ is

equal to 0.3, then 3 customers out of 10 are dynamic. This de¬nition can be generalized

in order to take into account both dynamic request occurrence times and possible time

windows. For a given δ value, a problem is more dynamic if immediate requests occur

at the end of the operational interval [0, T ]. As a result, the measure of dynamism can

be generalized as follows:

nd

ti /T

δ = i=1 .

ns + n d

Again δ ranges between 0 and 1. It is equal to 0 if all user requests are known in

advance while it is equal to 1 if all user requests occur at time T . Finally, the de¬nition

of δ can be modi¬ed to take into account possible time windows on user service time.

Let ai and bi be the ready time and deadline of customer i ∈ U , respectively. Then,

nd

i=1 [T ’ (bi ’ ti )]/T

δ= .

ns + n d

It can be shown that δ also varies between 0 and 1. Moreover, it is worth noting that

if no time windows are imposed (i.e. ai = ti and bi = T for each customer i ∈ U ),

then δ = δ . As a rule, vendor-based distribution systems (such as those distributing

heating oil) are weakly dynamic. Problems faced by long-distance couriers and appli-

ance repair service companies are moderately dynamic. Finally, emergency services

exhibit a strong dynamic behaviour.

Objectives. In real-time VRDPs the objective to be optimized is often a combina-

tion of different measures. In weakly dynamic systems the focus is on minimizing

routing cost but, when operating a strongly dynamic system, minimizing the expected

TLFeBOOK

294 SHORT-HAUL FREIGHT TRANSPORTATION

response time (i.e. the expected time lag between the instant a user service begins and

its occurrence time) becomes a key issue. Another meaningful criterion which is often

considered (alone or combined with other measures) is throughput optimization, i.e.

the maximization of the expected number of requests serviced within a given period

of time.

7.8 Integrated Location and Routing

Facility location and vehicle routing are two of the most fundamental decisions in

logistics. Location decisions that are very costly and dif¬cult to change are said to

be strategic, e.g. those involving major installations such as factories, airports, ¬xed

transportation links, etc. Others are said to be tactical, because, while still being

relatively costly, they can still be modi¬ed after several years. Warehouse and store

location fall in that category. Finally, operational location decisions involve easily

movable facilities such as parking areas, mail boxes, etc. Once facilities are located,

a routing plan must be put in place to link them together on a regular basis. All

too often, facilities are ¬rst located without suf¬cient consideration of transportation

costs, which may result in systemic inef¬ciencies. When planning to locate facilities

it is preferable to integrate into the analysis the routing costs that these will generate.