Hiking through Austria

The Austrian hike starts out at the University of Vienna, site of the OR2015 meeting, and passes by 100 of Austria's highest mountains. The point-to-point travel times were provided by Google Maps, setting the travel mode to walking. The total time for the hike is a little over 27 days.

100 Austrian Mountains. Click for a larger image. For an interactive version Click Here.

Note: Google Maps leaves it up to hikers to make the selection of the final climb to each of the moutain peaks. I've indicated these portions of the tour with dotted lines.

The hike has lots of climbing! This led to two changes, compared with the USA College and Extra Miler road trips we computed. First, we optimized the route for walking time, rather than walking or driving distance. Second, it is no longer reasonable to assume that traveling from point A to point B takes the same amount of time as traveling from B back to A. We therefore modeled the tour as an asymmetric traveling salesman problem, where travel direction matters.

To solve the 101-city asymmetric TSP, we used a standard trick to convert the problem to the symmetric form that can be handled by the Concorde solver. This involves splitting each city into two copies, one for incoming roads and one for outgoing roads. The two copies are connected by an edge that is required to be in the tour. Concorde handled the 101-city Austrian problem in under a second on a Mac Mini, but a more specialized approach would likely be needed if we had a larger ATSP example of 1,000 or so cities.

Terrain drawing. Click for a larger image. For an interactive version Click Here.

Road-map drawing. Click for a larger image. For an interactive version Click Here.

Itinerary

Here is the list of stops on the hike, given in the tour order.

Data

The optimal Austrian tour, computed by Concorde, has total time 2,352,950 seconds. As I mentioned, it was necessary to convert the asymmetric problem to a symmetric one before I could use the Concorde solver. If you have a large example of the ATSP and you would prefer a direct solution method, Keld Helsgaun's LKH code accepts ATSP input. His code implements a heuristic method, rather than an exact solver, but it usually provides very good solutions. Indeed, on the Austrian problem it delivered the optimal tour, albeit without a guarantee of optimality.

If you would like to try out your own TSP methods, here is the matrix of point to point travel times, measured in seconds.

Credits

The Austrian mountains to visit were selected from the Wikipedia page List of highest mountains of Austria. The point-to-point walking times were obtained with Google Maps.