Purbacher Martiniloben – Shortest Path Problem


Jedes Jahr findet in meiner Heimtagemeinde das Martiniloben statt. Dabei öffnen insgesamt 15 Winzer ihre Kellertüren für zahlreiche Besucher. Bisher ist es vermutlich noch niemandem gelungen, alle Stationen zu besuchen. Um dieser Herausforderung Herr zu werden, reicht es nicht einfach nur trinkfest zu sein. Man braucht einen gut durchdachten und bestens optimierten Plan. Smile 

Tatsächlich gibt es 15! = 1,307,674,368,000 mögliche Reihenfolgen, in denen man alle Keller begehen kann. Der kürzeste Pfad ist daher nicht offensichtlich.

image

Mit Hilfe von Excel 2016, lässt sich sehr einfach ein Routenplanungswebservice aufrufen und eine Distanzmatrix berechnen:

image

Auf dieser Basis kann ein Optimierungsmodell erstellt werden:

image

Der kürzeste Weg lässt sich anschließend mit einem evolutionären Suchalgorithmus (Excel Solver Addin) heuristisch bestimmen:

image

Die kürzeste Route ist demnach:

Jobst – Leidl- Kiesling – Eitler – Schüller – Sandhofer – Filz – Ots - Hafner & Tschank- Leidl Putz – Gmeiner – Kreiler – Türkenkeller – Haselbauer - Foltin

Die Strecke lässt sich theoretisch in weniger als zwei Stunden zurücklegen. Das Modell abstrahiert dabei jedoch vom Einfluss burgenländischer Qualitätsweine.  Smile 

image

image

http://tinyurl.com/p4yg2qv


Comments (0)

Skip to main content