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

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