In dieser Arbeit wurde ein neues Knozept, die Hierarchie berandeter Regionen (HBR), und Methoden, die optimale Kostensuche im Globalen und im Lokalen, entwickelt, um mittels einer HBR nach einer Preprocessing-Phase die Kosten eines optimalen Weges in einem fast planaren Straßennetz zu bestimmen. Der Aufwand dieser Verfahren wurde bezüglich dem Speicher und der Zeit abgeschätzt. Die Ergebnisse dieser Abschätzungen sind für vollständig zerlegte HBRen eines planaren Graphen, die mit einem sqrt(n)-Separator-Theorem erzeugt wurden, in der folgenden Tabelle zusammengefaßt.

| optimale Kostensuche | im Globalen | im Lokalen ---------------------------------------------------------------------------- Zeit | O(sqrt(n)) | mind. O(n^2 log n) Speicher | O(n sqrt(n)) | Zeit für Preprocessing | O(n^2 log n) | | evtl. O(n sqrt(n) log n) |

Die optimale Kostensuche im Lokalen wurde nicht weiter betrachtet, da sie für sqrt(n)-Separator-Theoreme nicht besser als bereits bekannte Verfahren ist.

Es wurde beschrieben, wie für fast planare Straßennetze eine HBR mittels einem planaren Separator-Theorem und einer in dieser Arbeit entwickelten Heuristiken aufgebaut und diese HBRen dann optimiert werden können.

Experimente an einem realen Straßennetz der Stadt Stuttgart mit 15224 Knoten und 38032 Kanten haben ergeben, daß die optimale Kostensuche im Globalen gegenüber dem Dijkstra-Algorithmus in diesem konkreten Straßennetz um den Faktor 1900 schneller ist. Berücksichtigt man auch die Zeit von 107 Minuten für die Preprocessing-Phase, so lohnt sich dieses Verfahren gegenüber dem Dijkstra-Algorithmus für das Stuttgarter Straßennetz erst, wenn die Kosten von 11000 optimalen Wegen bestimmt werden sollen und bereit ist, das 12,3-fache an Speicher zur Verfügung zu stellen.

Die Arbeit enthält außerdem kurze Zusammenfassungen von Veröffentlichungen, die sich mit dem Problem der optimalen Wegesuche in Straßennetzen und Graphen auseinandersetzen, insbesondere mit Heuristiken bzw. Algorithmen, die auf einem hierarchischen Ansatz beruhen.