We also computed optimal walking tours to see 383 Korean mountains and to visit the 2141 bars in Daejeon. These two smaller instances were created for a TSP talk given at KAIST.
Using the PeakVisor web site, we obtained a list of the 383 Korean mountain peaks measuring over 500 meters. The peak-to-peak walking times were again obtained with the OSRM routing software. The total hiking time for our optimal tour is measured as 5,434,221 seconds (about 65 days). The problem was solved in 0.88 seconds on an M1 Mac Studio.
You can view an interactive map of the mountain tour by clicking on the image below. In the map you will find a menu in the top left-corner with buttons to zoom into regions of Korea. The top right-corner of the map contains a small menu for modifying the drawing, and the bottom right-corner has buttons for zooming in or out. Clicking on a location marker will display a menu to allow you to zoom into the mountain peak or to pan to the neighboring stops in the tour.
Clicking on the left-side image below gives a high-resolution view of a beautifully rugged a segment of the peak-to-peak tour. The right-side image shows the same segment in the Grayscale-map view.
We had originally planed to make the mountain-peak challenge an example of the asymmetric TSP (ATSP), where the time to hike from peak A to peak B may not be the same as the time to walk from B back to A. But the OSRM router does not make an uphill/downhill distinction when computing travel times. For example, hiking from the coast up the trail to the 1947-meter peak of Hallasan on Jeju Island, the highest point in South Korea, takes the same time as walking from Hallasan to the coast.
So, with the OSRM travel times, it does not matter in which direction you hike between the peaks. For an example of the ATSP, please have a look at the driving tour to visit the Michi-no-Eki roadside stations in Japan.
The korea81998 data set contains the location of 2141 bars in the city of Daejeon. We computed an optimal tour for this Daejeon TSP in total running time 66.75 seconds on an M1 Mac Studio. The walking time for the tour is measured as 209,055 seconds (about 58 hours).
The figure below is a screen shot of an interactive map of the Daejeon tour. You can view the map by clicking on the image.
Links to data sets for the mountain peaks and Daejeon instances are given in the following table. The Lat-Lng sets give the (latitude-longitude) locations for each stop. The TSP sets give the tables of walking times in TSPLIB format. The Tour entries list the order the stops appear in the optimal tours; these files are also in TSPLIB format.
| Data Sets | Lat-Lng | TSP | Tour |
|---|---|---|---|
| Mountain Peaks | korea383.xy | korea383.tsp | korea383.tour |
| Daejeon Bars | dj2142.xy | dj2141.tsp.gz | dj2141.tour |
Point-to-point travel times and path polygons were generated with the Open Source Routing Machine (OSRM) using OpenStreetMap data.
The tour map-drawings were created with the Leaflet open-source JavaScript library for mobile-friendly interactive maps and make use of map tiles built by OpenStreetMap, by Stadia Maps, and by ArcGIS.
The drawings of the hiker, the walkers, and the Daejeon skyline are from the Daejeon Tourism page.
Locations of the Korean mountain peaks were obtained from the PeakVisor web site.
The locations of the Daejeon bars were obtained from a database maintained by the Korean National Police Agency.