When we first discussed star trips as potential 3D TSP challenges, Bob Vanderbei (coauthor of the great book Sizing up the Universe) immediately suggested the HYG Database, combining the Hipparcos, Yale Bright Star and Gliese catalogues.
A great thing about HYG is that it includes explicit xyz coordinates, placing each star in 3-dimensional space. The moving image to the right shows an optimal tour through all 119,614 of these star locations, where point-to-point travel is measured by straight-line 3D Euclidean distance, rounded to the nearest 1/10th parsec.
This is the largest instance of the TSP that we have solved to precise optimality, but its structure really splits the data set into two problems, one consisting of an outer rim of 10,215 points and another consisting of the remaining 109,399 points in an inner core.
The outer rim points lie on a sphere of radius 100,000 parsecs, centered at Earth. These correspond to stars whose position in the sky is known, but their distance from Earth is not part of the HYG database. Therefore, we also created a TSP instance, hyg109399, containing points for only the core stars, having more accurate placement information.
• David Applegate, Google Research
• Robert Bixby, Gurobi Optimization and Rice University
• Vaek 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
For a guide to navigating the moving image, click the ⓘ button in the top right corner of the page.
The computations were carried out on systems located at Roskilde and Waterloo. We thank our universities for their support.
We thank Bob Vanderbei for pointing us to the HYG database and Michael Boyle for suggesting the use of color hue to indicate the order stars appear in our solution.