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.
The full tour has length 25,307,773.4 parsecs, but the bulk of this is travel on the outer sphere. In contrast, the optimal tour for hyg109399 is a more svelte 1,375,087.4 parsecs.
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
Notes
For a guide to navigating the moving image, click the ⓘ button in the top right corner of the page.
Links to lots of information on the mathematical techniques we have employed can be found on the TSP home page and on the LKH web site.
Details on the point set for the star TSP instance are given on the Data page; further images can be found on the Tour page.
The computations were carried out on systems located at Roskilde and Waterloo. We thank our universities for their support.
The tour is rendered with the three.js JavaScript 3D library.
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.