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)
|