Software-Entwicklung (PSE) - ITI Prof. Sanders

  • Typ: Vorlesung (V)
  • Lehrstuhl: Prof. Dr. Peter Sanders
  • Ort:

    nach Vereinbarung
  • Zeit:

    nach Vereinbarung
  • Dozent:

    P. Sanders, G.V. Batz
  • SWS: 4
  • LVNr.: 24517
  • Prüfung:

    ja

Entwicklung eines Routenplaners für Radfahrer / Autofahrer / Fußgänger

Aufgabenstellung

Ihre Aufgabe ist die Entwicklung eines Routenplanungssystems für Radfahrer, Autofahrer, oder Fußgänger, das auf PCs läuft. Das System soll in der Lage sein für gegebenen Start- und Zielort optimale Routen zu berechnen. Weiterhin soll das System über eine graphische Benutzeroberfläche verfügen, über die einerseits Routenanfragen komfortabel an das Programm gestellt werden können, und die andererseits das Straßen- bzw. Wegenetz und die berechneten Routen graphisch darstellt.

Bei der Kartendarstellung kann auf das Kartenrendering des OpenStreetMap -Projektes zurückgegriffen werden oder auch eine eigene Renderengin entwickelt werden. Bei der Berechnung von Routen für Radfahrer order Fußgänger könnte z.B. auch die Höhe des Geländes berücksichtigt werden. Dafür kann man z.B. den SRTM -Datensatz verwenden. Natürlich kann man nicht alles machen, Sie müssen sich also ein stück weit entscheiden, welchen Schwerpunkt Sie bei ihrem Projekt setzten wollen.

 

Schnelle Routenberechnung

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

 

Termine

  • Erstes Treffen: Mitwoch 24.4.2013, 17:30, Raum 211 im Informatikbau am Fasanengarten (Gebäude 50.34). Bitte diesen Termin unbedingt wahrnehmen.
  • Abgabe Pflichtenheft: 17. Mai 2013, 23:59 Uhr
  • Anmeldeschluss zu PSE und TSE Prüfung: 20. Mai 2013 (ohne Gewähr)
  • Abgabe Entwurf: 14. Juni 2013, 23:59 Uhr

 

Materialien