There's always a bigger TSP. That's a great thing about computational work on the traveling salesman problem. No matter what you do, larger or more difficult challenges await, ready to serve as an engine of discovery.
ESA Gaia
For example, the European Space Agency (ESA) definitely has our TSP backs. The goal of their Gaia mission "is to make the largest, most precise three-dimensional map of our Galaxy." The first two data releases, Gaia DR1 and Gaia DR2, have already provided a treasure trove of astronomical information. Among many other accomplishments, research teams have used DR1 to construct a data set giving approximate 3D positions of over 2 million stars, and DR2 to build data sets for both 265 million stars and 1.33 billion stars. Now we're talking.
TSP in 3D
We used the Gaia sets, and the HYG Database, to create a series of 3-dimensional TSP challenges. The problems include the largest TSP test sets ever to be studied.
Check the about page for an overview, or click on the images (to the right) to take you to the individual problems and current results, including interactive displays of the 3D tours.
Research team
• David Applegate, Google Research
• Robert Bixby, Gurobi Optimization and Rice University
• Vašek Chvátal, Charles University
• William Cook, University of Waterloo and Johns Hopkins University
• Daniel Espinoza, Google Inc.
• Marcos Goycoolea, Universidad Adolfo Ibanez
• Keld Helsgaun, Roskilde University
