Recent Updates to the TSP Challenge Website

November 19, 2013

Official site moves to Site at is deactivated.

July 29, 2011

Corrected the lengths for the tours constructed by the Benchmark Greedy code on the four CEIL_2D instances in our test set (dsj1000, pla7397, pla33810, and pla85900). The code that generated these was a variant on the Benchmark version, and had an error when handling the ceiling metric. Thanks to "raoweizhen" for spotting this error.

December 11, 2008

Added optimal tour lengths for instances brd14051, d18512, pla33810, and pla85900, as computed in recent years by Bill Cook and collaborators - see and The Traveling Salesman Problem: A Computational Study, D.L. Applegate, R.E. Bixby, B. Chvatal, and W.J. Cook, Princeton University Press, Princeton, NJ, 2006. A citation to the latter book has also been added to the "About the Challenge" page.

November 26, 2008

Corrected Held-Karp Lower bound for E316k.0.

The previous value, 398582616.458995, was incorrect. Computations using Concorde on two separate machines confirms that the true value is roughly 398760104.63771. Thanks to Peter Merz for catching this error.

Also, the arrival date for the long awaited DIMACS Tech Report has now been postponed until Summer 2009. Added contributions still welcome.

November 16, 2004

Updated Fred Glover's affiliation.

It looks as if the long-awaited DIMACS Tech Report will now not appear until 2005, but we plan to get it done sometime in the first half of the year.

January 31, 2003

Corrected optimal value for dsj1000. The old entry was the optimal value under the ``rounded-to-nearest'' Euclidean metric, but the instance's prescribed metric is the ceiling metric. Thanks to Moshe Looks for catching this error.

August 22, 2002

Added new results for the Lin-Kernighan variants of Nguyen-Yosihara-Yamamori-Yasunaga and of David Neto. The latter help to better illustrate the effects of Neto's ``cluster compensation'' technique. Also corrected entries for the 10-neighbor Johnson-McGeoch Lin-Kernighan implementation, where the runs on random instances had mistakenly been performed with a depth bound of 50 rather than infinity.

Redesigned the Results page to make the presentations more uniform and to include the abberviations used in the Comparisons pages to name the various algorithms/implementations. Visitors to the website can now use their browser's FIND command on the Results page to jump to the section covering the corresponding algorithm/implementation.

Extended the deadline for the DIMACS Tech Report to 1 September 2002, although the job of putting the report together has finally begun and so this may be the last extension.

August 16, 2002

Updated URL's for the Cook et al. Traveling Salesman Page and Bill Cook's homepage . Please inform of any other outdated or inoperable links.

June 19, 2002

Added an Instance Comparison page, whereby one can see how all the implementations rank as to tour quality on a selected instance.

June 11, 2002

Added package for generating charts and comparisons using your own data, accessible through both the main and download pages (tarfile).

Updated Comparison and Results Pages so that data file names use the same abbreviations as were used in the TSP book chapter. (The book has now been published.) Added results for Walshaw's Multi-Level Helsgaun variant and Nguyen-Yoshihara-Yamamori-Yasunaga implementations of LK and ILK variants. Corrected typos in this page.

Fixed bug in instance generation code that on rare occasions could yield an incorrect "length" result for instance with the rounded-up Euclidean metric. (Thanks to Chris Walshaw for pointing out the error.)

Fixed bug in cgi-script that computed summary tables -- for TSPLIB instances it was only reporting the result for one of the listed instances. (Thanks to Nguyen Dinh Hung for pointing out the error.)

November 27, 2001

Replaced the drafts of STSP and ATSP chapters with new near-final versions that correct several typos and imprecisions.

Extended the deadline for the results if they are to be included in the DIMACS Tech Report until 28 February 2002.

October 1, 2001

Replaced the draft STSP chapter with a new version that corrects an error in the references (on page 77).

September 10, 2001

Replaced the draft STSP chapter with the "final" version.

August 28, 2001

Replaced the draft ATSP chapter with a "final" version that corrects typos and clarifies some of the writing.

August 6, 2001

Added a links to the postscript (80 pages) for a draft of the TSP book chapter summarizing the results of this Challenge as of 1 July 2001. Updated the about page to reflect a new planned deadline of 30 November 2001 for the multi-authored DIMACS Tech Report on the Challenge.

The chapter refers to a not-yet (but soon-to-be) implemented feature of the comparison page whereby one will be able to specify an instance and obtain a sorted summary of the results for all the heuristics in the Challenge on that instance. This will involve renaming many files to correspond to the new heuristic abbreviations specified in the chapter draft but should be implemented by the end of August.

