Using 3D astronomical data, we have created 12 instances of the TSP, ranging in size from 100 points up to 1.33 billion points. In these examples, star to star travel is measured by straight-line Euclidean distances in three-dimensional space, rounded to the nearest 1/10th parsec. (Why 3D?)
The tours we report come together with quality guarantees. For example, our tour through 2,079,471 stars, if not the absolute shortest possible, is off by at most a factor of 0.0000074. That is, we have a tour of length 28,884,352.4 parsecs and we know it's impossible to visit the stars in less than 28,884,139.0, a gap of only 213.4 parsecs.
Current results for the test instances are reported in the following table.
|# of Stars||Source||Quality|
|1,000||DR1 + HYG||Optimal|
|10,000||DR1 + HYG||Optimal|
|250,000||DR1 + HYG||0.0000043|
|2,079,471||DR1 + HYG||0.0000074|
• 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
We thank Bob Vanderbei for pointing us to the HYG database. This was the start of our work on 3D star tours.
Computations were carried out on systems located at Roskilde University and at the University of Waterloo.
We thank Michael Boyle for suggesting the use of color hue to indicate the order stars appear in our solutions.