Slice of StarHorse Tour

265,637,087 Stars


A teaser poster provides quick answers to "How many stars will be in the second Gaia data release?" The central figure, from the TSP perspective, is 1,331,909,727. That's the amazing count of Gaia DR2 stars that come equipped with parallax data. With some fancy math and statistics, Bailer-Jones et al. used this parallax information to infer distances out to nearly all of them. Their data set is the source of our Gaia DR2 TSP instance.

In the abstract to their research paper, Bailer-Jones et al. write the following.

"Although more precise distances can be estimated for a subset of the stars using additional data (such as photometry), our goal is to provide purely geometric distance estimates ..."

This nicely sets up the work of the StarHorse 2019 team of F. Anders et al. Their project did just as Bailer-Jones et al. suggest, using several photometric catalogues, together with the Gaia DR2 parallaxes, to produce 3-dimensional position data for 265,637,087 of the Gaia DR2 stars. Brilliant. Gives another great challenge for TSP solvers.

You can find details of the StarHorse point set on the data page.

As you can guess, we have a tour. And we think it's a good one. But we are not yet certain. The heuristic-search algorithm we are employing continues to find shortcuts every day, gradually decreasing the total length. As of October 6, 2020, that length is 3,687,479,103.2 parsecs. You can be confident this is not a best-possible result. But how close is it to optimal?

What's missing, thus far, is a lower bound on the tour length. We have created a (very large) linear-programming model to produce such a bound, but we are still working on the computational methods for handling LP instances of this size. Hopefully in another month or so we will have first results.

Research team

  • David Applegate, Google Research
  • William Cook, University of Waterloo and Johns Hopkins University
  • Keld Helsgaun, Roskilde University


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; images can be found on the Tour page.

Computations were carried out on systems located at Google Research, Roskilde University, and the University of Waterloo. We thank our institutions for their support.