Frans de Ruiter set to bike the Dutch tour. Click.
Enthusiastic cyclists and country-wide bike paths.
The Dutch certainly know how to ride.
So we jumped at the chance to work with Frans de Ruiter and the Dutch firm CQM on the computation of a nationwide cycling tour, visiting every Dutch national monument.
A total of 57,912 stops in a shortest-possible route.
This is the third in a sequence of large-scale traveling salesman problems we have solved where distances are provided by mapping software.
The previous two, a US history tour (November 2016) and a UK pub crawl (March 2018), used walking distances, obtained with the Google Maps API.
For the Dutch tour, CQM computed for us a table of all 1,676,870,916 point-to-point biking distances between pairs of monuments.
The paths they found are all legal for cycling (in many cases stopping just short of the monuments, but always giving a nice view).
Our traveling salesman problem (TSP) solution puts the point-to-point paths together to produce a round-trip tour of length 20,253,062 meters.
This is not just a good tour, we have proven that it's shortest possible, when distances are defined by the CQM table.
It is an optimal TSP solution.
To get a good look at the tour, head over to the Tour page for interactive maps, letting you zoom in to see details.
On the Data page you can download a file with the locations of the 57,912 monuments and on the Paths page you can see a discussion of the work CQM carried out to build the very large distance table.
For a few words on the (rather long) computation to solve nl57912, please see the Computation page.
How do we know the tour is shortest possible?
As in the computations to solve the US (49,603 stops) and UK (49,687 stops) instances, we clearly did not check every tour, one by one.
For nl59712, this would have meant examining roughly 4 followed by 250,668 zeroes different tours.
This huge number of possible solutions is frightening, but it doesn't mean we can't solve this large example of the TSP.
Our attack combined the LKH code for computing extremely good TSP solutions and the Concorde code for producing quality guarantees.
You can see a short discussion of how we apply these tools on the UK Pubs page.
Or, if you have a few minutes, you can check out the video of the talk Optimal Tours given at the National Museum of Mathematics (August 2021), where the method is described in detail.
The Big Picture
We use large examples of the traveling salesman problem as a means for developing and testing general-purpose optimization methods.
The world has limited resources and the aim of the applied mathematics fields of mathematical optimization and operations research is to create tools to help us to use these resources as efficiently as possible.