| Linear Facility Optimierung / Standortoptimierung / TrassensucheAnwendung des A* Algorithmus zur TrassensucheDas kostenbasierte Vorgehen des A* Algorithmus erlaubt die Kombination mehrerer Kostenarten. Diese Eigenschaft soll im folgenden Beispiel dazu dienen, eine optimale Trasse für eine Infrastruktureinrichtung (zum Beispiel eine Straße) zwischen zwei Punkten in einem vorgegebenen Raum zu finden (siehe Abbildungen).
Zur Trassensuche werden vier verschiedene Arten von Kosten herangezogen. Die Distanzkosten beziehen sich auf die Länge der Trasse. Je länger die Trasse wird, desto höher die Distanzkosten. Im Modell werden die Kosten zur Überwindung unterschiedlicher Landnutzungen vereinfacht als "Ökokosten" bezeichnet. Sie entsprechen in etwa den ökologischen Wertigkeit einer Fläche So ist eine Trassenführung über eine Ackerfläche (braun) sehr kostengünstig, wohingegen das Passieren eines Landschaftsschutzgebiets (hellgrün) zwar theoretisch möglich ist, aber nur zu vergleichsweise sehr hohen Kosten. Des weiteren wurde versucht, Zerschneidungseffekte in die Suche nach der optimalen Trasse mit einzubeziehen. Führt eine Trasse mitten durch eine große Fläche mit homogener Landnutzung, sind die Kosten sehr hoch. Liegt sie am Rande eines solchen Gebiets entstehen nur geringe Kosten (siehe unter Technische Details). Der letzte Kostenfaktor bezieht sich auf die Überwindung von Höhendifferenzen. Große Steigungen oder Gefälle verursachen hohe Kosten; im ebenen Gelände wird dieser Kostenfaktor Null. Die Landnutzungen Stadt und FFH-Gebiet (rot beziehungsweise lila) sind programmtechnisch von der Durchquerung ausgeschlossen. Da keine allgemein gültige Theorie oder Methode bekannt ist, diese unterschiedlichen Kosten miteinander zu verrechnen, wurden alle Kostenarten dimensionslos belassen. Der Anwender muß über die Gewichtungen der einzelnen Posten entscheiden. Um die Funktionen der einzelnen Kostenarten anschaulich zu machen, wurde bei den folgenden Abbildungen jeweils nur eine Kostenart zur Trassensuche berücksichtigt.
Wie bereits angesprochen, sind die methodischen Probleme noch nicht gelöst. Problematisch ist nicht nur die Verrechnung und Gewichtung der unterschiedlichen Kostenarten, sondern auch die Ermittlung der Kostenhöhe selbst. Die Entwicklung einer solchen, fachlich begründeten Methode stellt eine eigene wissenschaftliche Arbeit dar. Die technischen Möglichkeiten hierfür sind gegeben. Trotz der genannten Unzulänglichkeiten wurde bei den unten stehenden Abbildungen versucht, eine möglichst realistische Gewichtung der Faktoren zu erreichen. Die FFH-Flächen (lila) im Nordwesten und in der Bildmitte werden umgangen. Im restlichen Verlauf der Trasse wurde versucht, ein vernünftiges Maß zwischen Weglänge, Flächenzerschneidung, ökologischer Wertigkeit und Relief zu finden.
Technische Details Zum Aufbau der NetLogo-Welt wurden drei Datenschichten (Landnutzung, Gewässernetz und Höhenmodell) aus ArcView exportiert und mittels file-I/O-Kommandos nach NetLogo importiert. Die Zellwerte wurden den Bildpunkten mittels patch-own-Variablen zugewiesen. Die farbliche Darstellung erfolgt über die Variable pcolor. Start- und Zielknoten werden als origin beziehungsweise aim definiert. Die OPEN und CLOSED Listen wurde mit Hilfe des breed-Konzeptes von NetLogo umgesetzt. Breeds erlauben die Verwaltung mehrerer Arten von turtles, die separat angesprochen werden können. Zur Expansion der Knoten, die durch turtles repräsentiert werden, wird in jedem Schritt diejenige turtle aus der OPEN Liste mit den geringsten Gesamtkosten ausgewählt:
Sie wird in die CLOSED Liste verschoben und reproduziert sich acht mal. Dabei werden die bisher aufgelaufenen Kosten an die Nachfolger weitergegeben. Die neuen Knoten werden auf die acht umliegenden patches verteilt. Die Berechnung der Gesamtkosten für jeden Knoten erfolgt nach der Formel:
wobei t-cost für die Gesamtkosten, h-cost für den Wert der heuristischen Schätzfunktion und m-cost für die Kosten des eben ausgeführten Schrittes stehen. Die heuristische Schätzfunktion lautet:
Hierbei steht aim für den Zielknoten. Die Berechnung von m-cost erfolgt nach der Formel:
Die Kosten werden durch die Summe der Multiplikationen der Kostenarten mit ihren jeweiligen Gewichten ermittelt. Im Anschluß werden die Gesamtkosten mit dem Distanzgewicht multipliziert. Die Formel zur Ermittlung der Höhenüberwindungskosten lautet:
Die Höhendifferenz zwischen einem Knoten und seinem Mutterknoten (der einen patch zurück liegt) wird gedrittelt und anschließend quadriert. Die Kalibrierung der Formel erfolgte anhand gewünschter Ergebnisse. Die "Ökokosten" für die unterschiedlichen Landnutzungen sind hart kodiert. Zur Ermittlung der Zerschneidungskosten wird ein sehr schwaches Verfahren angewandt. Die Kosten ergeben sich aus der Summe der Nachbarpatches im Radius 10 mit gleicher Landnutzung:
|