Plan Your Roundtrip
Plan Your Roundtrip ist ein Projekt, welches ich für meine Bachelorarbeit an der Universität Wien umsetzte. Aufgrund meiner Programmierkenntnisse war es mir möglich, ein wirtschaftliches Thema mit der Informatik zu verbinden. Im Folgenden gebe ich eine Übersicht über das Projekt.
Webseite: www.roundtrip.at
Github: github.com/quellpunkt/roundtrip
Mit Plan Your Roundtrip stelle ich einen Service zur Verfügung, der eine Lösung für das Traveling Salesman Problem liefert. Zur Berechnung werden Heuristiken verwendet und das Ergebnis daher vom Optimum abweichen. Obwohl Heuristiken nicht immer die optimale Lösung finden, ist es doch möglich ein gutes Ergebnis in kurzer Rechenzeit zu liefern.
Was ist das Traveling Salesman Problem?
Das Traveling Salesman Problem befasst sich mit dem Finden der kürzesten Rundreise. Ausgehend von einem Startpunkt werden verschiedene Orte und schließlich wieder der Ausgangspunkt besucht. Ziel ist es, die Kosten, die Zeit oder die Wegstrecke zu minimieren. Für einen genaueren Einblick in das Thema besuchen Sie die Wikipedia Seite Problem des Handlungsreisenden.
Welche Algorithmen wurden implementiert?
Es wurden zwei Algorithmen implementiert:
Der Nearest Neighbor Algorithmus liefert eine Ausgangslösung. In jedem Schritt sucht er nach dem nähesten Nachbar und fügt ihn anschließend zur Rundreise hinzu.
Nachdem eine Ausgangslösung gefunden wurde, sucht der 2-opt Algorithmus nach Verbesserungen. Dies geschieht, indem in jedem Schritt die Reihenfolge zwischen zwei Punkten invertiert wird. Verbessert sich die ursprüngliche Lösung, so wird die Verbesserung zur neuen Ausgangslösung. Danach beginnt der Prozess erneut. Der Algorithmus kommt schließlich zu einem Ende, wenn keine weitere Verbesserung erzielt wird.
Beschränkungen
Plan Your Roundtrip verwendet Google Maps für Berechnungen und mehr. Dadurch kommt es allerdings zu Einschränkungen. Im Moment können Benutzerinnen und Benutzer daher nur bis zu 10 Städte auswählen und eine Rundreise berechnen.
Lizenz
Ich habe die JavaScript-Datei zur Berechnung der Heuristiken unter der MIT-Lizenz veröffentlicht. Sie können diese Software also für alle Zwecke verwenden. Den genauen Wortlaut der Lizenz können Sie hier finden.
Weitere Informationen
Sie können mich gerne für weitere Informationen kontaktieren.
Sehen Sie sich auch meine anderen Projekte an.