Optimal Hike through Austria

August 14, 2015

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
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.

100 Austrian Mountains -- Terrain
Terrain drawing. Click for a larger image. For an interactive version Click Here.
100 Austrian Mountains
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.

Univeristy of Vienna 48.212542,16.365265
Hoher Tenn, 3368m 47.179722,12.759444
Grosser Baerenkopf, 3396m 47.130833,12.731667
Klockerin, 3425m 47.147222,12.736111
Grosses Wiesbachhorn, 3564m 47.156389,12.755278
Mittlerer Baerenkopf, 3358m 47.127222,12.713333
Kitzsteinhorn, 3203m 47.188056,12.687500
Hocheiser, 3206m 47.156389,12.673333
Keeskogel, 3291m 47.136389,12.311944
Grosser Geiger, 3360m 47.093056,12.308889
Schlieferspitze, 3290m 47.122778,12.243333
Dreiherrnspitze, 3499m 47.069167,12.240833
Reichenspitze, 3303m 47.139444,12.110833
Rossandspitze, 3157m 47.083056,11.960000
Hintere Stangenspitze, 3225m 47.057222,11.976111
Wollbachspitze, 3210m 47.050000,11.979722
Grosser Loeffler, 3379m 47.032500,11.915833
Grosser Moerchner, 3285m 47.031111,11.865556
Moerchenschneide, 3230m 47.034444,11.861111
Turnerkamp, 3420m 46.990000,11.810000
Talggenkoepfe, 3179m 47.013333,11.762500
Grosser Greiner, 3201m 47.019722,11.753889
Schrammacher, 3411m 47.026944,11.643056
Olperer, 3476m 47.053056,11.658889
Hochfeiler, 3510m 46.972222,11.727778
Grosser Moeseler, 3480m 46.992500,11.781944
Berliner Spitze, 3253m 47.002500,11.845000
Hoher Riffler, 3231m 47.081111,11.704444
Gefrorene-Wand-Spitzen, 3288m 47.064722,11.678889
Feuerstein, 3268m 46.971667,11.244444
Hohe Wand, 3289m 47.013333,11.627500
Habicht, 3277m 47.043611,11.289722
Oestliche Seespitze, 3416m 47.049167,11.151667
Wilder Freiger, 3418m 46.970278,11.190556
Luesener Fernerkogel, 3298m 47.096667,11.115000
Gleirscher Fernerkogel, 3189m 47.113889,11.063889
Strahlkogel, 3295m 47.109167,11.019444
Laengentaler Weisser Kogel, 3218m 47.070000,11.085833
Schrandele, 3393m 47.054722,11.111667
Schrankogel, 3497m 47.043889,11.099167
Gaisslehnkogel, 3216m 47.063333,11.076389
Kuehlehnkarschneid, 3195m 47.068889,11.066111
Hoher Seeblaskogel, 3235m 47.095556,11.074722
Breiter Griesskogel, 3287m 47.101111,11.022778
Innere Schwarze Schneid, 3367m 46.924167,10.921389
Aussere Schwarze Schneid, 3257m 46.937500,10.952778
Granatenkogel, 3318m 46.836944,11.072222
Schalfkogel, 3540m 46.801667,10.959167
Grosser Ramolkogel, 3550m 46.846667,10.958889
Nederkogel, 3163m 46.906944,11.009167
Stockkogel, 3278m 46.881389,10.988889
Windacher Daunkogel, 3348m 46.987500,11.081111
Murkarspitze, 3150m 47.023889,11.035833
Wilde Leck, 3359m 47.002778,11.062500
Piz Buin, 3312m 46.844167,10.118611
Silvrettahorn, 3244m 46.858056,10.092639
Augstenberg, 3228m 46.864722,10.203889
Fluchthorn, 3399m 46.890833,10.227500
Krone, 3188m 46.875556,10.231944
Hoher Riffler, 3168m 47.115833,10.370833
Watzespitze, 3533m 46.989444,10.795556
Verpeilspitze, 3425m 47.003333,10.805000
Rostizkogel, 3394m 46.968611,10.794722
Plattigkopf, 3170m 46.927500,10.675833
Hochvernagtspitze, 3535m 46.881389,10.796111
Weisseespitze, 3518m 46.846667,10.717222
Glockturm, 3355m 46.893333,10.665556
Vordere Oelgrubenspitze, 3452m 46.908333,10.773333
Bliggspitze, 3454m 46.918056,10.786111
Eiskastenspitze, 3373m 46.930278,10.791667
Loecherkogel, 3324m 46.959167,10.791389
Liebenerspitze, 3399m 46.820278,11.075556
Hochfirst, 3403m 46.826667,11.080833
Hochwilde, 3480m 46.765556,11.022222
Hinterer Seelenkogel, 3472m 46.801667,11.044444
Schwarzenstein, 3369m 47.010000,11.874167
Grosser Loefffler, 3190m 47.017500,12.164444
Fleischbachspitze, 3157m 46.958056,12.162500
Lenkstein, 3236m 46.939167,12.166944
Alplesspitze, 3149m 46.957778,12.260833
Keeseck, 3173m 46.969167,12.241111
Hochschober, 3242m 46.942500,12.698333
Hohe Achsel, 3161m 47.067222,12.426667
Hoher Eichham, 3371m 47.053611,12.406389
Zopetspitze, 3198m 47.057222,12.361667
Grossvenediger, 3666m 47.109167,12.346389
Weissspitze, 3300m 47.076111,12.392500
Kreuzspitze, 3155m 47.046667,12.359444
Roetspitze, 3496m 47.026944,12.205278
Quirl, 3251m 47.033056,12.268889
Johannisberg, 3453m 47.109444,12.672778
Grosser Muntanitz, 3232m 47.073611,12.589167
Gloedis, 3206m 46.961111,12.726111
Klammerkoepfe, 3163m 46.958889,12.762222
Petzeck, 3283m 46.948056,12.804722
Grosser Hornkopf, 3251m 46.967222,12.778889
Roter Knopf, 3281m 46.978611,12.739444
Grossglockner, 3798m 47.074167,12.694444
Fuscherkarkopf, 3331m 47.098889,12.745556
Hocharn, 3254m 47.076111,12.937222
Hochalmspitze, 3360m 47.015000,13.321111
Univeristy of Vienna 48.212542,16.365265

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.