Privatized Rural Postman Problem Algorithm

Julián Aráoz, Elena Fernández

Dept. EIO, UPC
and
Oscar Meza
Dept. CTI, USB

Departament d’EIO. Secció Informàtica

Universitat Politècnica de Catalunya

November 28, 2004

DR 2004/xx
 Privatized Rural Postman Problem Algorithm
Julián Aráoz
Simón Bolı́var University∗, Venezuela
Technical University of Catalonia†, Spain
Elena Fernández
Technical University of Catalonia, Spain
Oscar Meza‡
Simón Bolı́var University, Venezuela.

Abstract
In this work . . .

1 Introduction
2 The Privatized Rural Postman Problem
The Privatized Rural Postman Problem has been defined in the work of
Aráoz, Férnandez and Zoltan [2], we repeat here the definitions and results
relevant for our algorithm. Since this problem is a generalization of the
classical Rural Postman Problem, we began with its definition.
Definition 2.1 Rural Postman Problems (RPPs)
Given a graph G(V, E), a set R ⊆ E and a cost function c from E in
IR+ , the Rural Postman Problem is to find a cycle C ∗ , not necessarily
simple that minimizes the value of
X
(te ce )
e∈C

where C is such that R ⊆ E(C) and te is the number of times that edge e is
traversed in C.
We denote a RPP by (G, R, c).
∗
Retired Professor Dpt. Process and Systems.
†
Visiting Professor Dpt. Statistics and Operation Research.
‡
Retired Professor Dpt. Computation and Information Technology

1
 We use standard graph nomenclature, the reader could see [?] or [2] for
definitions and elementary properties.
In a Privatized Rural Postman Problem instead of required edges we
have benefits that we could collet passing through an edge.

Definition 2.2 Privatized Rural Postman Problems (PRPPs).

Given a graph G(V, E) with a distinguished vertex d, the Depot, and two
functions from E in IR+ , the profit function b and the cost function c, the
Privatized Rural Postman Problem is to find one cycle C ∗ which maximizes
the value of X
(be − te ce )
e∈C

where C is a cycle in G passing trough d, and not necessarily simple, and t e

is the number of times that edge e is traversed in C.
We denote a PRPP by (G, d, b, c).

That is, in a PRPP, we look for the most Profitable Subtour passing
through d.
In [2] was proved that the PRPP is NP–Hard, for this reason our ap-
proach is to apply to the linear system with an exponential number of in-
equalities defined in [2] the Cut approach of a Branch and Cut method.
citar algo?
We define the functions ϕe = be − ce and ψe = be − 2ce = ϕe − ce . These
two functions play an important role in a PRPP: ϕ e is the value obtained
when traversing the edge e the first time, whereas ψ e is the value obtained
when traversing the edge e twice.
We partition the set of edges in three sets:

P = {e ∈ E | ϕe < 0}, R = {e ∈ E | ψe ≥ 0}, Q = {e ∈ E \ R | ϕe ≥ 0}

We call Negative the edges in P and Positive the edges in Q ∩ R, Truly

Positive the edges in R and Low Positive the edges in Q.
The Truly Positive edges play an important role in these PRPPs similar
to the set of required edges in a RPP (G, R, c) and the Negative edges have
a similar behavior to the edges in the set of non-required edges in the same
RPP. Really, the edges in the set Q are the ones that provide a different
behavior (see [2]).
We Call (G, d, b, c) a Truly Positive Problem when there are not Low
Positive edges and the Negative edges have 0 benefit.

2
 We denote by GR ≡ (V (R) ∪ {d}, R) the subgraph induced by the edge
set R and the depot.
Let Ci , i ∈ P = {0, . . . , p)} be the connected components of the graph
GR and we assume that d ∈ C0 . When necessary, we denote by Vi = V (Ci )
and we differentiate between γ(Vi ) in the original graph G and γR (Vi ) in the
graph GR . That is γR (Vi ) = γ(Vi ) ∩ R.
Let eRi be an arbitrarily selected edge in C i , i ∈ P .
Since it could be that no edge of R meets d, it is possible that V 0 = {d}
γR (V0 ) = ∅ and that eR 0 would be undefined. In this case we add a loop
(d, d) with b(d,d) = c(d,d) = 0, in this case this dummy edge will be e R
0. creo que
Given an optimum solution C, in [2], were proved the following proper- lo mejor es
ties: no tener
edje en C0
2.3 Dominance 1. No edge is used more than twice in C.
y definir
x R = 1 en el
2.4 Dominance 2. If and edge e ∈ C is used with value c e then it is used 0
twice. sistema

2.5 Dominance 3. Let e ∈ C, if for some connected component C k of GR

we have that V (e) ∩ Vk 6= ∅ then all the truly positive edges of C k are in C.
2.6 Dominance 4. Let Ck be a connected components of GR and let e1 , e2 ∈
γR (Vk ). Then we have both edges in C or none.
2.7 Preprocessing 1. Let Ck be one of the connected components of G R . If
f ∈ γ(Vk ) \ R then f is used only once.
From a more general result in [2] we also have the following corollary:
2.8 Preprocessing 2. γR (V0 ) ⊆ C.
2.9 Since, by Dominance 1 in any optimal solution to the PRPP no edge is
traversed more than twice, from now on, we will consider an auxiliary graph
G0 = (V, E 0 ∪ E 00 ). Where both E 0 and E 00 are disjoint copies of E with all
the edges in E 0 corresponding to the first time that the original edge is used
and all the edges in E 00 corresponding to the second time that the original
edge is used. We denote by e an original edge in E and by e 0 and e00 its
corresponding copies in E 0 and E 00 respectively.
Hence for any e ∈ E we have be0 = be , ce0 = ce and be00 = 0, ce00 = ce ,
also eR
i ∈E .
0

Therefore, given a PRPP (G, d, b, c), its solution is an Eulerian subgraph

