TSP Test Data

Throughout the history of the TSP, researchers have relied on the availability of standard test instances to measure the progress of proposed solution methods. Early research papers by Dantzig, Fulkerson, and Johnson (1954), Held and Karp (1962), and Karg and Thompson (1964) included distance matrices for their main test instances, but this quickly became infeasible as the size of the studied problems grew over time. In its place, TSP researchers made their test instances available as computer-readable files stored on tape, punchcards or other media. In 1990, Gerhard Reinelt collected many of these test instances together with a wide collection of new examples drawn from industrial applications and from geographic problems featuring the locations of cities on maps. Reinelt's library is called the TSPLIB; it contains over 100 examples with sizes from 14 cities up to 85,900 cities.

To provide additional tests for the TSP, particularly for large instances, we have made available the following sets of examples (all stored in TSPLIB format).

		National TSP Collection A set of 27 problems, ranging in size from 28 cities in Western Sahara to 71,009 cities in China. Thirteen of these instances remained unsolved, providing a challenge for new TSP codes.
		VLSI TSP Collection A set of 102 problems based on VLSI data sets from the University of Bonn. The problems range in size from 131 cities up to 744,710 cities.
		The World TSP A 1,904,711-city TSP consisting of all locations in the world that are registered as populated cities or towns, as well as several research bases in Antarctica.
		Mona Lisa TSP A 100,000-city TSP that provides a continous-line drawing of the Mona Lisa. An optimal solution to this example would give a new world record in the solution of the TSP.
		United States TSP A 115,475-city TSP through (nearly) all towns, villages, and cities in the United States. $500 prize for best solution found before July 4, 2013.