Untersuchung der Struktur großer Straßennetzwerke

Abstract

In den letzten Jahren hat die Bedeutung von Geoinformationen durch das Aufkommen von navigationsfähigen Smartphones und personalisierter Werbung stark zugenommen. Diese Anwendungsbereiche, aber auch intelligentes Routing oder Verbesserungen im Straßenbau, benötigen exakte, detaillierte Karten, die Straßendaten mit Points of Interests oder Stauinformationen vernetzen. Im Jahr 2004 wurde durch die Gründung von OpenStreetMap eine Plattform für eine Open Source Straßenkarte geschaffen, an der sich jeder mit einem GPS Empfänger oder GPS fähigem Smartphone beteiligen kann. Der Open Source Ansatz kann jedoch auf Grund fehlender Organisationsstrukturen auch ein Problem sein. Dies lässt sich alleine an 199 unterschiedlichen Straßentypen erkennen, von denen jedoch nur 20-30 Typen weitere Verbreitung erfahren. Auch werden viele Straßen uneinheitlich eingepflegt. Dennoch ist die Qualität der OSM bereits heute in manchen Bereichen gleichwertig oder besser als kommerzielle Alternativen. Um die OpenStreetMap algorithmisch verwenden zu können, muss zunächst eine Transformation und eine Bereinigung der Karte durchgeführt werden, da das Ursprungsformat nicht für die algorithmische Bearbeitung geeignet ist und viele nicht benötigte Informationen enthält. Die vorliegende Studienarbeit beschäftigt sich im Kapitel 2 mit der Umwandlung in ein algorithmisch gut verwendbares Datenformat und der Bereinigung des Graphen. In den Kapiteln 3 und 4 geht es um die Ermittlung von grundlegenden Eigenschaften des Graphen, die zur Optimierung und Laufzeitabschätzung von Algorithmen benötigt werden. Durch die Analyse der Verzerrung der Weglängen und Distanzen werden Hinweise auf problematische Gebiete im Graphen gegeben.