<<

. 12
( 15)



>>

cycle (generally infeasible for the NRPCL) is generated through an exact or heuristic
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.

<<

. 12
( 15)



>>