---

Backbone based TSP Heuristics for Large Instances: Addendum

authored by Changxing Dong, Boris Goldengorin, Gerold Jäger, Dirk Richter, and Paul Molitor, all with University of Halle.

Source code of the improved LKH version

Tolerances in Helsgaun's Lin-Kernighan-heuristic for the TSP
tolerances_in_LKH.zip (115,4 KB)  vom 11.06.2009

Starting tours used during the experiments for pseudo backbone contraction

For computing the starting tours of the experiments for pseudo backbone contraction (see Section 6 of the paper) the different versions of LKH-1.3 described in Section 3.4 of the paper have been used.

Mostly, we used the default parameter values of LKH (see below the section on search parameters), whereas we varied only the parameters r, s, and t mentioned in the paper.

To collect the starting tours, we could not afford strong parameter values because of large running times. Therefore the search for the starting tours was associated with relative weak parameter values (and the search for the reduced instances with stronger ones). The standard values of r, s, and t are r=5, s=5, and t=10.

Starting tours bgb4355 - boa28924
startingtours_bgb4355_boa28924.zip (5,6 MB)  vom 24.06.2008

Starting tours brd14051 - dsj1000
startingtours_brd14051_dsj1000.zip (2,7 MB)  vom 24.06.2008

Starting tours ei8246 - fma21553
startingtours_ei8246_fma21553.zip (6,1 MB)  vom 24.06.2008

Starting tours fna52057 - fry33203
startingtours_fna52057_fry33203.zip (4,3 MB)  vom 24.06.2008

Starting tours ics39603 - ida8197
startingtours_ics39603_ida8197.zip (5,3 MB)  vom 24.06.2008

Starting tours ido21215 - kz9976
startingtours_ido21215_kz9976.zip (6,5 MB)  vom 24.06.2008

Starting tours lap7454 - pcb3038
startingtours_lap7454_pcb3038.zip (2,4 MB)  vom 24.06.2008

Starting tours pia3056 - xia16928
startingtours_pia3056_xia16928.zip (7,1 MB)  vom 24.06.2008

Starting tours xib32892 - xqe3891
startingtours_xib32892_xqe3891.zip (6,5 MB)  vom 24.06.2008

Starting tours xrb14233 - xrh24104
startingtours_xrb14233_xrh24104.zip (3,8 MB)  vom 24.06.2008

Starting tours xsc6880 - ym7663
startingtours_xsc6880_ym7663.zip (5,3 MB)  vom 24.06.2008

---

Search Parameters

Most of the search parameters are default values to the program. We have used two sets of parameters: that for small instances and that for large instances.

Search parameters applied in our experimental runs
param.tar (60 KB)  vom 23.06.2008

---

Information about the Record Tours

Zum Seitenanfang