Interdisziplinäres Projekt Mathematik - Routenplaner Hellabrunn

• Aufgabenstellung
• Online-Routenplaner
• Dokumentation

Aufgabenstellung

Das Ziel dieses Projekts war die Entwicklung eines effizienten und benutzerfreundlichen Routenplaners für den Tierpark Hellabrunn . Basierend auf einem bereits abgeschlossenen Projekt wurden die folgenden Aufgaben bearbeitet:

• Erweiterung des bestehenden TSP-Algorithmus um eine Christofides-Heuristik.
• Programmierung eines Grapheditors um Karten erstellen und bearbeiten zu können.
• Programmierung eines über das Internet ausführbaren Routenplaners.
• Erstellen eines Datenmodells des Tierparks Hellabrunn.

Die folgenden Aspekte fanden bei der Ausarbeitung besondere Beachtung:

• Die Algorithmen sollen unabhängig von der konkreten Anwendung ohne Schwierigkeiten in späteren Projekten wiederverwendet und erweitert werden können.
• Der Routenplaner muss eine klare Bedienoberfläche haben und ohne (mathematische) Vorkenntnisse benutzbar sein.
• Die implementierten Algorithmen müssen schnell genug sein um in kurzer Zeit ein zufriedenstellendes Ergebnis zu liefern.

In einer weiterführenden Projektarbeit wurden Verallgemeinerungen des Traveling Salesman Problems untersucht. Dabei wurde ein Branch-and-Cut-and-Price Framework speziell für das Orienteering Problem entwickelt. Beim Orienteering wird eine Tour gesucht, die maximalen Profit auf den besuchten Knoten einsammelt und eine obere Schranke an die zur Verfügung stehende Zeit einhält. In der online-Version des Tierpark Applet ist derzeit nur eine Heuristik integriert. In Kürze wird jedoch auch in das exakte Lösungsverfahren für das Applet verfügbar sein.

Aufgabensteller

Prof. Dr. Peter Gritzmann

Betreuer

Dr. René Brandenberg

Bearbeiter

• Andreas Haug (haugin.tum.de)
• Stefan Hinterstoisser (hinterstin.tum.de)
• Philipp Menschner (menschnein.tum.de)
• Christoph Niedermayr (niedermcin.tum.de)

• Christian Böhm (christian.boehmmytum.de)
• Benjamin Broll(benjamin.brollgmail.com)