of G0 passing through the depot d plus isolated vertices. We call such a
subgraph d-Eulerian.

3
3 Polyhedral Model
The linear equations that we use to define the feasible solutions correspond-
ing to d-eulerian subgraphs of G0 are like the ones in the paper of Aráoz,
Férnandez and Zoltan [2] where the PRPPs were defined.
Let (G, d, b, c) be a given PRPP. cual es
The model is defined on the graph G0 (2.9)where each edge of G has been la mejor
replicated. Each edge e0 ∈ E 0 is associated with the variable xe0 whereas manera de
each edge e00 ∈ E 00 is associated with the variable ye00 however whenever manejar las
there is not confusion we use xe and ye instead of xe0 and ye00 . copias
The PRPP Linear Program (PRPPLP) model is the following: ver la ecua-
cion 2
X X
max z(x, y) = φe xe − ce ye (1)
e∈E 0 e∈E 00
x(δ 0 (v) \ F 0 ) + y(δ 00 (v) \ F 00 ) ≥ x(F 0 ) + y(F 00 ) − |F 0 ∪ F 00 | + 1,
v ∈ V, F 0 ⊆ δ 0 (v), F 00 ⊆ δ 00 (v), |F 0 ∪ F 00 | odd. (2)
0 00
x(δ (S)) + y(δ (S)) ≥ 2xe ,
S ⊆ V \ {d}, e ∈ γ 0 (S) \ R0 (3)
0
x(δ (S)) + y(δ (S)) ≥00
2eR
k,
S ⊆ V \ {d}, k 6= 0, Vk ∩ S 6= ∅ (4)
0 0
x e = x eR , e ∈ γ (Vk ) ∩ R , k ∈ P (5)
k

ye00 ≤ xe0 , e∈E (6)

x e ≤ x eR , e ∈ ((γ 0 (Vk ) ∪ δ 0 (Vk )) \ R0 ), k ∈ P (7)
k
00 00
ye = 0, e ∈ γ (Vk ) \ R , k ∈ P (8)
0 0
xe = 1, e ∈ γ (V0 ) ∩ R (9)
xe0 , ye00 ∈ {0, 1}, e∈E (10)
ver la ecua-
P
Notice that we use the standard compact notation f (A) ≡ e∈A fe when cion ?? creo
A ⊆ E, and f is a vector or a function defined on E. Also, by extension, que alcanza
if H is a graph or a path we denote f (H) ≡ f (E(H)). Finally, we use the E 0 ∩ γ 0 (S)
prime and double prime in edge sets to denote which copies we are using, ojo Oscar
like δ 0 (V ) = δ(V ) ∩ E 0 , δ 00 (V ) = δ(V ) ∩ E 00 . las usa
explicar las
• Inequalities (2) ensure even degree at every vertex, and they are im- ecuaciones
plied by the so-called co-circuit inequalities in Barahona and Grötschel
[3] in a matroid context (see also Aráoz et al. [1]).

4
 • Inequalities (3)and (4) ensure connectivity with the depot of any edge
that is selected, that is an edge e0 corresponding to xe0 = 1, by Dom-
inance 2 we do not need to check the edges in E 00 and by Dominance
4 if e0 ∈ Ck we only use eRk.

• Equalities 5 xe = xeR correspond to Dominance 4.

k

• Inequalities 6 ye00 ≤ xe0 correspond to Dominance 2.

• Inequalities 7 xe ≤ xeR correspond to Dominance 3 and Dominance 4.

k

• Equalities 8 ye = 0 correspond to Preprocessing 1.

• Equalities 9 xe = 1 correspond to Preprocessing 2.

• Binary conditions 10 xe0 , ye00 ∈ {0, 1} correspond to Dominance 1.

4 Cutting Plane Algorithm

4.1 Initial Linear Relaxation
The cutting plane algorithm starts with the linear relaxation that is de-
scribed below. Then, at each iteration cutting planes, to be described later
on, are added.
The initial linear relaxation is the following:

X X
max z(x, y) = φe xe − ce ye (11)
e∈E 0 e∈E 00
0 00
x(δ (v)) + y(δ (v)) ≥ 2xe , v ∈ V, e ∈ δ 0 (v). (12)
0 00
x(δ (Vk )) + y(δ (Vk )) ≥ 2xeR , k∈P (13)
k
0
x e = x eR , e ∈ E ∩ γR (Vk ) and k ∈ P (14)
k

ye00 ≤ xe0 , e∈E (15)

0 0 0
x e ≤ x eR , e ∈ ((γ (Vk ) ∪ δ (Vk )) \ R ), k ∈ P (16)
k

ye = 0, e ∈ γ 00 (Vk ) \ R00 , k ∈ P (17)

0 0
xe = 1, e ∈ γ (V0 ) ∩ R (18)
0 ≤ xe0 , ye00 ≤ 1, e∈E (19)

This initial program has the same functional (1) and all the inequalities
(5)-(9) of the PRPPLP. However it relax the integrity condition (10) and

5
from the inequalities of the type (2) it take only the ones that correspond
to the sets with |F 0 | = 1 ∧ |F 0 | = 0.
That is, let F 0 = {e} we obtain

x(δ 0 (v) \ e) + y(δ 00 (v)) ≥ xe ≡

x(δ 0 (v)) − xe + y(δ 00 (v)) ≥ xe ≡
x(δ 0 (v)) + y(δ 00 (v)) ≥ 2xe (see 13)

We take no inequality of (3), but, in each component C k we chose as

e = eRk one of the edges with greatest φ e , with it we take the inequalities
of the type (4) that correspond to the sets S = V k with e = eRk . Note that
the solutions to this system may be integer despite not being feasible to the
PRPPLP.

4.2 Cutting Plane Algorithm

The cutting plane algorithm is as follows:

1. Let LPR be the linear program relaxation 11 to 19

2. Let z̄ = ∞; z = 0; optimum = f alse; bestxy = (0, 0)