July 25, 2001

Added a link on the ATSP page to the postscript for a draft chapter (45 pages) on experimental analysis of heuristics for the ATSP, to appear in the book The Traveling Salesman Problem and its Variations , G. Gutin and A. Punnen, editors, Kluwer Academic Publishers. A draft of a companion chapter on the symmetric TSP, summarizing results from the DIMACS Implementation Challenge on the TSP, should be posted in the next week or so, along with other updates to the Challenge website.

June 19, 2001

Replaced results for approximate Christofides with HK one-trees by ones for true Christofides using HK one-trees, true minimum matchings, and greedy shortcuts (Rohe). Also added results for Rohe's LK implementation using the above as starting tours.

June 17, 2001

Added ATSP page from which instances and instance generators for the Asymmetric TSP can be downloaded.

Added results for the best of ten runs of chained and iterated Lin-Kernighan, best of five tour merges, and for 10N-iteration Iterated Lin-Kernighan. Added results for Concorde's versions of 2-, 2.5-, and 3-Opt.

June 4, 2001

Fixed a bug present in some of our normalization codes that could cause mis-estimates of 50% on selected TSPLIB instances.

Added results for "Best of multiple runs" for Chained LK, Iterated LK, and tourmerging, and 10N-iteration runs of the latter. Also Added results for Nearest, Random, and Farthest Addition to the results for the previously included "augmented addition" algorithms. Added results for C316k.0 to results for the Applegate-Cook-Rohe codes.

May 17, 2001

Added runs of Jon Bentley's implementations of 2-Opt, 2.5-Opt, and 3-Opt, as well as runs of the Johnson-McGeoch implementations of 2-Opt, 3-Opt, and Lin-Kernighan on the MIPS processor for comparison purposes. Added additional text and pointers to help explain some of the algorithms on the results page.

Fixed a bug in the summary table generating script that underestimated the tour quality for the 10,000-city Random Distance Matrix instance. Revised results for the J-M implementations of 2-Opt etc. to fix a bug that inflated running times for fractional-coordinate TSPLIB instances.

May 9, 2001

Added additional running time normalization factor options on comparison page. Changed "Clarke-Wright" to "Clarke-Wright Savings Heuristic" to be more in line with the literature on that algorithm. Removed spurious data for Random Distance Matrix instances on several implementations (The only Concorde tour construction heuristic that actually handles these is Nearest Neighbor).

May 2, 2001

Added results for Concorde's Lin-Kernighan implementation, an augmented version of Lin-Kernighan by Harald Buesching, and Johnson-McGeoch's implementations of 2-Opt, 3-Opt, and Lin-Kernighan with 10 and 20 quadrant neighbors. (Previously results were only available for 40 quadrant neighbors.)

Made other minor corrections.

April 29, 2001

Added an algorithm that merely reads the instance to the second column of options on the Comparisons page. With this, one can determine what proportion of a heuristic's total time is spent on instance-reading. This was run on a 196 Mhz MIPS processor, and so yields the most accurate comparisons for heuristic results on the same processor. Charts and table for comparisons involving the "Reading algorithm" do not include Tour Quality comparisons.

Augmented the heuristic menus on the Comparison page to include all the heuristic runs covered on the Results page. From now on these two should be in sync. Added a few more references/algorithm explanations to the Results page.

April 26, 2001

Changed the format of the summary tables to increase clarity, and changed the TSPLIB entries in those tables to be averages over sets of instances, as specified on the generated page.

Rearranged the Results page to better mirror the algorithm grouping for the TSPbook Chapter on the Challenge, and linked in a description of the Stem-and-Cycle Ejection Chain algorithm.

April 25, 2001

Added a Comparison page so that visitors can compare the results for various algorithms based on online-generated charts and tables. Thanks to David Applegate for help with the online generation of charts, and to John Denker for general help with CGI-scripts.

Added results for the Applegate-Cook-Rohe implementation of N-iteration Chained Lin-Kernighan, for a stem-and-cycle ejection chain variant on LK due to Rego, Glover, and Gamboa, and for an implementation of Boruvka's algorithm due to the latter group.

March 30, 2001

Added results for the multi-trial version of Helsgaun's LKH variant on Lin-Kernighan.

Corrected bug in cgi-script for summary table that led to underestimates of average running times for random distance matrix instances. Also, modified this and the cgi-script for normalized data so that if the instance size exceeds the maximum size for which the benchmark was run on the given machine, the time is normalized based on the largest instance size for which the benchmark code WAS run.

