3D Star TSPs

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.

References

The TSP point sets are based on David Nash's HYG Database and on Gaia distance estimates reported in the following three research papers.

TSP 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

Information on the TSP solution techniques we have employed can be found on the TSP home page and on the LKH web site.

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.

All tour images were rendered with the three.js JavaScript 3D library.

We thank Michael Boyle for suggesting the use of color hue to indicate the order stars appear in our solutions.