3. Do:

(a) Find a solution (x∗ , y ∗ ) of the current linear program relaxation

LPR.
(b) if z̄ > z(x∗ , y ∗ ) then z̄ = z(x∗ , y ∗ )
(c) If (x∗ , y ∗ ) is feasible in PRPPLP then bestxy = (x ∗ , y ∗ ); z = z̄
i. identify inequalities of types (2) to (4) violated by (x ∗ , y ∗ ).
ii. Add the valid inequalities identified in step (3(c)i) to LPR.
iii. Compute the heuristic lower bound and solution z h = (xh , y h )
iv. if z < z(xh , y h ) then z = z(xh , y h ); bestxy = (xh , y h )

4. Until either z = z̄ or no more inequalities are added to LPR in step

(3(c)ii).

5. if z = z̄ then output z; bestxy else output gap = z̄ − z; z; bestxy

6
4.3 Separation Cuts
At a given iteration of the algorithm Step (3(c)i) consists of the following:

1. Finding violated inequalities of type (2). To separate the inequalities

(2) we use a heuristic proposed by Ghiani and Laporte [11]
Let (x∗ , y ∗ ) be a solution of the current linear program relaxation LPR.
We solve the following problem: For each vertex v we find the value

Av = min x∗ (δ 0 (v) \ F 0 )
F 0 ⊆δ 0 (v)∪F 00 ⊆δ 00 (v)
X X
+ y ∗ (δ 00 (v) \ F 00 ) + (1 − x∗e ) + (1 − ye∗ ) − 1
e∈F 0 e∈F 00

The minimum is obtained by the set F 0 ∪F 00 that contains all the edges
e0 and e00 incident with v such that x∗e0 ≥ 0.5 and ye∗0 ≥ 0.5 If Av < 0
then: If |F 0 ∪ F 00 | is odd then for v and F 0 ∪ F 00 the following inequality
is violated by (x∗ , y ∗ ):

x(δ 0 (v) \ F 0 ) + y(δ 00 (v) \ F 00 ) ≥ x(F 0 ) + y(F 00 ) − |F 0 ∪ F 00 | + 1

If |F 0 ∪ F 00 | is even and positive then we eliminate from F 0 ∪ F 00 the

edge e with value closer to 0.5. If
X X
x∗ (δ 0 (v) \ F 0 ) + y ∗ (δ 00 (v) \ F 00 ) + (1 − x∗e ) + (1 − ye∗ ) − 1
e∈F 0 e∈F 00

is negative for this new set F 0 ∪ F 00 , then the following inequality is

violated by (x∗ , y ∗ ):

x(δ 0 (v) \ F 0 ) + y(δ 00 (v) \ F 00 ) ≥ x(F 0 ) + y(F 00 ) − |F 0 ∪ F 00 | + 1

2. Finding violated inequalities of type (3)or (4). falta revisar

To separate the inequalities of type (3) we proceed as follows: y com-
patibilizar
Inequalities of type (3) we will call connectivity inequality and (4) we con nuevas
will call set-parity inequality (as opposed to inequalities (2) which are ecuaciones
node-parity).
Connectivity inequalities are of the form x(δ(S)) + y(δ(S)) ≥ 2x e , for
e ∈ γ(S), S ⊆ V \ {d}.
Set-parity inequalities are of the form x(δ(S)) + y(δ(S)) ≥ 2x e , for e ∈
δ(S), S ⊂ V . For separating any of the above inequalities (connectivity

7
 or set-parity) we use the algorithm of Gusfield to calculate the tree of
min-cuts of the graph G0 obtained from the original one by eliminating
all edges in E 0 or E 00 with value zero and assigning a cost to each edge
with value equal to the value of the variable associated with that edge.
The tree of min-cuts of G0 contains the same vertices as G0 . In order to
determine in that tree the value of the min cut in G 0 between two given
nodes v and w, one has to find in the tree the edge e ∗ of minimum
cost (the costs of the edges in the tree correspond to costs of cuts in
G0 ) in the path that connects the vertices v and w. The value of e∗ is
the value of the min-cut that separates v and w in G 0 , and the set of
vertices that defines the minimum cut is the set of vertices of any of
the two connected components that result when eliminating edge e∗
from the tree.
The connectivity inequalities are separated with an exact algorithm.
That is, if there exists a violated connectivity inequality this algorithm
finds it. This result are from from Belenguer and Benavent [4, p.261].
The algorithm does the following:
For each edge e = {u, v} ∈ E 0 with v and w different form the depot
and x∗e > 0 we determine the minimum cut δ(S) such that e ∈ γ(S).
This min-cut is easily obtained from the min-cut tree as they explain
in the above referenced book. If the value of the min cut is smaller
than 2x∗e then the following inequality is violated by (x ∗ , y ∗ ): x(δ(S))+
y(δ(S)) ≥ 2xe0 . The set parity inequalities are separated exactly with
a very simple algorithm: For each edge e = {u, v} ∈ E 0 we determine
the minimum cut δ(S) that separates v and w. If the value of this
min cut is less than 2xe then the following inequality is violated by
(x∗ , y ∗ ): x(δ(S)) + y(δ(S)) ≥ 2xe .

4.4 Heuristic Bound

The algorithm used to obtain a lower bound is the following heuristics: creia que el
depot era el
1. Let (x∗ , y ∗ ) be the solution obtained with the linear relaxation de- vertice 1, G
scribed in the previous section. o G’,
2. Transform the PRPP into a RPP. The graph of the RPP will be the
graph PRPP plus a fictitious edge {0, 0 0 } of zero cost that will be
required to guarantee that the solution passes through the depot. The
costs of the remaining edges correspond to the costs of the edges of the

8
 PRPP. The other required edges of RPP will be the edges of PRPP
with value x∗e ”close” to 1.

3. Find a feasible solution to RPP with the 3T heuristic of Fernández,

Meza, Garfinkel and Ortega [10].

4. The feasible solution to PRPP results from eliminating the parallel

edges {0, 00 } when they exist from the feasible solution to RPP ob-
tained in 3. siempre esta
0,0’ ?
5 Experimentation
We use some of the standard test problems for the RPP’s, the ALBAIDAA
and ALBAIDAB, P01 to P24, DEGREE0 to DEGREE35, GRID0 to GRID35
and RANDOM0 to RANDOM19.
These problems are in [?],and convert these problems to PRPP assigning
benefits to the edges.
To generate PRPP’s problems we take an RPP (G, R, c) and assign ran-
dom generated benefits to he edges and add a vertex d in order to generate
a (G,d,b,c) PRPP.
From [2] we know that transforming and RPP into PRPP by assigning
high enough values of benefits to the required edges and zero benefit for
the non-required ones, the edges used in both solution are the same. Notice
that the set of required edges of the RPP is the same that the set of Truly
Positive edges of the new PRPP.
To solve the linear problems we use Simplex version xxx in a yyy com-
puter
We use the initials in table of acronyms for the identification of columns
in the tables of results.

5.1 RPP Solutions

Since RPP can be expressed as a PRPP, the first group of test problems
are obtained by given the value b(e) = 99999, ∀e ∈ E, we also define d as
the vertex 1, and connecting it with an edge, with 0 cost and benefit, to a
vertex incident with a required edge.
We see that there are less than one percent margin between the higher
and the lower bound

9
 Mnemonic Parameter Name
PN Problem Name
LRV Linear Relaxation Value
HV Heuristic Value
DIF (LRV-HV)
PDRH Percent Difference Between LRV and HV=(LRV-HV)/LRV*100
TBHS Total Benefits Heuristic Solution
TCHS Total Cost Heuristic Solution
LRT Linear Relaxation Time (sec)
HT Heuristic Time (sec)
LRIN Linear Relaxation Number
LRCR Linear Relaxation Connection Restriction Number
RSPRN Linear Relaxation Set Parity Restriction Number
RVPRN Linear Relaxation Vertex Parity Restriction Number
ORN Objective Rounding Number

Table 1: Acronyms

5.2 PRPP Solutions

We solve many instances of generated problems. To generate PRPP’s prob-
lems we take the same RPP’s of section 5.2. Vertex 0 is the depot and for
each (G, R, c) we assign uniformely random generated benefits:

• for e ∈ R the random number are between c e and 3ce .

• for e ∈ E \ R the random number are between 0 and c e − 1.

We denote the transform of a problem named XXX as XXXM.

6 Conclusions

7 Acknowledgements
The work of the first and third authors has been partially supported by
grants from FONACIT Project USB S1- 2000000438, Venezuela. The re-
search of the first author has been partially financed by the Spain “Secre-
tarı́a de Estado de Educación y Universidades”. The research of the second
author has been partially supported by grant TIC 2000 1750 006/3 of the
Inter-Ministerial Spanish Commission of Science and Technology. These
supports are gratefully acknowledged.

10
References
[1] J. Aráoz , W. Cunningham , J. Edmonds, and J. Green–Krotki. Reduc-
tions to 1–matching polyhedra. Networks, 13:455–473, 1983.

[2] J. Aráoz, E. Fernández, C. Zoltan. “The Privatizad Rural Postman

Problem”. Reporte DR-2003/12, EIO Departament , Universitat Politc-
nica de Catalunya, Espaa (2002). Accepted in Computers and Opera-
tions Research.

[3] F. Barahona and M. Groeschel. On the cycle polytope of a binary ma-

troid.J. Comb. Theory, 40:40–62, 1986.

[4] E. Benavent, A. Corberan, and J.M. Sanchis. Linear programming

based methods for solving arc routing problems. In Arc Routing: The-
ory, Solutions and Applications M. Dror (edt), Kluwer Academic Pub-
lishers, 2000.

[5] N. Christofides, V. Campos, A. Corberan, and E. Mota. An algorithm

for the rural postman problem. Imperial College Report IC.O.R., 81.5,
1981.

[6] J. Edmonds and E.L. Johnson. Matching, euler tours and the chinese
postman. Mathematical Programming 5:88–124, 1973.

[7] M. Dror Edt. Arc Routing: Theory, Solutions and Applications. Kluwer
Academic Publishers, 2000.

[8] L. Euler. Solutio problematis ad geometriam situs pertinentis. Com-

mentarii Academiae Petropolitannae, 8:128–140, 1736.

[9] D. Feillet, P. Dejax, and M. Gendreau. Traveling salesman problems

with profits: an overview.Transportation Science.

[10] 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.

[11] G. Ghiani and G. Laporte. A branch-and-cut algorithm for the undi-

rected rural postman problem. Mathematical Programming, 87:467–481,
2000.

[12] J.K. Lenstra and A.H.G. Rinnooy Kan. On general routing problem.
Networks, 6:273–280, 1976.

11
[13] N. Maculan, G. Plateau, and A. Lisser. Integer linear models with a
polynomial number of variables and constraints for some classical com-
binatorial optimization problems. Pesquisa Operacional 23:161–168,
2003.

[14] K. Wenger. A New Approach to Cactus Construction Applied to TSP

Support Graphs. In Proc. Ninth Conference on Integer Programming
and Combinatorial Optimization (IPCO 02), 2002.

12
PN LRV HV DIF PDRH TBHS TCHS LRT HT LRIN LRCR RSPRN RVPRN