March 28, 2001

Added results for Concorde's implementation of chained Lin-Kernighan as computed on two different machines.

Added results for Balas and Simonetti's dynamic programming based tour improvement heuristic, along with a text file of Simonetti's description of the algorithm and analysis of its results (more of these short descriptions from participants will be added in soon - if you haven't sent me one for your submission, please do so).

Added results for additional tour construction heuristics, including the GENI and GENIUS algorithms of Gendreau, Hertz, and Laporte (as modified by David Johnson for improved speed and memory usage without affecting solutions quality).

Added results for C316k.0 for several of the Johnson-McGeoch local optimization implementations.

Noted of home page that results are still being accepted for the DIMACS tech report, since it will be sometime yet before the editors have time to put it together.

Added an additional reason why normalized running times might be inaccurate to the discussion in norm.html

March 9, 2001

Introduced a cgi-script to automatically generate the normalized datafiles (previously simply referred to as html tables). Also added a cgi-script to automatically generate a summary table for each algorithm, so that results for similarly sized instances from each class can be more readily compared.

Added results for a variety of additional tour construction heuristics implemented by Bentley, Johnson, and McGeoch.

January 26, 2001
Added results from

Modified homepage and ``About'' page to reflect the fact that the initial deadline has now passed, but that submissions were still welcome (indefinitely) and that a new section devoted to the asymmetric TSP should be opened shortly.

October 30, 2000
Replaced homepage (index.html) with a simpler page including some graphics and pointers to the other pages. Former homepage is now about.html.

Extended the deadline for inclusion in the initial technical report until November 30, 2000.

September 5, 2000
Added Held-Karp bound for the new benchmark instances C316k.0 (and the time for computing it) to relevant tables.

Added .pdf version of the viewgraphs for David Johnson's talk about the Challenge at the 2000 International Symposium on Mathematical Programming. Link is on the bottom of the Challenge homepage (and here).

August 28, 2000
Added a 316,228-city random clustered instance to the test suite, which can be generated by the command

portcgen 316228 316228 > C316k.0

If correctly generated, the instance should consist of 6459637 bytes. We will shortly add results for this instance to the data for Johnson-McGeoch codes that can handle instances this large. Participants who have already submitted data and want to include this instance as well can send results for the instance alone if run on the same machine as your other results, and we will add them to your data files.

August 21, 2000
Put link at the bottom of the homepage (and here) to the postscript for the viewgraphs for David Johnson's talk about the Challenge at the 2000 International Symposium on Mathematical Programming in Atlanta (August 7-11). There are 29 viewgraphs in the file, including displays of some of the random instances in the testbed and some early attempts at graphical comparisons of algorithms. Some of these will soon appear in gif form in the relevant results sections.

August 4, 2000
Replaced table illustrating imprecision of normalization process with a more direct one containing data for Lin-Kernighan as well as the Benchmark Greedy code.

August 2, 2000
Moved Machine Comparisons and Algorithm Results to a new ``Results'' page and changed other pages to reflect this. Reformatted the Download page adding some extra explanatory remarks.

Resorted the machine speed table according to speed on small instances.

Reformatted results tables to give excess over optimal (where known) as well as excess of the Held-Karp bound, and to include a normalized running time (obtained by dividing by the benchmark greedy time for the machine used). Added a table illustrating the imprecision of the normalization process.

Added results for Applegate-Cook-Rohe Lin-Kernighan and Chained Lin-Kernighan, for Johnson-McGeoch Iterated Lin-Kernighan, and for Rohe's Lagrangean relaxation code for approximating the Held-Karp bound.

Added results for the Clarke-Wright tour construction algorithm and ran the benchmark greedy code on the full suite of testbed instances using a second machine, so as to provide an additional perspective on the accuracy of running time normalization.

July 24, 2000
Added IBM 595 to machine table, updated results for Concorde.

June 15, 2000
Added optimal tour length for the final 3162-city random Euclidean instance.

June 8, 2000
Updated tar and zip files for benchmark codes to correct problems pointed out by David Applegate. Two of the included files have been changed:

  1. Replaced the generator portcgen.c for generating clustered geometric instances with a more robust version. This should work on more machines (and generates the same instances as before).
  2. Expanded the README file to correct the omission of generating instructions for the two largest test instances.

June 1, 2000
Officially announced the Challenge

Challenge Homepage

About the Challenge

Download Page

Results Page

Comparison Page