LKH results for Soler's ATSP instances

The table below shows the results of running LKH on 126 asymmetric traveling salesman instances with known optimal solutions from the work by David Soler.

Parameter settings:

     PROBLEM_FILE = file name 
     OPTIMUM = optimal cost 
     MAX_CANDIDATES = 6 SYMMETRIC 
     MOVE_TYPE = 3 
     PATCHING_C = 3 
     PATCHING_A = 2 
     RUNS = 100
     TRACE_LEVEL = 0

Meaning of the column labels:

Name: Name of the instance
|V|: Number of vertices
Opt-cost: Optimum
Best:Best solution cost found in 100 runs (Opt is shown if the best solution cost coincides with the optimum)
a-cost: Average cost over 100 runs (Opt is shown if optimum has been found in all 100 runs)
a-T: Average running time per run measured in seconds on a 2.93 GHz Intel Core i7 iMac

Last updated: April 2, 2012

Name
|V|
Opt-cost
Best
a-cost
a-T
D41140
64
417880
Opt
Opt
0.0
D61440
77
512674
Opt
Opt
0.0
D4940m
51
336325
Opt
Opt
0.0
D81740m
102
664613
Opt
Opt
0.0
D4940
67
422508
Opt
Opt
0.0
D81740
129
809706
Opt
Opt
0.0
D82040m
103
689971
Opt
Opt
0.0
D102240m
121
803595
Opt
Opt
0.0
D82040
122
790971
Opt
Opt
0.0
D102240
163
1027751
Opt
1027751.7
0.0
D102640m
118
815096
Opt
Opt
0.0
D122640m
130
880335
Opt
Opt
0.0
D122940m
148
997772
Opt
Opt
0.0
D102640
139
926142
Opt
Opt
0.0
D122640
150
990448
Opt
Opt
0.0
D122940
209
1316922
Opt
1316922.0
0.0
D143040a
161
1072673
Opt
Opt
0.0
D143340
230
1452339
Opt
Opt
0.0
D143340m
162
1100177
Opt
Opt
0.0
D143040
236
1472328
Opt
1472332.7
2.0
D143040b
186
1210175
Opt
Opt
0.0
D163440a
169
1145914
Opt
Opt
0.0
D163440
226
1452914
Opt
Opt
0.0
D163440b
200
1310767
Opt
Opt
0.0
D183840a
184
1255781
Opt
Opt
0.0
D163740
226
1468709
Opt
Opt
0.0
D183840
258
1652091
Opt
Opt
0.0
D183840b
220
1449912
Opt
1449912.3
0.3
D204240a
213
1438448
Opt
1438448.4
0.1
D184040a
196
1331558
Opt
Opt
0.0
D204240
315
1980807
Opt
Opt
0.1
D184040
262
1686092
Opt
Opt
0.0
D184040b
226
1493759
Opt
Opt
0.0
D204240b
275
1764636
Opt
Opt
0.0
D41141
68
454381
Opt
Opt
0.0
D4941
70
452101
Opt
Opt
0.0
D61441
84
561657
Opt
Opt
0.0
D61641
95
633760
Opt
Opt
0.0
D81741
112
730893
Opt
730899.1
1.0
D82041m
122
804695
Opt
Opt
0.0
D102241m
128
854290
Opt
Opt
0.1
D82041
136
880751
Opt
Opt
0.0
D102241
161
1029382
Opt
Opt
0.0
D122641a
152
1011650
Opt
Opt
0.0
D102641m
152
1009032
Opt
Opt
0.1
D122941m
157
1058436
Opt
Opt
0.0
D122641
207
1306865
Opt
1306865.3
0.4
D102641
188
1199118
Opt
1199125.3
1.1
D122941
192
1243493
Opt
Opt
0.1
D122641b
179
1156769
Opt
1156769.1
0.8
D143041a
164
1103917
Opt
1103918.4
1.6
D143341a
178
1201011
Opt
Opt
0.1
D143341b
211
1376011
Opt
Opt
0.0
D143041
217
1389294
Opt
1389295.7
4.4
D143341
251
1584011
Opt
Opt
0.0
D143041b
185
1219063
Opt
1219070.7
2.1
D163441a
198
1313082
Opt
Opt
0.0
D163441
282
1761528
Opt
Opt
0.9
D163441b
242
1547424
Opt
1547424.4
0.7
D163741m
200
1343095
Opt
Opt
0.4
D163741
235
1530323
Opt
Opt
0.1
D183841a
206
1385166
Opt
Opt
0.0
D183841
278
1769642
Opt
Opt
0.4
D183841b
237
1552379
Opt
1552383.4
2.2
D184041b
242
1591521
Opt
1591521.2
0.6
D184041a
224
1491653
Opt
1491653.1
0.4
D184041
282
1803657
Opt
1803659.5
5.8
D204241a
224
1510820
Opt
Opt
0.4
D204441a
230
1556414
Opt
Opt
0.3
D204241
291
1872362
Opt
1872373.8
4.9
D204441
315
2007744
Opt
2007745.2
1.4
D204241b
258
1693166
Opt
1693166.6
1.6
D204441b
273
1785585
Opt
1785585.6
2.1
D4942
80
517768
Opt
517768.3
0.3
D61642
138
875072
Opt
875078.9
0.9
D61442
120
768117
Opt
Opt
0.1
D81742
127
828368
Opt
828369.7
0.7
D82042
128
849394
Opt
Opt
0.0
D102242
146
963636
Opt
Opt
0.1
D122642m
162
1077557
Opt
1077559.3
1.4
D122942m
172
1149670
Opt
Opt
0.1
D102642
160
1065324
Opt
Opt
0.1
D122642
176
1153625
Opt
1153643.8
2.5
D122942
188
1235878
Opt
1235878.4
0.4
D143042m
184
1224644
Opt
Opt
0.1
D143342m
200
1329993
Opt
Opt
0.6
D143042
211
1369730
Opt
1369769.9
3.6
D143342
237
1525120
Opt
1525121.1
2.9
D163442
253
1622974
Opt
1622974.8
1.3
D163442a
206
1367607
Opt
Opt
0.1
D163742a
214
1432892
Opt
1432892.6
1.1
D163442b
219
1442855
Opt
1442862.6
1.8
D163742b
246
1602916
Opt
Opt
0.1
D163742
301
1888149
Opt
1888158.9
8.7
D183842m
213
1434387
Opt
1434409.2
2.2
D183842
233
1542727
Opt
1542730.3
3.4
D184042m
229
1534827
Opt
Opt
0.1
D184042
270
1753907
Opt
1753907.0
0.9
D204242a
236
1587087
Opt
Opt
0.1
D204242
289
1872624
Opt
1872628.4
6.7
D204242b
265
1742305
Opt
Opt
0.2
D41143
108
695196
Opt
Opt
0.1
D61443
128
822217
Opt
822220.2
0.8
D61643
134
869353
Opt
869354.4
1.0
D81743
147
948708
Opt
948725.8
2.3
D82043m
154
1003444
Opt
Opt
0.4
D82043
168
1079720
Opt
1079721.6
3.5
D102643
168
1121130
Opt
Opt
0.1
D122643
186
1218825
Opt
Opt
0.1
D122943m
210
1365993
Opt
Opt
0.1
D122943
240
1526097
Opt
Opt
0.5
D4944
120
758785
Opt
758785.2
0.4
D61444
152
964730
Opt
964731.6
1.4
D61644
153
984935
Opt
984947.6
2.0
D81744
154
995860
Opt
Opt
0.3
D102244m
194
1245433
Opt
1245435.7
3.3
D82044
168
1091866
Opt
1091866.2
1.0
D122644m
198
1295659
Opt
1295659.1
0.5
D122944m
210
1380447
Opt
1380451.7
4.3
D122944
224
1456564
Opt
1456573.6
3.4
D102644
214
1379555
Opt
1379559.6
5.0
D143044m
219
1438672
Opt
1438693.5
5.8
D143044
245
1578725
Opt
1578737.9
4.3
D143344
236
1549308
Opt
1549327.0
5.5
D163744m
254
1671485
Opt
1671489.7
7.5
D163744
278
1801619
Opt
1801629.8
8.9