ALBAIDAA 719057 718901 156 0,02 729500 10599 4,16 1,48 6 126 23 38
ALBAIDAB 571851 571671 180 0,03 580300 8629 2,38 1,23 6 227 22 38
P01 2424 2424 0 0,00 2500 76 0,01 0,18 3 11 1 2
P02 7858 7848 10 0,13 8000 152 0,02 0,04 2 9 2 2
P03 6899 6898 1 0,01 7000 102 0,10 0,05 5 24 1 4
P04 5419 5416 3 0,06 5500 84 0,03 0,02 3 34 1 7
P05 6780 6776 4 0,06 6900 124 0,04 0,05 3 11 4 3
P06 6900 6898 2 0,03 7000 102 0,06 0,03 3 19 6 7
P07 9170 9170 0 0,00 9300 130 0,04 0,01 3 29 1 10
P08 9179 9178 1 0,01 9300 122 0,06 0,02 5 0 0 13
P09 5619 5617 2 0,04 5700 83 0,03 0,01 4 9 2 6
P10 4428 4420 8 0,18 4500 80 0,01 0,03 2 7 2 0
P11 1377 1377 0 0,00 1400 23 0,01 0,00 1 0 0 0
P12 1281 1281 0 0,00 1300 19 0,01 0,00 2 4 0 0
P13 1165 1165 0 0,00 1200 35 0,30 0,00 1 0 0 0
P14 14312 14298 14 0,10 14500 202 0,06 0,18 2 28 4 11
P15 17562 17559 3 0,02 18000 441 0,06 0,15 4 56 8 6
P16 13702 13697 5 0,04 13900 203 0,17 0,53 4 64 5 8
P17 6193 6188 5 0,08 6300 112 0,03 0,08 2 17 4 2
P18 5956 5954 2 0,03 6100 146 0,05 0,05 3 38 6 8
P19 13545 13544 1 0,01 13800 256 0,13 0,06 4 62 2 12
P20 27815 27796 19 0,07 28200 404 0,49 3,21 6 100 1 30
P21 28443 28430 13 0,05 28800 370 0,35 0,69 5 172 9 23
P22 49285 49279 6 0,01 49900 621 0,42 0,10 4 131 0 27
P23 37528 37525 3 0,01 38000 475 0,62 1,04 6 208 0 38
P24 28798 28795 3 0,01 29200 405 0,39 0,11 4 112 1 17
DEGREE0 11628 11628 0 0,00 11900 272 0,02 0,00 5 10 1 0
DEGREE1 24006 23927 79 0,33 24700 773 0,07 0,02 11 76 21 1
DEGREE2 31551 31498 53 0,17 32200 702 0,02 0,01 2 9 4 1
DEGREE3 33546 33546 0 0,00 34300 754 0,08 0,00 12 72 36 2
DEGREE4 32759 32680 79 0,24 33600 920 0,06 0,03 8 60 14 0
DEGREE5 48106 48037 69 0,14 49000 963 0,03 0,04 4 18 3 4
DEGREE6 39648 39591 57 0,14 40500 909 0,03 0,03 4 40 7 2
DEGREE7 45464 45366 98 0,22 46400 1034 0,03 0,12 3 29 3 3
DEGREE8 60471 60387 84 0,14 61400 1013 0,03 0,11 3 12 4 6
DEGREE9 35586 35563 23 0,06 36600 1037 0,19 0,05 8 130 50 3
DEGREE10 22761 22761 0 0,00 23500 739 1,18 0,02 26 559 168 2
DEGREE11 61812 61812 0 0,00 62900 1088 0,18 0,08 5 117 35 1
DEGREE12 50315 50315 0 0,00 51400 1085 0,15 0,03 5 86 46 6
DEGREE13 71466 71396 70 0,10 72500 1104 0,12 0,10 3 54 18 2
DEGREE14 94409 94384 25 0,03 95800 1416 0,13 0,03 3 32 11 8
DEGREE15 89919 89895 24 0,03 91300 1405 0,14 0,08 4 33 9 11
DEGREE16 105221 105153 68 0,06 106600 1447 0,20 0,09 4 77 17 14
DEGREE17 121855 121743 112 0,09 123500 1757 0,32 0,11 5 6 2 16
DEGREE18 70450 70385 65 0,09 71700 1315 22,20 0,62 54 1654 252 3
DEGREE19 71549 71507 42 0,06 72900 1393 25,18 0,21 15 359 140 7
DEGREE20 64957 64937 20 0,03 66200 1263 3,46 0,09 15 773 155 11
DEGREE21 113516 113486 30 0,03 115100 1614 1,33 0,32 6 213 43 23
DEGREE22 111532 111445 87 0,08 113200 1755 1,16 0,45 5 183 55 17
DEGREE23 115681 115626 55 0,05 117400 1774 1,53 0,13 8 184 43 27
DEGREE24 170142 170105 37 0,02 172300 2195 0,91 0,12 5 52 12 31
DEGREE25 145445 145386 59 0,04 147400 2014 1,07 0,54 6 125 22 32
DEGREE26 184434 184332 102 0,06 186800 2468 0,86 0,26 5 135 21 42
DEGREE27 88575 88507 68 0,08 90300 1793 56,90 1,93 28 1600 377 17
DEGREE28 101996 101918 78 0,08 103800 1882 208,33 2,81 74 5242 737 22
DEGREE29 88510 88394 116 0,13 90200 1806 298,31 6,68 134 8757 1388 19
DEGREE30 152955 152890 65 0,04 155200 2310 17,50 0,80 17 1669 140 43
DEGREE31 175918 175883 35 0,02 178300 2417 43,10 1,31 35 3048 176 47
DEGREE32 145719 145636 83 0,06 147800 2164 4,21 3,93 5 244 90 26
DEGREE33 213394 213254 140 0,07 216200 2946 7,44 9,99 7 393 29 53
DEGREE34 217857 217737 120 0,06 220600 2863 11,02 1,21 13 1360 41 52
DEGREE35 215469 215354 115 0,05 218200 2846 4,41 0,55 5 231 29 55

Table 2: table experiments I

13
PN LRV HV DIF PDRH TBHS TCHS LRT HT LRIN LRCR RSPRN RVPRN

GRID0 288 288 0 0,00 300 12 0,05 0,01 8 80 18 0

