Entwicklung eines Routenplaners

Aufgabenstellung

Ihre Aufgabe ist die Entwicklung eines Routenplanungssystems für den PC. Das System soll über eine graphische Benutzeroberfläche verfügen, über die Anfragen komfortabel an das Programm gestellt werden können. Diese Anfragen sollen von einem von Ihnen implementierten Routingalgorithmus verarbeitet werden, dessen Ergebnisse wiederum die Oberfläche graphisch darstellt.

Es bestehen gewisse Freiheitsgrade beim Entwurf des Systems. So kann Ihr Routenplaner klassisch die schnellste Verbindung zwischen zwei gegebenen Punkten finden, oder z.B. die schönste Wanderstrecke bei benutzerdefinierten Steigungswerten und Streckenlängen berechnen. Bei der Kartendarstellung kann auf das Kartenrendering des OpenStreetMap -Projektes zurückgegriffen werden oder auch eine eigene Renderengin entwickelt werden. Diese und andere Schwerpunkte werden Sie bei Ihrem Projekt selbstständig setzen müssen.

Schnelle Routenberechnung

Das Standardverfahren zur Routenberechung ist der Algorithmus von Dijkstra. Dieser arbeitet für größere Graphen (wie z.B. das deutsche Straßennetz) aber zu langsam. Hier helfen sogenannte Speedup-Techniken, die Dijkstras Algorithmus zum Teil um vierstellige Faktoren beschleunigen. Für Ihr Projekt werden Sie unter Umständen eine solche Technik benötigen. Für Punkt-zu-Punkt-Anfragen empfehlen wir Ihnen z.B. die Verwendung von Arc-Flags, einer einfachen aber recht effektiven Speedup-Technik.

Teams

Es werden zwei Teams betreut, die beide die gleiche (oben beschriebene) Grundaufgabenstellung bekommen. Die Teams dürfen und sollen unabhängig voneinander ihre Schwerpunkte festlegen.

Termine

• Erstes Treffen: wird noch bekanntgegeben
• Abgabe Pflichtenheft: 
• Abgabe Entwurf:
• Implementierung bis:
• Abnahme:
• Abschlusspräsentation: