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.
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.
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).
.