GRID1 486 486 0 0,00 500 14 0,05 0,02 6 30 11 0
GRID2 388 388 0 0,00 400 12 0,06 0,01 8 54 11 0
GRID3 784 784 0 0,00 800 16 0,02 0,01 2 7 8 0
GRID4 684 684 0 0,00 700 16 0,05 0,02 5 54 10 1
GRID5 687 686 1 0,15 700 14 0,04 0,02 7 58 14 1
GRID6 1281 1280 1 0,08 1300 20 0,03 0,06 3 10 5 1
GRID7 784 784 0 0,00 800 16 0,17 0,01 3 24 9 1
GRID8 884 882 2 0,23 900 18 0,04 0,04 5 50 11 2
GRID9 1076 1076 0 0,00 1100 24 1,78 0,02 28 511 221 3
GRID10 1271 1270 1 0,08 1300 30 0,85 0,05 14 408 66 2
GRID11 1471 1470 1 0,07 1500 30 2,37 0,12 16 243 111 4
GRID12 2559 2556 3 0,12 2600 44 0,43 0,42 8 246 13 11
GRID13 2262 2260 2 0,09 2300 40 0,75 0,10 16 347 65 9
GRID14 2460 2458 2 0,08 2500 42 0,35 0,34 6 138 21 8
GRID15 3453 3450 3 0,09 3500 50 0,12 0,23 3 25 7 10
GRID16 2957 2954 3 0,10 3000 46 0,15 0,26 4 113 10 6
GRID17 3352 3352 0 0,00 3400 48 0,11 0,03 3 67 6 11
GRID18 2353 2350 3 0,13 2400 50 15,06 0,21 35 1797 227 7
GRID19 2650 2648 2 0,08 2700 52 33,97 0,23 70 2939 312 5
GRID20 2648 2646 2 0,08 2700 54 38,84 0,15 72 2269 383 7
GRID21 4533 4530 3 0,07 4600 70 17,35 0,26 34 1753 130 20
GRID22 4633 4630 3 0,06 4700 70 2,04 0,26 8 401 37 13
GRID23 4926 4924 2 0,04 5000 76 0,88 0,40 5 250 33 16
GRID24 6711 6710 1 0,01 6800 90 1,83 0,23 8 75 14 27
GRID25 6017 6016 1 0,02 6100 84 1,27 0,20 5 148 13 27
GRID26 6517 6516 1 0,02 6600 84 1,02 0,13 5 225 12 21
GRID27 4023 4020 3 0,07 4100 80 140,89 0,68 71 3504 521 16
GRID28 4816 4814 2 0,04 4900 86 202,78 0,59 87 7680 438 25
GRID29 4320 4316 4 0,09 4400 84 360,29 1,51 192 8563 1208 18
GRID30 7193 7190 3 0,04 7300 110 25,91 0,72 21 1730 270 31
GRID31 7588 7584 4 0,05 7700 116 6,79 7,02 7 438 100 19
GRID32 8083 8078 5 0,06 8200 122 3,44 5,05 6 51 23 29
GRID33 11154 11152 2 0,02 11300 148 3,38 0,33 4 62 6 39
GRID34 10559 10556 3 0,03 10700 144 6,82 2,01 10 150 9 41
GRID35 10760 10756 4 0,04 10900 144 4,52 2,30 6 162 14 44
RANDOM0 595047 595047 0 0,00 624900 29853 0,15 0,01 16 154 30 1
RANDOM1 937883 937883 0 0,00 972200 34317 0,17 0,00 15 128 35 0
RANDOM2 814332 814332 0 0,00 839300 24968 0,22 0,01 20 126 76 1
RANDOM3 1713746 1713746 0 0,00 1747800 34054 0,08 0,00 8 61 24 4
RANDOM4 1651523 1651344 179 0,01 1677600 26256 0,14 0,01 11 98 22 2
RANDOM5 894942 894942 0 0,00 930700 35758 0,69 0,01 23 517 84 5
RANDOM6 2112266 2111642 624 0,03 2151000 39358 1,26 0,00 42 495 108 2
RANDOM7 1405960 1405960 0 0,00 1441100 35140 0,42 0,01 26 163 95 1
RANDOM8 2241571 2241571 0 0,00 2290300 48729 1,71 0,01 42 784 149 2
RANDOM9 2208128 2208128 0 0,00 2250700 42572 0,29 0,01 11 148 70 4
RANDOM10 2026759 2026759 0 0,00 2065500 38741 2,63 0,01 30 530 154 1
RANDOM11 1479373 1478872 501 0,03 1521500 42628 1,18 0,02 31 473 129 4
RANDOM12 1084255 1083201 1054 0,10 1134600 51399 1,66 0,05 32 809 87 3
RANDOM13 3462002 3461133 869 0,03 3516000 54867 0,45 0,05 9 94 32 3
RANDOM14 4138844 4137158 1686 0,04 4203100 65942 1,25 0,12 16 305 124 4
RANDOM15 3554511 3552188 2323 0,07 3616600 64412 11,83 0,10 53 1765 124 10
RANDOM16 1888551 1888551 0 0,00 1938900 50349 2,14 0,06 29 440 233 2
RANDOM17 1552828 1552828 0 0,00 1596100 43272 7,46 0,12 49 1199 305 3
RANDOM18 3509230 3509230 0 0,00 3566100 56870 5,35 0,01 38 1129 160 9
RANDOM19 3124737 3123439 1298 0,04 3169100 45661 0,35 0,04 5 66 42 2

Table 3: table experiments I continuation

14
PN LRV HV DIF PDRH TBHS TCHS LRT HT LRIN LRCR RSPRN RVPRN ORN

