Change search
ReferencesLink to record
Permanent link

Direct link
A backbone based TSP heuristic for large instances
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Show others and affiliations
2014 (English)In: Journal of Heuristics, ISSN 1381-1231, E-ISSN 1572-9397, Vol. 20, no 1, 107-124 p.Article in journal (Refereed) Published
Abstract [en]

We introduce a reduction technique for large instances of the traveling salesman problem (TSP). This approach is based on the observation that tours with good quality are likely to share many edges. We exploit this observation by neglecting the less important tour space defined by the shared edges, and searching the important tour subspace in more depth. More precisely, by using a basic TSP heuristic, we obtain a set of starting tours. We call the set of edges which are contained in each of these starting tours as pseudo-backbone edges. Then we compute the maximal paths consisting only of pseudo-backbone edges, and transform the TSP instance to another one with smaller size by contracting each such path to a single edge. This reduced TSP instance can be investigated more intensively, and each tour of the reduced instance can be expanded to a tour of the original instance. Combining our reduction technique with the currently leading TSP heuristic of Helsgaun, we experimentally investigate 32 difficult VLSI instances from the well-known TSP homepage. In our experimental results we set world records for seven VLSI instances, i.e., find better tours than the best tours known so far (two of these world records have since been improved upon by Keld Helsgaun and Yuichi Nagata, respectively). For the remaining instances we find tours that are equally good or only slightly worse than the world record tours.

Place, publisher, year, edition, pages
2014. Vol. 20, no 1, 107-124 p.
Keyword [en]
Traveling salesman problem, Lin-Kernighan Heuristic, Helsgaun Heuristic (LKH), Pseudo-Backbones
National Category
URN: urn:nbn:se:umu:diva-86832DOI: 10.1007/s10732-013-9233-yISI: 000330827800004OAI: diva2:705441
Available from: 2014-03-17 Created: 2014-03-11 Last updated: 2015-02-23Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Jäger, Gerold
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Journal of Heuristics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 51 hits
ReferencesLink to record
Permanent link

Direct link