Home

NetLogo

Methoden

Umsetzungen

Aktuelles

Forschung

Sonstiges

Links

Kontakt




















Linear Facility Optimierung / Standortoptimierung / Trassensuche 


Zurück zum Inhaltsverzeichnis


Anwendung des A* Algorithmus zur Trassensuche

Das 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).

Landnutzungskarte

zu Grunde liegendes Höhenmodell,
Mit freundlicher Genehmigung von M. Greweldinger

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.

Die Abbildung  zeigt eine Trasse, die nur die Distanzkosten berücksichtigt. In logischer Folge ergibt sich der kürzeste Weg aus der direkten Verbindung von Start- und Zielpunkt.
 Hier ist der Verlauf einer Trasse dargestellt, der die geringsten "Ökokosten" verursacht. Da die Landnutzung Acker die geringsten Kosten produziert, verläuft der optimale Weg so lange wie möglich durch Ackerfläche. Dem Landschaftsschutzgebiet (hellgrün) wird soweit möglich ausgewichen. Das Überqueren des Flusses erfolgt auf dem kürzesten möglichen Weg, da die Überschreitungskosten sehr hoch sind.
In diesem Bild wurde eine Trasse unter dem Gesichtspunkt ermittelt, die Zerschneidungskosten so gering wie möglich zu halten. Dies führt bei konsequenter Anwendung zu einem Trassenverlauf enlang der Grenzen der unterschiedlichen Flächennutzungen.
In dieser Darstellung wurde eine Trasse gesucht, die die geringsten Kosten zur Überwindung von Höhendifferenzen verursacht. Auf die Weglänge wurde keine Rücksicht genommen. Erwartungsgemäß verläuft die Trasse hauptsächlich entlang von Tälern. Bei den unvermeidlichen steilen An- oder Abstiegen reproduziert das Verfahren eine uralte Technik der Höhenüberwindung: die Serpentine:

 

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:

ask min-one-of open [t-cost] [set breed closed
reproduce]

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:

set t-cost t-cost + h-cost + m-cost

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:

set h-cost distance-nowrap aim

Hierbei steht aim für den Zielknoten. Die Berechnung von m-cost erfolgt nach der Formel:

set m-cost ((weight-elev-cost * elev-cost)
+ (weight-eco-cost * eco-cost)
+ (weight-zerschneidung-cost * zerschneidung-cost))
set m-cost distance-weight * m-cost

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:

set elev-cost
(((elevation - elevation-of patch-ahead -1 ) / 3 )^2)

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:

set zerschneidung-cost ((count patches


Applet (wird nachgereicht)