Heuristics for the Prize-collecting Rural

Postman Problem (PRPP)

Oscar Meza
Guillermo Palma

Computer Science and Information Technology Department,

Universidad Simón Bolívar
Caracas-Venezuela
 Content

1. The Prize-collecting Rural Postman Problem

2. Two 0-1 LP models
3. Adhoc heuristics to obtain feasible solutions
4. Some procedures to improve feasible solutions
5. A Scatter search algorithm
6. A Tabu search algorithm
7. Results
8. Final comments
 1. Prize-collecting Rural Postman Problem (PRPP)

PRPP is a NP-Hard Arc-Routing Problem (Aráoz, J., E. Fernández, C.

Zoltan (2006), The Privatized Rural Postman Problem, Computers and Operations
Research, 33, 3432-3449)

Instance G=(V,E), a undirected graph

d: distinguished vertex (depot)
p:Eℝ (profit), c:E ℝ (cost)

Question: To find one closed path C * that the maximizes the value of p
ete
c e
e
C
among all closed paths C , not necessarily simple, that pass through d.
te denotes the number of times that edge e is traversed in C.
 Example
7
Demand edges B 9 A
9 6
ce : cost for traversing e 2 4
0 9
0 9 3
G: d D
pe: profit for servicing e 9
7 9
0
9 6
C E
0
9-7
B A
-2 -4
d 9-3 D
A feasible solution:
-7
9-4
9-7
C E

Net profit of the route: (9-7)+(9-4)+(9-7)-2+(9-3)-4-7=2

 2. Two LP models for PRPP
1
if
edge
eis
serviced
(traversed
for
the
first
time)
x

e
0
otherwise eE
ye : number of times that edge e is traversed after the first time.

Let e = pe - ce



x
ee 
Maxc
y
ee
e
E e
E

Subject to:
• All vertices have even degree
• Connectivity with the depot of edges that are serviced

Dominance Relations • ye  1
(In an optimal solution) • ye  xe
 All Vertices have even degree

x(d (v))+ y(d (v)) º mod 2 vÎV

can be modeled by:
x( d (v) \ F ) + y( F \ F ’ )  x( F ) + y( F ’ ) - | F | - |F ’ | + 1
vV, F  d (v), F ’  F, | F | +|F ’| odd.
F
F’
F\F’

d (v)\F

Implied by co-circuit inequalities

F. Barahona and M. Groeschel. On the cycle polytope of a binary matroid. J. Comb. Theory, 40:40–62, 1986.
 Connectivity with the depot (and Set Parity of edges
that are serviced)

x(d (S)) + y(d (S))  2 xe , S  V \{d}; e  g(S)

an exponential number of constraints but

separation problem easy!!!

Belenguer, J., E. Benavent, The Capacitated Arc Routing Problem: valid inequalities and facets.
Computational Optimization and Applications (10), 165-187, 1998.
 A LP flow conservation model

- The even degree vertex constraints can be modeled by flow

conservation.

To every edge {i,j} of G we associate four 0-1 variables xij , xji , yij and yji

xij= 1 iff edge {i,j} is traversed the first time from i to j

yij= 1 iff edge {i,j} is traversed the second time from i to j

x x
iV
ij
kV
jk   yij   y jk  0 j V
iV kV
 xi j  1 – xj i  i,j Î V
yi j  1 – yj i  i,j Î V
yi j + yj i  xi j + xj i  i,j Î V

for depot d we create a duplicate d’ and edge {d, d’} in

order to guarantee solution passing through it:

1 xd d’

- The connectivity with the depot can be modeled in a similar way as before:

x(d (S)) + y(d (S))  xij , (S  V \{d}); ((i,j)  g(S))

 3. Adhoc heuristics to obtain feasible solutions

Five heuristics:
1. A very simple greedy procedure.
2. Three heuristics that use an adaptation of the 3T heuristic (*).
2.1 Union of connected components
2.2 Union and deletion of connected components
2.3 Union and deletion of connected components using a factor
3. A probabilistic greedy procedure.

(*) E. Fernández, O. Meza, R. Garfinkel, and M. Ortega. On the undirected rural postman problem: Tight
bounds based on a new formulation. Operations Research, 51:281–291, 2003.
 Union of connected components

Let S be the edge set of G with pe – ce  0, and Gs the induced graph by S. The costs on edges are:
ce if e Î S, and ce – pe if e  S

a. Build a minimum cost tree T between connected components of Gs, ET .

b. Add edges to ET  S so that all vertices have even degree. (minimum cost perfect matching in the
subgraph induced by odd degree vertices: M)
c. Apply shortcuts to improve the solution ET  S  M .
 4. Some procedures to improve a feasible solution

Let C be a feasible solution of PRPP:

a) Remove negative subcycles. C=<d, … , v, … ,v, … , d> if <v, … , v> has negative profit then
remove it from C
b) Remove parallel edges with negative profit and not disconecting
c) Replace consecutive edges (i,k),(k,j) by a path from i to j with greater profit
 5. A Scatter Search Algorithm

General
framework:
 Diversification Generation Method

The population consists in 18 feasible solutions which are generated with the
Adhoc Heuristics (applying or not the improvement procedures):

1. The very simple greedy procedure.

2. Three heuristics that use of an adaptation of the 3T heuristic.
2.1 Union of connected components
2.2 Union and deletion of connected components
2.3 Union and deletion of connected components using a factor
3. The probabilistic greedy procedure.
 Solution Combination Method

