The European Space Agency's Gaia Data Release 2 provides parallax and proper motion data for an amazing 1.33 billion stars. Computing how to visit them all, in a shortest-possible route, is a TSP challenge for the ages. Fortunately, a team at the Max Planck Institute for Astronomy published in an online catalogue the stars' 3-dimensional coordinates. So here we go.
The exact number we are talking about is 1,331,906,450 points to visit. Oh my. You can see details on the data page.
Our current tour for this monster weighs in at 4,961,937,077 parsecs, or about 16.2 billion light years. Several images are given on the tour page.
The NASA publication Exploring the Intersteller Medium notes that for the Milky Way galaxy "the average distance between stars is over four light-years." The star-to-star segments in our tour are 3 times longer than this estimate, so it appears we are far off base. But, via a linear-programming (LP) bound, we know no tour can have length less than 4,943,597,110 parsecs. Rather than 3 times too long, the tour is at most 1.0038 times the length of a shortest-possible route.
The 1.0038 factor is nice, but it's not nearly as strong as the quality guarantees we have for the smaller star-TSP instances. We hope to do much better in the coming months, when we will be able to deploy a new LP solver to handle, as a whole, the huge model we have created. The tour itself is likely much better than the gap indicates, and we are improving it nearly every day. The LP bound is the culprit.
Research team
• David Applegate, Google Research
• William Cook, University of Waterloo and Johns Hopkins University
• Keld Helsgaun, Roskilde University
Notes
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 University and the University of Waterloo. Support was provided by an NSERC Discovery Grant.
The tour is 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 solution.