ALBAIDAAM 6324 5909 415 6,6 14400 8491 70,81 0,20 75 7607 88 50 0
ALBAIDABM 4405 4330 75 1,7 10723 6393 3,53 0,08 8 449 60 35 0
P01M 3 3 0 0,0 9 6 0,01 0,00 2 6 0 0 0
P02M 66 66 0 0,0 202 136 0,02 0,00 4 24 0 3 0
P03M 57 49 8 14,0 160 111 0,10 0,02 4 57 7 7 0
P04M 46 41 5 10,9 123 82 0,04 0,01 4 34 1 8 0
P05M 35 35 0 0,0 158 123 0,03 0,01 3 18 12 4 0
P06M 60 60 0 0,0 151 91 0,06 0,01 3 11 4 8 0
P07M 91 89 2 2,2 217 128 0,05 0,01 3 38 6 8 0
P08M 90 86 4 4,4 185 99 0,06 0,01 6 23 3 15 1
P09M 48 43 5 10,4 119 76 0,02 0,00 3 11 6 4 1
P10M 42 38 4 9,5 126 88 0,02 0,01 3 7 3 4 0
P11M 9 9 0 0,0 32 23 0,01 0,15 2 4 0 0 0
P12M 10 10 0 0,0 26 16 0,01 0,00 3 4 0 2 0
P13M 5 5 0 0,0 29 24 0,30 0,00 1 0 0 0 0
P14M 129 106 23 17,8 277 171 0,17 0,16 5 66 15 17 1
P15M 46 39 7 15,2 261 222 0,10 0,00 6 102 45 8 1
P16M 113 106 7 6,2 291 185 0,26 0,04 5 56 8 20 1
P17M 43 36 7 16,3 148 112 0,06 0,02 5 33 11 9 1
P18M 22 10 12 54,5 149 139 0,12 0,01 8 117 22 7 1
P19M 90 80 10 11,1 269 189 0,23 0,01 6 49 17 14 0
P20M 255 222 33 12,9 573 351 0,44 0,19 5 57 3 22 1
P21M 259 245 14 5,4 591 346 1,02 0,10 10 292 29 32 1
P22M 475 438 37 7,8 1103 665 0,50 0,04 5 120 4 35 0
P23M 360 360 0 0,0 762 402 0,34 0,04 4 160 8 30 0
P24M 238 226 12 5,0 586 360 0,68 0,06 9 195 15 28 1
DEGREE0M 109 109 0 0,0 223 114 0,01 0,00 1 0 0 0 0
DEGREE1M 115 115 0 0,0 873 758 0,05 0,00 8 71 19 4 0
DEGREE2M 274 274 0 0,0 948 674 0,02 0,00 2 10 8 2 0
DEGREE3M 172 172 0 0,0 627 455 0,04 0,00 5 30 18 4 0
DEGREE4M 210 210 0 0,0 1065 855 0,04 0,00 4 33 7 5 0
DEGREE5M 316 268 48 15,2 1113 845 0,04 0,01 5 27 9 7 0
DEGREE6M 166 166 0 0,0 921 755 0,03 0,00 4 31 10 4 0
DEGREE7M 275 235 40 14,5 1231 996 0,07 0,00 7 64 0 9 0
DEGREE8M 478 457 21 4,4 1187 730 0,05 0,00 5 27 11 10 1
DEGREE9M 160 160 0 0,0 757 597 0,44 0,00 14 250 86 9 0
DEGREE10M 0 0 0 0,0 0 0 0,23 0,00 11 192 34 4 0
DEGREE11M 409 392 17 4,2 1362 970 0,77 0,01 14 441 60 8 0
DEGREE12M 286 271 15 5,2 1146 875 0,29 0,02 8 161 103 10 0
DEGREE13M 728 662 66 9,1 1754 1092 0,42 0,02 9 207 61 11 0
DEGREE14M 810 810 0 0,0 2148 1338 0,20 0,02 4 70 33 12 0
DEGREE15M 722 649 73 10,1 1887 1238 0,31 0,02 7 99 15 20 1
DEGREE16M 1022 965 57 5,6 2405 1440 0,24 0,04 5 153 21 15 1
DEGREE17M 1122 1010 112 10,0 2580 1570 0,24 0,04 6 97 10 23 0
DEGREE18M 533 508 25 4,7 1677 1169 1,33 0,04 8 324 118 8 1
DEGREE19M 517 472 45 8,7 1623 1151 3,02 0,05 12 483 254 14 1
DEGREE20M 470 440 30 6,4 1553 1113 8,19 0,03 22 1156 166 12 1
DEGREE21M 1017 939 78 7,7 2540 1601 1,70 0,15 8 333 111 22 1
DEGREE22M 1014 875 139 13,7 2571 1696 1,68 0,40 7 195 62 18 0
DEGREE23M 995 878 117 11,8 2537 1659 4,11 0,09 13 528 70 31 1
DEGREE24M 1504 1384 120 8,0 3338 1954 0,85 0,07 4 125 34 30 0
DEGREE25M 1328 1313 15 1,1 3219 1906 1,02 0,05 5 251 42 35 1
DEGREE26M 1674 1499 175 10,5 3757 2258 1,57 0,09 6 44 8 36 1
DEGREE27M 573 497 76 13,3 2175 1678 51,76 0,13 36 2781 843 32 1
DEGREE28M 845 678 167 19,8 2413 1735 228,67 0,70 89 6004 938 32 1
DEGREE29M 582 424 158 27,1 2149 1725 42,34 1,07 25 1900 302 31 1
DEGREE30M 1414 1350 64 4,5 3485 2135 4,68 0,13 5 233 54 44 1
DEGREE31M 1549 1350 199 12,8 3721 2371 21,10 2,53 14 1240 141 54 0
DEGREE32M 1087 909 178 16,4 3119 2210 4,08 0,27 5 195 72 36 0
DEGREE33M 2090 1957 133 6,4 4880 2923 7,22 4,44 8 452 50 51 0
DEGREE34M 1828 1640 188 10,3 4256 2616 24,13 0,12 19 2085 62 61 0
DEGREE35M 1942 1783 159 8,2 4513 2730 11,52 0,56 9 378 34 62 0

