4.5 Conclusion et perspectives
Nous étudions la résolution du GTSP par un
algorithme mémétique dans lequel l'opérateur de croisement
se base sur une recherche à grand voisinage dont l'opérateur,
appelé Dropstar, a été présenté
dans le chapitre 2. Notre principale contribution est l'originalité de
notre opérateur de croisement. Nous montrons par les résultats
expérimentaux que notre algorithme est robuste et offre un bon compromis
entre temps de calcul et qualité des solutions. Il résout 41
instances sur 41 à l'optimal et les solutions renvoyées ne sont
jamais à plus de 0,75 % de pourcentage d'erreur par rapport aux
solutions optimales. Nous montrons donc que l'hybridation entre un
opérateur de recherche locale à grand voisinage et un algorithme
génétique (l'ensemble définissant un algorithme
mémétique) est une méthode qui semble efficace.
|
instance
|
opt
|
best
|
mean gap
|
min gap
|
max gap
|
CPU time
|
|
10att48.gtsp
|
5394
|
5
|
0.00
|
0.00
|
0.00
|
0.76
|
|
10gr48.gtsp
|
1834
|
5
|
0.00
|
0.00
|
0.00
|
0.79
|
|
10hk48.gtsp
|
6386
|
5
|
0.00
|
0.00
|
0.00
|
0.50
|
|
11eil51.gtsp
|
174
|
5
|
0.00
|
0.00
|
0.00
|
0.81
|
|
12brazil58.gtsp
|
15332
|
5
|
0.00
|
0.00
|
0.00
|
0.65
|
|
14st70.gtsp
|
316
|
5
|
0.00
|
0.00
|
0.00
|
0.93
|
|
16eil76.gtsp
|
209
|
5
|
0.00
|
0.00
|
0.00
|
1.00
|
|
16pr76.gtsp
|
64925
|
5
|
0.00
|
0.00
|
0.00
|
1.17
|
|
20kroA100.gtsp
|
9711
|
5
|
0.00
|
0.00
|
0.00
|
1.81
|
|
20kroB100.gtsp
|
10328
|
5
|
0.00
|
0.00
|
0.00
|
2.17
|
|
20kroC100.gtsp
|
9554
|
5
|
0.00
|
0.00
|
0.00
|
1.85
|
|
20kroD100.gtsp
|
9450
|
5
|
0.00
|
0.00
|
0.00
|
2.77
|
|
20kroE100.gtsp
|
9523
|
5
|
0.00
|
0.00
|
0.00
|
1.81
|
|
20rat99.gtsp
|
497
|
5
|
0.00
|
0.00
|
0.00
|
3.89
|
|
20rd100.gtsp
|
3650
|
5
|
0.00
|
0.00
|
0.00
|
2.91
|
|
21eil101.gtsp
|
249
|
5
|
0.00
|
0.00
|
0.00
|
2.09
|
|
21lin105.gtsp
|
8213
|
5
|
0.00
|
0.00
|
0.00
|
3.18
|
|
22pr107.gtsp
|
27898
|
5
|
0.00
|
0.00
|
0.00
|
4.78
|
|
24gr120.gtsp
|
2769
|
5
|
0.00
|
0.00
|
0.00
|
2.34
|
|
25pr124.gtsp
|
36605
|
5
|
0.00
|
0.00
|
0.00
|
2.84
|
|
26bier127.gtsp
|
72418
|
5
|
0.00
|
0.00
|
0.00
|
3.35
|
|
28pr136.gtsp
|
42570
|
5
|
0.00
|
0.00
|
0.00
|
4.23
|
|
29pr144.gtsp
|
45886
|
5
|
0.00
|
0.00
|
0.00
|
5.42
|
|
30kroA150.gtsp
|
11018
|
5
|
0.00
|
0.00
|
0.00
|
5.95
|
|
30kroB150.gtsp
|
12196
|
5
|
0.00
|
0.00
|
0.00
|
5.02
|
|
31pr152.gtsp
|
51576
|
5
|
0.00
|
0.00
|
0.00
|
5.24
|
|
32u159.gtsp
|
22664
|
5
|
0.00
|
0.00
|
0.00
|
5.58
|
|
39rat195.gtsp
|
854
|
5
|
0.00
|
0.00
|
0.00
|
11.01
|
|
40d198.gtsp
|
10557
|
5
|
0.00
|
0.00
|
0.00
|
10.15
|
|
40kroA200.gtsp
|
13406
|
5
|
0.00
|
0.00
|
0.00
|
10.41
|
|
40kroB200.gtsp
|
13111
|
5
|
0.00
|
0.00
|
0.00
|
10.81
|
|
45ts225.gtsp
|
68340
|
3
|
0.04
|
0.00
|
0.09
|
31.45
|
|
46pr226.gtsp
|
64007
|
5
|
0.00
|
0.00
|
0.00
|
8.25
|
|
53gil262.gtsp
|
1013
|
2
|
0.14
|
0.00
|
0.3
|
24.34
|
|
53pr264.gtsp
|
29549
|
5
|
0.00
|
0.00
|
0.00
|
18.27
|
|
60pr299.gtsp
|
22615
|
5
|
0.00
|
0.00
|
0.00
|
21.25
|
|
64lin318.gtsp
|
20765
|
5
|
0.00
|
0.00
|
0.00
|
26.33
|
|
80rd400.gtsp
|
6361
|
1
|
0.42
|
0.00
|
0.75
|
32.21
|
|
84fl417.gtsp
|
9651
|
5
|
0.00
|
0.00
|
0.00
|
31.63
|
|
88pr439.gtsp
|
60099
|
5
|
0.00
|
0.00
|
0.00
|
42.55
|
|
89pcb442.gtsp
|
21657
|
1
|
0.19
|
0.00
|
0.38
|
62.53
|
TABLE 4.1 - Résultats
expérimentaux : qualité des solutions sur instances
fermées
|
instance
|
best
|
mean gap
|
min gap
|
max gap
|
CPU time
|
|
99d493.gtsp
|
20117.2
|
-0.03
|
-0.28
|
0.23
|
166.11
|
|
107att532.gtsp
|
13510.8
|
-0.30
|
-0.34
|
-0.17
|
137.54
|
|
107si535.gtsp
|
13513.2
|
-0.01
|
-0.05
|
0.06
|
90.98
|
|
113pa561.gtsp
|
1051.2
|
-0.84
|
-1.26
|
-0.21
|
149.43
|
|
115rat575.gtsp
|
2414.8
|
0.04
|
-0.45
|
0.09
|
157.01
|
|
131p654.gtsp
|
27439
|
-0.03
|
-0.04
|
0.00
|
144.95
|
|
132d657.gtsp
|
22599
|
-0.15
|
-0.43
|
0.28
|
259.11
|
|
145u724.gtsp
|
21657
|
0.45
|
0.24
|
0.66
|
218.66
|
|
157rat783.gtsp
|
3300.2
|
-0.07
|
-0.58
|
0.12
|
391.79
|
|
201pr1002.gtsp
|
114582.2
|
0.03
|
-0.18
|
0.16
|
513.48
|
|
207si1032.gtsp
|
22388.8
|
-0.26
|
-0.33
|
-0.17
|
616.28
|
|
212u1060.gtsp
|
108390.4
|
-0.92
|
-1.58
|
0.19
|
762.86
|
|
217vm1084.gtsp
|
131884.6
|
-0.26
|
-0.65
|
0.09
|
583.44
|
TABLE 4.2 - Résultats
expérimentaux : qualité des solutions sur instances
ouvertes
|
instance
|
mrOX
|
Bontoux
|
|
99d493.gtsp
|
20117.2
|
20061
|
|
107att532.gtsp
|
13510.8
|
13464
|
|
107si535.gtsp
|
13513.2
|
13506
|
|
113pa561.gtsp
|
1051.2
|
1038
|
|
115rat575.gtsp
|
2414.8
|
2404
|
|
131p654.gtsp
|
27439
|
27428
|
|
132d657.gtsp
|
22599
|
22502
|
|
157rat783.gtsp
|
3300.2
|
3281
|
|
201pr1002.gtsp
|
114582.2
|
114374
|
|
207si1032.gtsp
|
22388.8
|
22315
|
|
212u1060.gtsp
|
108390.4
|
106677
|
|
217vm1084.gtsp
|
131884.6
|
131028
|
TABLE 4.3 - Résultats
expérimentaux : meilleures solutions connues
|
name
|
opt
|
Dropstar
Gap CPU
|
One-Point
Gap CPU
|
|
10att48.gtsp
|
5394
|
0.00
|
0.76
|
0.00
|
0.15
|
|
10gr48.gtsp
|
1834
|
0.00
|
0.79
|
0.00
|
0.14
|
|
10hk48.gtsp
|
6386
|
0.00
|
0.50
|
0.00
|
0.17
|
|
11eil51.gtsp
|
174
|
0.00
|
0.81
|
0.00
|
0.15
|
|
12brazil58.gtsp
|
15332
|
0.00
|
0.65
|
0.00
|
0.24
|
|
14st70.gtsp
|
316
|
0.00
|
0.93
|
0.00
|
0.20
|
|
16eil76.gtsp
|
209
|
0.00
|
1.00
|
0.00
|
0.17
|
|
16pr76.gtsp
|
64925
|
0.00
|
1.17
|
0.00
|
0.25
|
|
20kroA100.gtsp
|
9711
|
0.00
|
1.81
|
0.00
|
0.27
|
|
20kroB100.gtsp
|
10328
|
0.00
|
2.17
|
0.00
|
0.27
|
|
20kroC100.gtsp
|
9554
|
0.00
|
1.85
|
0.00
|
0.27
|
|
20kroD100.gtsp
|
9450
|
0.00
|
2.77
|
0.00
|
0.27
|
|
20kroE100.gtsp
|
9523
|
0.00
|
1.81
|
0.00
|
0.53
|
|
20rat99.gtsp
|
497
|
0.00
|
3.89
|
0.00
|
0.44
|
|
20rd100.gtsp
|
3650
|
0.00
|
2.91
|
0.36
|
0.40
|
|
21eil101.gtsp
|
249
|
0.00
|
2.09
|
0.56
|
0.61
|
|
21lin105.gtsp
|
8213
|
0.00
|
3.18
|
0.00
|
0.36
|
|
22pr107.gtsp
|
27898
|
0.00
|
4.78
|
0.08
|
0.33
|
|
24gr120.gtsp
|
2769
|
0.00
|
2.34
|
0.62
|
0.07
|
|
25pr124.gtsp
|
36605
|
0.00
|
2.84
|
0.00
|
0.44
|
|
26bier127.gtsp
|
72418
|
0.00
|
3.35
|
0.00
|
0.42
|
|
28pr136.gtsp
|
42570
|
0.00
|
4.23
|
0.72
|
0.86
|
|
29pr144.gtsp
|
45886
|
0.00
|
5.42
|
0.00
|
0.54
|
|
30kroA150.gtsp
|
11018
|
0.00
|
5.95
|
0.01
|
1.14
|
|
30kroB150.gtsp
|
12196
|
0.00
|
5.02
|
0.33
|
1.45
|
|
31pr152.gtsp
|
51576
|
0.00
|
5.24
|
0.00
|
0.68
|
|
32u159.gtsp
|
22664
|
0.00
|
5.58
|
0.43
|
0.83
|
|
39rat195.gtsp
|
854
|
0.00
|
11.01
|
1.05
|
1.63
|
|
40d198.gtsp
|
10557
|
0.00
|
10.15
|
0.07
|
1.41
|
|
40kroA200.gtsp
|
13406
|
0.00
|
10.41
|
0.21
|
1.65
|
|
40kroB200.gtsp
|
13111
|
0.00
|
10.81
|
0.15
|
2.09
|
|
45ts225.gtsp
|
68340
|
0.04
|
31.45
|
0.29
|
1.91
|
|
46pr226.gtsp
|
64007
|
0.00
|
8.25
|
0.00
|
1.03
|
|
53gil262.gtsp
|
1013
|
0.14
|
26.34
|
1.8
|
2.35
|
|
53pr264.gtsp
|
29549
|
0.00
|
18.27
|
0.46
|
2.43
|
|
60pr299.gtsp
|
22615
|
0.00
|
21.25
|
0.20
|
5.79
|
|
64lin318.gtsp
|
20765
|
0.00
|
26.33
|
0.59
|
4.67
|
|
80rd400.gtsp
|
6361
|
0.42
|
32.21
|
1.45
|
10.12
|
|
84fl417.gtsp
|
9651
|
0.00
|
31.63
|
0.00
|
3.41
|
|
88pr439.gtsp
|
60099
|
0.00
|
42.65
|
0.09
|
10.56
|
|
89pcb442.gtsp
|
21657
|
0.19
|
62.53
|
1.26
|
11.22
|
TABLE 4.4 - Résultats
expérimentaux : comparaisons des opérateurs de croisement sur
instances fermées
|
name
|
best
|
Dropstar
Gap CPU
|
One-Point Gap CPU
|
|
99d493.gtsp
|
20117.2
|
-0.03
|
166.11
|
0.03
|
12.1
|
|
107att532.gtsp
|
13510.8
|
-0.30
|
121.54
|
0.21
|
18.73
|
|
107si535.gtsp
|
13513.2
|
-0.01
|
90.98
|
0.01
|
10.58
|
|
113pa561.gtsp
|
1051.2
|
-0.84
|
149.43
|
1.58
|
11.66
|
|
115rat575.gtsp
|
2414.8
|
0.04
|
157.01
|
5.01
|
17.99
|
|
131p654.gtsp
|
27439
|
-0.03
|
144.95
|
-0.01
|
10.95
|
|
132d657.gtsp
|
22599
|
-0.15
|
259.11
|
1.15
|
27.2
|
|
145u724.gtsp
|
17370
|
0.45
|
218.66
|
2.76
|
45.31
|
|
157rat783.gtsp
|
3300.2
|
-0.07
|
391.79
|
3.68
|
42.76
|
|
201pr1002.gtsp
|
114582.2
|
0.03
|
513.48
|
1.49
|
76.54
|
|
207si1032.gtsp
|
22388.8
|
-0.26
|
616.28
|
0.33
|
75
|
|
212u1060.gtsp
|
108390.4
|
-0.92
|
762.86
|
-0.28
|
88.6
|
|
217vm1084.gtsp
|
131884.6
|
-0.26
|
583.44
|
0.3
|
89.87
|
TABLE 4.5 - Résultats
expérimentaux : comparaisons des opérateurs de croisement sur
instances ouvertes
|
instance
|
Bontoux
Gap CPU
|
mrOX
Gap CPU
|
Snyder
Gap CPU
|
GI
Gap CPU
|
BC CPU
|
|
10att48
|
0
|
0.76
|
0
|
0.36
|
0
|
0.18
|
*
|
*
|
2.1
|
|
10gr48
|
0
|
0.79
|
0
|
0.32
|
0
|
0.08
|
*
|
*
|
1.9
|
|
10hk48
|
0
|
0.5
|
0
|
0.31
|
0
|
0.08
|
*
|
*
|
3.8
|
|
11eil51
|
0
|
0.81
|
0
|
0.26
|
0
|
0.08
|
0
|
0.3
|
2.9
|
|
12brazil58
|
0
|
0.65
|
0
|
0.78
|
0
|
0.1
|
*
|
*
|
3
|
|
14st70
|
0
|
0.93
|
0
|
0.35
|
0
|
0.07
|
0
|
1.7
|
7.3
|
|
16eil76
|
0
|
1
|
0
|
0.37
|
0
|
0.11
|
0
|
2.2
|
9.4
|
|
16pr76
|
0
|
1.17
|
0
|
0.45
|
0
|
0.16
|
0
|
2.5
|
12.9
|
|
20kroA100
|
0
|
1.81
|
0
|
0.5
|
0
|
0.24
|
0
|
5
|
51.5
|
|
20kroB100
|
0
|
2.17
|
0
|
0.63
|
0
|
0.25
|
0
|
6.8
|
18.4
|
|
20kroC100
|
0
|
1.85
|
0
|
0.6
|
0
|
0.22
|
0
|
6.4
|
22.2
|
|
20kroD100
|
0
|
2.77
|
0
|
0.62
|
0
|
0.23
|
0
|
6.5
|
14.4
|
|
20kroE100
|
0
|
1.81
|
0
|
0.67
|
0
|
0.43
|
0
|
8.6
|
14.3
|
|
20rat99
|
0
|
3.89
|
0
|
0.58
|
0
|
0.15
|
0
|
6.7
|
13
|
|
20rd100
|
0
|
2.91
|
0
|
0.51
|
0
|
0.29
|
0.08
|
7.3
|
16.6
|
|
21eil101
|
0
|
2.09
|
0
|
0.48
|
0
|
0.18
|
0.4
|
5.2
|
25.6
|
|
21lin105
|
0
|
3.18
|
0
|
0.6
|
0
|
0.33
|
0
|
14.4
|
16.4
|
|
22pr107
|
0
|
4.78
|
0
|
0.53
|
0
|
0.2
|
0
|
8.7
|
7.4
|
|
24gr120
|
0
|
2.34
|
0
|
0.66
|
0
|
0.32
|
*
|
*
|
41.9
|
|
25pr124
|
0
|
2.84
|
0
|
0.68
|
0
|
0.26
|
0.43
|
12.2
|
25.9
|
|
26bier127
|
0
|
3.35
|
0
|
0.78
|
0
|
0.28
|
5.55
|
36.1
|
23.6
|
|
28pr136
|
0
|
4.23
|
0
|
0.79
|
0.16
|
0.36
|
1.28
|
12.5
|
43
|
|
29pr144
|
0
|
5.42
|
0
|
1
|
0
|
0.44
|
0
|
16.3
|
8.2
|
|
30kroA150
|
0
|
5.95
|
0
|
0.98
|
0
|
0.32
|
0
|
17.8
|
100.3
|
|
30kroB150
|
0
|
5.02
|
0
|
0.98
|
0
|
0.71
|
0
|
14.2
|
60.6
|
|
31pr152
|
0
|
5.24
|
0
|
0.97
|
0
|
0.38
|
0.47
|
17.6
|
94.8
|
|
32u159
|
0
|
5.58
|
0
|
0.98
|
0
|
0.55
|
2.6
|
18.5
|
146.4
|
|
39rat195
|
0
|
11.01
|
0
|
1.37
|
0
|
1.33
|
0
|
37.2
|
245.9
|
|
40d198
|
0
|
10.15
|
0
|
1.63
|
0.07
|
1.47
|
0.6
|
60.4
|
763.1
|
|
40kroA200
|
0
|
10.41
|
0
|
1.66
|
0
|
0.95
|
0
|
29.7
|
187.4
|
|
40kroB200
|
0
|
10.81
|
0.05
|
1.63
|
0.01
|
1.29
|
0
|
35.8
|
268.5
|
|
45ts225
|
0.04
|
31.45
|
0.14
|
1.71
|
0.28
|
1.09
|
0.61
|
89
|
37875.9
|
|
46pr226
|
0
|
8.25
|
0
|
1.54
|
0
|
1.09
|
0
|
25.5
|
106.9
|
|
53gil262
|
0.14
|
24.34
|
0.45
|
3.64
|
0.55
|
3.05
|
5.03
|
115.4
|
6624.1
|
|
53pr264
|
0
|
18.27
|
0
|
2.36
|
0.09
|
2.72
|
0.36
|
64.4
|
337
|
|
60pr299
|
0
|
21.25
|
0.05
|
4.59
|
0.16
|
4.08
|
2.23
|
90.3
|
812.8
|
|
64lin318
|
0
|
26.33
|
0
|
8.08
|
0.54
|
5.39
|
4.59
|
206.8
|
1671.9
|
|
80rd400
|
0.42
|
32.21
|
0.58
|
14.58
|
0.72
|
10.27
|
1.23
|
403.5
|
7021.4
|
|
84fl417
|
0
|
31.63
|
0.04
|
8.15
|
0.06
|
6.18
|
0.48
|
427.1
|
16719.4
|
|
88pr439
|
0
|
42.55
|
0
|
19.06
|
0.83
|
15.09
|
3.52
|
611
|
5422.8
|
|
89pcb442
|
0.19
|
62.53
|
0.01
|
23.43
|
1.23
|
11.74
|
5.91
|
567.7
|
58770.5
|
|
Averages
|
0.02
|
10.12
|
0.03
|
2.69
|
0.11
|
1.77
|
0.98
|
83.09
|
3356.47
|
|
Essais
|
5
|
|
5
|
|
5
|
|
1
|
|
1
|
TABLE 4.6 - Résultats
expérimentaux : comparatifs entre plusieurs algorithmes
|
instance
|
Min
|
Dropstar
Mean CPU Time
|
Min
|
One-Point
Mean CPU Time
|
|
baf10att48.gtsp
|
1774
|
1774
|
0.68
|
1774
|
1774
|
0.15
|
|
baf10gr48.gtsp
|
1182
|
1182
|
1.33
|
1182
|
1182
|
0.16
|
|
baf10hk48.gtsp
|
2112
|
2112
|
0.77
|
2112
|
2112
|
0.17
|
|
baf11eil51.gtsp
|
86
|
86
|
1.52
|
86
|
86
|
0.15
|
|
baf12brazil58.gtsp
|
3378
|
3378
|
2.16
|
3378
|
3378
|
0.23
|
|
baf14st70.gtsp
|
141
|
141
|
4.32
|
141
|
141
|
0.26
|
|
baf16eil76.gtsp
|
107
|
107.2
|
4.79
|
107
|
110.2
|
0.47
|
|
baf16pr76.gtsp
|
18349
|
18349
|
5.06
|
18349
|
18481
|
0.45
|
|
baf20kroA100.gtsp
|
5044
|
5076.2
|
22
|
5117
|
5254.4
|
0.6
|
|
baf20kroB100.gtsp
|
5395
|
5395
|
12.64
|
5413
|
5793.8
|
0.58
|
|
baf20kroC100.gtsp
|
5799
|
5804.8
|
25.09
|
5799
|
5849.6
|
0.61
|
|
baf20kroD100.gtsp
|
5266
|
5298.2
|
23.31
|
5266
|
5360
|
0.62
|
|
baf20kroE100.gtsp
|
5449
|
5449
|
6.98
|
5449
|
5449.4
|
0.41
|
|
baf20rat99.gtsp
|
230
|
231.6
|
13.91
|
230
|
235.8
|
0.41
|
|
baf20rd100.gtsp
|
1747
|
1747.4
|
7.9
|
1747
|
1793.8
|
0.7
|
|
baf21eil101.gtsp
|
105
|
105
|
4.8
|
105
|
105
|
0.32
|
|
baf21lin105.gtsp
|
2758
|
2758
|
14.05
|
2758
|
2764.4
|
0.37
|
|
baf22pr107.gtsp
|
6849
|
6879.6
|
4.97
|
6849
|
6889.8
|
0.39
|
|
baf24gr120.gtsp
|
1412
|
1434
|
18.03
|
1414
|
1440.8
|
0.9
|
|
baf25pr124.gtsp
|
10745
|
10745
|
8.3
|
10745
|
10745
|
0.38
|
|
baf26bier127.gtsp
|
11740
|
11973.2
|
5.92
|
12164
|
12258.8
|
0.59
|
|
baf28pr136.gtsp
|
17824
|
17857.8
|
22.88
|
17824
|
17959.2
|
0.55
|
|
baf29pr144.gtsp
|
14070
|
14071
|
26.55
|
14070
|
14269
|
0.8
|
|
baf30kroA150.gtsp
|
7076
|
7316.4
|
52.39
|
7248
|
7319
|
2.18
|
|
baf30kroB150.gtsp
|
5855
|
5992.6
|
31.27
|
6055
|
6147
|
1.63
|
|
baf31pr152.gtsp
|
13002
|
13154.6
|
29.09
|
13002
|
13223.8
|
1.09
|
|
baf32u159.gtsp
|
7301
|
7309.2
|
27.89
|
7326
|
7595.8
|
0.78
|
|
baf39rat195.gtsp
|
477
|
477.4
|
144.94
|
477
|
480
|
1.09
|
TABLE 4.7 - Résultats
expérimentaux : comparatifs des opérateurs de croisement sur de
nouvelles instances (1)
|
instance
|
Min
|
Dropstar
Mean CPU Time
|
Min
|
One-Point
Mean CPU Time
|
|
baf40d198.gtsp
|
1500
|
1555.4
|
18.71
|
1514
|
1555.6
|
1.54
|
|
baf40kroA200.gtsp
|
7126
|
7416.8
|
82.2
|
7316
|
7537.2
|
2.82
|
|
baf40kroB200.gtsp
|
7375
|
7544.6
|
152.83
|
7420
|
7732.4
|
2.99
|
|
baf41gr202.gtsp
|
3656
|
3656
|
16.57
|
3656
|
3656
|
1.32
|
|
baf45ts225.gtsp
|
26059
|
26359.6
|
113.32
|
26076
|
26369.2
|
1.79
|
|
baf46pr226.gtsp
|
13555
|
13555
|
86.31
|
13555
|
13555
|
0.95
|
|
baf53gil262.gtsp
|
591
|
624.8
|
223.63
|
642
|
659.2
|
3.06
|
|
baf53pr264.gtsp
|
7716
|
7748
|
40.56
|
7772
|
7821.6
|
2.06
|
|
baf60pr299.gtsp
|
10137
|
10795.4
|
265.09
|
10933
|
11771.8
|
6.11
|
|
baf64lin318.gtsp
|
7762
|
8113
|
259.89
|
8054
|
8216.6
|
5.74
|
|
baf80rd400.gtsp
|
3725
|
3899.2
|
635.63
|
3782
|
3919.6
|
12.34
|
|
baf84fl417.gtsp
|
2267
|
2335.2
|
422.72
|
2296
|
2572.6
|
7.93
|
|
baf87gr431.gtsp
|
10787
|
10861.4
|
105.07
|
10825
|
10917.8
|
7.69
|
|
baf88pr439.gtsp
|
14292
|
15280.2
|
325.86
|
15334
|
16579
|
8.99
|
|
baf89pcb442.gtsp
|
10266
|
10707.8
|
464.16
|
11716
|
12855
|
17.63
|
|
baf99d493.gtsp
|
3156
|
3232.4
|
217.08
|
3273
|
3321.6
|
16.16
|
|
baf107att532.gtsp
|
4392
|
4529.6
|
508.4
|
4530
|
4705
|
16.4
|
|
baf107si535.gtsp
|
9059
|
9129.8
|
444.81
|
9258
|
9741
|
22.35
|
|
baf113pa561.gtsp
|
460
|
470.4
|
817.12
|
478
|
512.4
|
12.22
|
|
baf115rat575.gtsp
|
1366
|
1376
|
382.36
|
1419
|
1477.6
|
11.92
|
|
baf131p654.gtsp
|
5956
|
6033.6
|
833.75
|
6130
|
6225.2
|
18.3
|
|
baf132d657.gtsp
|
8821
|
9377.6
|
421.54
|
8870
|
11216.8
|
21.75
|
|
baf145u724.gtsp
|
10165
|
10253.6
|
877.34
|
13794
|
15031.6
|
45.79
|
|
baf157rat783.gtsp
|
1931
|
2131.4
|
439.91
|
2878
|
2983.6
|
39.77
|
|
baf201pr1002.gtsp
|
50225
|
52626.8
|
754.24
|
56844
|
60121
|
82.89
|
|
baf207si1032.gtsp
|
19108
|
19228.6
|
653.14
|
20066
|
20306.6
|
82.26
|
|
baf212u1060.gtsp
|
44684
|
46058.6
|
731.6
|
52151
|
65714.8
|
97.58
|
|
baf217vm1084.gtsp
|
61595
|
64708.8
|
976.06
|
102578
|
105324
|
114.43
|
TABLE 4.8 - Résultats
expérimentaux : comparatifs des opérateurs de croisement sur de
nouvelles instances (2)
| 
