Softwarenews MB Routing

Hierfür implementiert wurde ein modifizierter Dijkstra-Algorithmus. Von einer maximal zu berücksichtigenden Entfernung ausgehend, wird für die Umkreissuche ein Quadrat aus dem Knoten-Kanten-Modell selektiert, welches den Ausgangspunkt als Zentrum und die doppelte gewählte Entfernung als Kantenlänge hat. Für die Entfernungsberechnung wird ein Rechteck ausgewählt, welches die maximale Entfernung abzüglich der Entfernung von Ausgangs- und Zielpunkt in der jeweiligen Achse in jeder Richtung enthält. Die Knoten und Kanten der Auswahl werden in den Arbeitsspeicher geladen und dort weiter verarbeitet. Der Dijkstra-Algorithmus wurde für das Routing dahingehend modifiziert, dass in die Berechnung jedes Weges die Entfernung des Endpunktes zum Zielpunkt einfließt. Dadurch werden unsinnige Wege früher erkannt und deren weitere Verfolgung abgebrochen.

Das Ergebnis der Entfernungsberechnung ist der kürzeste Pfad zwischen Anfangs- und Endpunkt, sowie die Summe der Längen der den Pfad bildenden Geraden. Für die Umkreissuche werden alle Knoten innerhalb der gewählten Entfernung als Zwischenergebnis ermittelt. Aus diesen Knoten wird abschließend ein konkaves Polygon gebildet, welches der Darstellung des Umkreises dient.

Problematisch erwiesen sich Abweichungen und Fehler in den Daten. In den Adressdaten sind Straßen, in Ausnahmefällen auch Ortsnamen, teilweise anders geschrieben, als im ATKIS. Im ATKIS fehlen Straßennamen, die Verbindungen insbesondere an der Grenze von Bundesländern sind stellenweise unterbrochen. Nicht trivial ist auch die Auswahl der Verkehrswege über die Attribute des ATKIS, da Fußwege am Straßenrand nicht immer über den Straßentyp identifiziert werden können. So ist die Aufbereitung der Daten für deren spätere Verwendbarkeit von herausragender Bedeutung.

Aus den Verkehrswegen wurde zur Realisierung des Routing ein Knoten-Kanten-Modell gebildet. Sämtliche Daten werden im Referenzprojekt in Tabellen in Microsoft SQLServer gehalten. Für die Geometrien wurde der Datentyp "geometry" verwendet.

Zunächst wurden die flächenhaften Elemente, insbesondere Plätze, skelettiert und so linienhafte Elemente aus ihnen abgeleitet. Die Skelettierung einer Fläche kommt der Nutzung derselben durch Fußgänger recht nah und ergibt so realistische Entfernungswerte. Diese Linien-Elemente wurden mit den linienhaften Elementen des ATKIS zusammengefasst und bilden so das Verkehrswegenetz Deutschlands.

Daran anschließend wurde das Verkehrswegenetz weiter in Geraden zerlegt. Dadurch entstehen Elemente mit konstanter Länge (nur Anfangs- und Endpunkt), was die spätere Verarbeitung stark vereinfacht. Die Anfangs- und Endpunkte der Geraden werden als Knoten geführt. Eine wesentliche Eigenschaft des Knoten-Kanten-Modells ist dessen Redundanzfreiheit; Knoten mit derselben Koordinate werden zu einem Knoten zusammengefasst, ebenso Geraden mit gleichen Knoten.

Die Adressdaten werden gesteuert durch Postleitzahl, Gemeinde und Straßenname mit der nächstgelegenen Kante verbunden. Dabei wird von der Adresse ein Lot auf die Kante gefällt und diese an dem Schnittpunkt mit dem Lot geteilt. Dadurch entstehen aus der einen Kante bis zu drei neue Kanten, die die Adresse als Knoten in das Modell einbeziehen.

Knoten und Kanten werden über eindeutige Kennziffern mit einander referenziert, so dass für eine Routing-Abfrage zwischen zwei Knoten nicht die vergleichsweise aufwändigen Geometrien verwendet werden müssen, sondern nur deren eindeutige Kennziffer. Darüber hinaus wurde für jede Gerade deren Länge als numerisches Attribut gespeichert und muss so nicht für jede an einer Abfrage beteiligte Gerade aufs Neue berechnet werden. Diese beiden Maßnahmen führen zu einer deutlichen Verbesserung der Performanz des Routings.