Table 4: table experiments II

15
PN LRV HV DIF PDRH TBHS TCHS LRT HT LRIN LRCR RSPRN RVPRN ORN

GRID0M 0 0 0 0,0 0 0 0,16 0,00 1 0 0 0 0

GRID1M 0 0 0 0,0 0 0 0,01 0,00 2 6 0 0 0
GRID2M 0 0 0 0,0 6 6 0,02 0,00 4 6 6 0 0
GRID3M 2 2 0 0,0 6 4 0,03 0,00 5 16 14 0 0
GRID4M 0 0 0 0,0 0 0 0,04 0,00 5 50 4 0 0
GRID5M 4 4 0 0,0 14 10 0,05 0,00 9 63 13 1 0
GRID6M 9 8 1 11,1 24 16 0,04 0,01 6 23 23 1 0
GRID7M 1 1 0 0,0 17 16 0,05 0,01 6 56 9 1 0
GRID8M 4 4 0 0,0 14 10 0,05 0,00 8 62 17 0 0
GRID9M 2 2 0 0,0 20 18 0,63 0,01 19 270 108 0 0
GRID10M 0 0 0 0,0 0 0 1,23 0,00 36 303 140 0 0
GRID11M 4 4 0 0,0 28 24 0,59 0,01 17 324 117 3 0
GRID12M 16 11 5 31,3 45 34 0,33 0,13 7 171 19 5 1
GRID13M 13 10 3 23,1 44 34 0,60 0,05 13 275 72 5 0
GRID14M 15 12 3 20,0 50 38 1,20 0,35 14 310 58 8 1
GRID15M 26 22 4 15,4 64 42 0,21 0,12 5 94 5 14 1
GRID16M 20 17 3 15,0 51 34 0,49 0,11 10 236 22 9 1
GRID17M 24 21 3 12,5 57 36 0,30 0,09 5 59 14 13 1
GRID18M 8 8 0 0,0 46 38 14,46 0,02 36 1579 289 4 0
GRID19M 8 2 6 75,0 36 34 32,05 0,07 71 2213 390 2 1
GRID20M 9 8 1 11,1 48 40 62,40 0,04 123 3250 573 12 0
GRID21M 33 30 3 9,1 92 62 11,66 0,54 30 1339 332 15 1
GRID22M 32 25 7 21,9 81 56 42,95 0,54 28 1434 129 16 1
GRID23M 33 31 2 6,1 93 62 25,48 0,20 12 496 129 13 1
GRID24M 58 56 2 3,4 132 76 1,72 0,13 6 207 46 23 0
GRID25M 48 44 4 8,3 112 68 5,11 1,32 18 1055 80 27 0
GRID26M 58 55 3 5,2 129 74 2,00 0,39 7 385 44 15 0
GRID27M 14 9 5 35,7 67 58 62,13 0,13 43 2191 461 9 1
GRID28M 24 20 4 16,7 96 76 365,76 0,69 113 6705 1151 16 0
GRID29M 15 10 5 33,3 84 74 191,26 2,15 82 3565 1040 11 1
GRID30M 51 47 4 7,8 137 90 6,81 2,81 7 418 204 20 1
GRID31M 54 52 2 3,7 138 86 16,20 0,93 13 656 162 22 0
GRID32M 60 55 5 8,3 155 100 3,60 5,23 5 206 52 24 0
GRID33M 94 90 4 4,3 210 120 6,35 0,91 7 425 30 34 0
GRID34M 86 81 5 5,8 199 118 7,67 2,23 10 580 66 36 1
GRID35M 90 84 6 6,7 200 116 7,46 0,99 7 395 57 42 1
RANDOM0M 1742 1742 0 0,0 15682 13940 0,06 0,00 10 49 10 4 0
RANDOM1M 4297 3853 444 10,3 13786 9933 0,07 0,00 8 83 11 7 1
RANDOM2M 5638 5638 0 0,0 34427 28789 0,08 0,00 9 81 21 1 0
RANDOM3M 18453 18453 0 0,0 49481 31028 0,09 0,00 8 60 34 3 0
RANDOM4M 17316 17316 0 0,0 43923 26607 0,06 0,00 6 48 15 5 0
RANDOM5M 298 298 0 0,0 30621 30323 0,63 0,01 22 469 107 12 0
RANDOM6M 12478 12478 0 0,0 53765 41287 1,00 0,01 35 536 98 5 0
RANDOM7M 9405 9405 0 0,0 48056 38651 0,27 0,01 15 184 94 10 0
RANDOM8M 14847 14847 0 0,0 65952 51105 0,56 0,01 19 438 53 4 0
RANDOM9M 17523 17523 0 0,0 56830 39307 0,27 0,01 10 191 46 6 0
RANDOM10M 17405 17405 0 0,0 57193 39788 1,24 0,01 19 448 89 7 0
RANDOM11M 7125 7125 0 0,0 35769 28644 0,58 0,00 20 228 132 4 0
RANDOM12M 1493 1493 0 0,0 33011 31518 0,60 0,00 19 331 39 6 0
RANDOM13M 32619 30323 2296 7,0 89523 59200 0,37 0,01 8 93 55 8 1
RANDOM14M 30757 27063 3694 12,0 75649 48586 0,50 0,01 8 172 53 12 0
RANDOM15M 27953 27481 472 1,7 101508 74027 2,38 0,02 19 688 49 18 1
RANDOM16M 10566 10533 33 0,3 68246 57713 1,25 0,02 15 392 117 6 0
RANDOM17M 4290 3296 994 23,2 10263 6967 3,51 0,00 49 1106 79 16 0
RANDOM18M 28510 27239 1271 4,5 84083 56844 0,58 0,02 8 254 67 13 1
RANDOM19M 26873 26873 0 0,0 77701 50828 0,22 0,01 3 1 2 5 0

Table 5: table experiments II continuation

16