Tar and Zip files containing Makefile and C programs for the Greedy benchmark algorithm and for generators of three types of random instances: uniform points in the plan, clustered points, random distance matrices. They also contain a README file that lists the commands for generating all the randomly generated instances in the testbed, and a program for verifying the length of the tour corresponding to a given permutation of the cities ( tarfile, zipfile ).

All benchmark instances are in the standard TSPLIB format as specified in the following documentation from the TSPLIB website ( postscript ). The format and metric used for each instance is specified in the instance's header in terms explained in the TSPLIB documentation. The testbed uses only the following three types: two dimensional Euclidean metric rounded to the nearest integer (EUC_2D), two dimensional Euclidean metric rounded up (CEIL_2D), and explicit distance matrix presented in upper diagonal form (UPPER_DIAG_ROW). To visit the TSPLIB website, click here.

Benchmark TSPLIB Instances ( tarfile, zipfile )
Tar and Zip files containing all instances from TSPLIB with 1000 or more cities as of 1 January 2000.

Samples of Randomly Generated Instances ( tarfile, zipfile )
Tar file containing one 1000-city instance of each type (E1k.1, C1k.1, M1k.1) from the randomly generated instance testbed. Use these to verify that the instance generator codes are working correctly.

Held-Karp Lower Bounds and Optimal Tour Lengths (where known) (text, html )
Held-Karp lower bounds for E3M.0 and E10M.0 are estimated using the formula from Johnson, McGeoch, and Rothberg, ``Asymptotic experimental analysis for the Held-Karp traveling salesman bound,'' in Proc. 7th ACM-SIAM Symp. on Discrete Algorithms, 1996, pp. 341-350 (pdf, 10 pages). The remainder were computed exactly using the Concorde program of Applegate, Bixby, Chvatal, and Cook (webpage), with the result for E1M.0 computed at Rice University on a bigger machine by Applegate et al. Exact values are included in the text file; entries in the html file are rounded to the nearest integer. Optimal tour lengths for TSPLIB instances courtesy of TSPLIB (webpage). Optimal values for the randomly generated instances were computed using Concorde. In the ``html'' summary, the ``percent excess'' is the amount by which the optimal tour length (when known) exceeds the Held-Karp lower bound.

The postscript figures included in the book chapters based on this Challenge and gifs produced by the Comparison page on this website were produced using a set of programs that have been bundled together into a downloadable package (tarfile)(zipfile). This package requires that gnuplot and ppmtogif are installed on your machine, but otherwise should be usable on most UNIX and LINUX. More details can be in this README text file (also included in the package).