Combine solutions using the Liner Order Operator (GEN, M., AND CHENG, R. Genetic
algorithms and engineering design. Wiley-Interscience, 1997.)

Sol. 1: d-5-7-9-8-4-10-2-3-d Take some profitable common edges:

Sol. 2: d-3-2-4-8-9-2-10-7-5-d d-5, 5-7, 9-8, 10-2, 2-3

Place edges in a list from left to right Chose a range:

according to solution: positions 2 to 3
Put into sol. 1 the egdes in sol. 2 not
List. 1: d-5, 5-7, 9-8, 10-2, 2-3
in the range of sol. 1 (from left to
List. 2: 3-2, 8-9, 2-10, 7-5, 5-d
right) and viceversa:
New List. 1: 3-2, 5-7, 9-8, 2-10, 5-d
New List. 2: d-5, 8-9, 2-10, 5-7, 2-3

Construct two new solutions by means of minimal paths (mp):

New sol. 1: d-mp-3-2-mp-5-7-mp-9-8-mp- 2-10-mp- 5-d
New sol. 2: d-5-mp-8-9-mp-2-10-mp-5-7-mp-2-3 –mp-d
 6. Tabu Search

Components of Tabu Search:

- It is a local search algorithm allowing non-improving moves

- Define a search space and its neighborhood structure

- Cycling back to  previously visited solutions is prevented by the use

of  short-term memories, called tabu lists

- The aspiration criteria which consists in allowing a move, even if it is

tabu, if it results in a solution with an objective value better than that of
the current best-known solution

- Intensification and Diversification which use intermediate-term memory

and long-term memory

- Termination criteria. For example, after some number of iterations without

an improvement in the objective function value
 A very simple Tabu Search Implementation

The neighborhood structure:

(CORBERÁN, A., MARTÍ, R., AND ROMERO, A. Heuristics for the mixed rural postman problem. Computers &
Operations Research 27, 2 (2000), 183–203)

- Let (l,m) be any edge of the actual solution:

C=<(d,a),(a,b), … , (i,j), … , (l,m), … , (p,q), … , (s,t), (t,d)>

(i,j) and (p,q) are nearest edges with profit (in RUQ) to (p,q) (if not, take (d,a) or (t,d))

- Find two minimum paths [j,l] and [m,p], taking suitable costs on edges

- Replace the respective path in C by [j,l] and [m,q].

- A neighborhood of C will be:

C’ =<(d,a),(a,b), … , (i,j), [j,l] , (l,m), [m,p] , (p,q), … , (s,t), (t,d)>

 A very simple Tabu Search Implementation….

- Choose the neighbor with highest profit.

If the profit is no greater than the best solution found so far, then take a
neighbor at random (the probability of a neighbor will be proportional to
its profit)

- Termination criteria: 40 iterations without finding a better solution

- Diversification Method: Each 5 iterations without finding a better solution, begin the
search from a new feasible solution obtained from the adhoc heuristics.
 7. Results
- All instances were run on a Sun ULTRA 10, model 440,
UltraSPARC-IIi processor with 440 MHZ, 1 GB DRAM. GNU Compiler Collection
(GCC) versión 3.4.6

- The benchmark Instances are the 118 PRPP instances from well
known sets of benchmark RPP instances (Araoz, Fernandez & Meza).

- The 118 RPP benchmark instances are divided in five groups.

- The first group contains two problems, ALBAIDAA and ALBAIDAB,

obtained from the Albaida,Spain Graph (Corberán and Sanchis).

- The second group contains the 24 instances (problems labeled P) of

Christofides et al.

- The last three groups contain instances from Hertz et al:

36 instances with vertices of degree 4 and disconnected required
edge sets (labeled D), 36 grid instances (labeled G), and 20 randomly
generated instances (labeled R).
 Example: Description of the R-instances
|V|: number of vertices
|E|: number of edges
|RUQ|: number of edges with non-negative profit (pe – ce >=0) (profit minus cost)
#comp.R U Q: number of connected components induced by R U Q
#e = number of edges with pe – ce = 0
Results for the Scatter Search(SS) and Tabu Search(TS) Metaheuristics

As the two metaheuristcs are

probabilistics algorithms, each
instance was run 20 times

vpss(ts): mean value of 20

solution’s objective values

%dpss(ts): percent deviation

of the mean value from the
optimum

ss(ts): standard deviation

vss(ts): best value from 20

solutions

#mss(ts): number of times

(from 20 solutions) the best
value is attained

These lows values confirm the robustness of

metaheuristic implementations
Performance of three Heuristics: H (from Fernandez&al.),
Scatter Search (SS) and Tabu Search(TS)

vo(h,ss,ts): optimum
solution value, Heuristic
value, best (from 20)
scatter search value, best
(from 20) tabu search
value

%dh(ss,ts): percent
deviation of the best
value from the optimum

th(ss,ts): mean time in

seconds
 Consolidated Results
Sum of best values in
each group Mean of deviation percent
(the best results in Scatter Total time per group
and Tabu searchs)
 8. Final Comments

 Satisfactory preliminary results for PRPP with very simple

implementations of Scatter Search and Tabu Search
Future work:
 Test the new linear model (flow conservation)
 Implement new Adhoc Heuristics in order to improve the population in
Scatter Search
 Try a more elaborated implementation of Tabu Searh.
 For Intensification: use of intermediate-term memory, such as
a recency memory.
 For Diversification: use long-term memory of the search, such as
a frequency memory.