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.

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.

For general information on mathematical modeling and its impact on industry, commerce, medicine, and the environment, we point you to a number of societies that support mathematics research and education: American Mathematical Society, Mathematical Association of America, Mathematical Optimization Society, INFORMS (operations research), and SIAM (applied mathematics).

William Cook, Combinatorics and Optimization, University of Waterloo, Canada
Daniel Espinoza, Google, Research and Development, USA
Marcos Goycoolea, School of Business, Universidad Adolfo Ibanez, Chile
Keld Helsgaun, Computer Science, Roskilde University, Denmark

The table of point-to-point cycling distances was computed at CQM by the following researchers.
Frans de Ruiter, CQM, Netherlands
Carien Leushuis, CQM, Netherlands
Matthijs Tijink, CQM, Netherlands
Bart Verberne, CQM, Netherlands

The raw cyclying-map data for the Netherlands was provided by Geodan.

Kaart met Rijksmonumenten in Nederland shows the locations of more than 63,000 national monuments and provides links to government data sets.

The huge number of linear-programming models that arose in the computation were solved with the IBM CPLEX Optimizer. Many thanks to IBM for making their great software freely available for academic research.

The map drawings of the tour were created by the CQM team, making use of the Leaflet open-source JavaScript library for mobile-friendly interactive maps.