Previous: AIDA-99-05 Index 2000

Intellectics Group: Technical Report 00-01

A Comparison of Nature Inspired Heuristics on the Traveling Salesman Problem

Thomas Stützle and Andreas Grün and Sebastian Linke and Marco Rüttger

Submitted to PPSN-VI

The Traveling Salesman Problem is a standard test-bed for algorithmic ideas. Currently, there exist a large number of nature-inspired algorithms to the TSP and for some of these approaches very good performance is reported. In particular, the best performing approaches combine solution modification or construction with the subsequent application of a fast but powerful local search algorithm. Yet, comparisons between these algorithms with respect to their performance are often difficult due to different implementation choices of which the choice of the local search algorithm is particularly critical. In this article we experimentally compare some of the best performing recently proposed nature-inspired algorithms which improve solutions by using a same local search algorithm and investigate their performance on a large set of benchmark instances.

Full Paper: Gzipped postscript BibTeX entry