Milestones in the Solution of TSP Instances

Computer codes for the TSP have become increasingly more sophisticated over the years.  A conspicuous sign of these improvements is the increasing size of nontrivial instances that have been solved, moving from Dantzig, Fulkerson, and Johnson's solution of a 49-city problem in 1954 up through the solution of a 85,900-point problem 52 years later.

Year	Research Team	Size of Instance	Name
1954	G. Dantzig, R. Fulkerson, and S. Johnson	49 cities	dantzig42
1971	M. Held and R.M. Karp	64 cities	64 random points
1975	P.M. Camerini, L. Fratta, and F. Maffioli	67 cities	67 random points
1977	M. Grötschel	120 cities	gr120
1980	H. Crowder and M.W. Padberg	318 cities	lin318
1987	M. Padberg and G. Rinaldi	532 cities	att532
1987	M. Grötschel and O. Holland	666 cities	gr666
1987	M. Padberg and G. Rinaldi	2,392 cities	pr2392
1994	D. Applegate, R. Bixby, V. Chvátal, and W. Cook	7,397 cities	pla7397
1998	D. Applegate, R. Bixby, V. Chvátal, and W. Cook	13,509 cities	usa13509
2001	D. Applegate, R. Bixby, V. Chvátal, and W. Cook	15,112 cities	d15112
2004	D. Applegate, R. Bixby, V. Chvátal, W. Cook, and K. Helsgaun	24,978 cities	sw24798
2006	D. Applegate, R. Bixby, V. Chvátal, W. Cook, Daniel Espinoza, Marcos Goycoolea, and K. Helsgaun	85,900 cities	pla85900