8th DIMACS Implementation Challenge:

The Traveling Salesman Problem

Challenge News: Still Open for Business!

(Including New Do-It-Yourself Feature)

The original deadline for submitting results to TSP Challenge has passed, and the Johnson-McGeoch chapter that summarizes the Challenge results (as of 1 July 2001), ``Experimental analysis of heuristics for the STSP,'' has now been published in The Traveling Salesman Problem and Its Variations, G. Gutin and A. P. Punnen (Editors), Kluwer Academic Publishers, 2002, Boston, 369-443. A near-final draft, differing from the published version only in pagination and the correction of a few typographical errors, can be downloaded: (80 pages postscript) (PDF). The deadline has also passed for the DIMACS technical report that will cover all the Challenge submissions and describe this website in detail. However, this report has not yet been completed, so there may still be time for late results to be included (new deadline: 1 June 2009).

Even after the report is written we will continue to welcome submissions, and will periodically add them to the Results Page below. We hope to maintain this site indefinitely so that future TSP researchers will have a ready set of benchmarks to which they can compare their results. Moreover, software is now available (tarfile)(zipfile) so that users of UNIX/LINUX systems can generate figures and comparison charts for their data in our standard formats (gif and postscript) before they submit it to the site. Also included is code that will generate normalized results like those on our Results page, and this code should work on most platforms.

For those interested in the Asymmetric TSP, see below for a page devoted to that topic.

About the Challenge

Download Page

Results Page

Comparison Pages:   Algorithms   Instances

How do the algorithms/implementations covered in the Challenge compare to each other with respect to tour quality and running time? These pages let you generate comparison charts and tables online. The "Algorithms" page lets you see (in graphical or tabular form) how two selected algorithms compare over the whole instance testbed. It also lets you examine the detailed results for a single algorithm and attempt to estimate how its running time grows as a function of N. The "Instances" page lets you see how all the algorithms rank (with respect to tour quality) for any selected instance.

Asymmetric TSP Page

Download the random instances generators and real-world instances (from TSPLIB and elsewhere) covered in the papers ``The asymmetric traveling salesman problem: Algorithms, instance generators, and tests'' by Cirasella, Johnson, McGeoch, and Zhang, in Algorithm Engineering and Experimentation, Third International Workshop, ALENEX 2001, Lecture Notes in Computer Science, Vol. 2153, Springer, Berlin, 2001, 32-59 (28 pages postscript) (PDF), and ``Experimental analysis of heuristics for the ATSP'' by Johnson, Gutin, McGeoch, Yeo, Zhang, and Zverovitch, in The Traveling Salesman Problem and Its Variations, Kluwer Academic Publishers, Boston, 2002, 445-487 (45 pages postscript, near-final draft) (PDF). .

History of Updates to this Website (Latest Update: 19 November 2013)