The nl57912 TSP instance was constructed by Frans de Ruiter and a team at the Dutch firm CQM. It consists of biking distances, measuerd in meters, between 57,912 national monuments in the Netherlands. The distances are symmetric, that is, for any pair of monuments A and B, the distance from A to B is the same as the distance from B back to A.
The first step in building an example of the TSP is to collect the locations of the points to visit. Fortunately, the monument register page of the Dutch National Office for Cultural Heritage has a long list waiting for us, giving a total of 63,287 Rijksmonumenten. These locations are nicely displayed on the maps of the
• Kaart met Rijksmonumenten in Nederland
web page, together with photos and information on the monuments. The monuments are typically interesting older houses and buildings, rather than statues. (If you are in the Netherlands in mid-September, be sure to check out the Open Monumentendag events.)
Well, you no doubt noticed that 63,287 does not equal 57,912. This reduction came in the second step, when the CQM team discovered that roughly 5,000 of the monuments are listed with the exact latitude and longitude of another monument in the data base. There are a further several hundred listed monuments where the latitude and longitude coordinates are not available. This gets us down to 57,912 locations given in the following file
• nl57912.xy (latitude-longitude coordinates).
and these are the points we would like to visit.
The latitude-longitude coordinates are sufficient to define a geometric instance of the TSP, but there are plenty of examples of that type, including all of the large TSPLIB instances.
The goal here is to work with map-defined distances, testing the limits of TSP-solution techniques on non-geometric data sets. To this end, CQM offered to compute biking distances, making use of the extensive Dutch network of legal bike paths. That's great, but it creates a first difficulty: some monuments are not reachable by bike. Concerning this, Frans de Ruiter made the following notes.
• There are 986 locations that are 200 meters or more from the map.
• There are 20 points that are one kilometer or more from the map.
• The furthest one is 7,154 meters from the map: a former lighthouse on an island nature reserve.
We don't expect cyclists to swim out to lighthouses, so the CQM team projected the monument locations onto the nearest point of the bike map. This will typically get you a close view of the monument, but you might need to carry a small monocular if you want to see from 7,154 meters the Emder kapp in Rottumeroog.
The task now is to find a shortest path between each pair of the bike-map-projected monument locations. Now, unlike in the case of the TSP, there are very efficient ways to find a shortest path from point A to point B along a map network. The challenge in creating nl57912 is the huge number of such pairs A and B that need to be handled.
To finish the job, CQM employed their in-house shortest-path software. The Paths page and the two news articles
• Allergrootste handelsreizigersprobleem óóit opgelost
• The shortest route from A to B via lots of stop-offs can be done in Brabant
describe their work in computing the point-to-point paths, building the 1,676,870,916 entries of the distance table in a remarkably short two-hour computation.
The full data set, in TSPLIB format, is a 10.2 GByte file. This is too large to store on our university server. But if you would like to carry out experiments on nl57912, please write to bico@uwaterloo.ca and I'll place the file temporarily at a public location.
Click on the images to see high-resolution snapshots.
