Spatial Operations Research 

Operations Research (OR) ist ein Begriff aus den Wirtschafts- und Ingenieurwissenschaften und bezeichnet quantitative Modelle und Methoden zur Entscheidungsunterstützung. Ziel von OR ist die Optimierung von Unternehmensabläufen oder Produktionsverfahren. Neben einfachen linearen Optimierungsverfahren kommen Methoden, die dem Forschungsgebiet der Künstlichen Intelligenz (KI) entstammen, zum Einsatz

Geographische Fragestellungen, bei denen OR bisher eingesetzt wird, sind die Optimierung von Transport- und Logistiksystemen oder einfache Verfahren zur Standortsuche, die nur die Entfernungen zu Zulieferern und Kunden berücksichtigen. Dieses Gebiet wird zur Zeit fast ausschließlich von Wirtschaftswissenschaftlern bearbeitet. Lediglich im Bereich Geomarketing, arbeiten zahlreiche Geographen mit Methoden des OR. Dieser Artikel will die theoretischen Möglichkeiten des Einsatzes einer Spatial Operations Research (SOR) in der Angewandten Geographie aufzeigen.

Standortsuchverfahren und räumliche Planung sind klassische Gebiete der Angewandten Geographie. Die momentan angewandten Methoden zur Standortbewertung und Planung sind statische Verfahren. Mit Hilfe von Sachverstand, Erfahrung und Intuition werden verschiedene Lösungsalternativen zu einem Problem entworfen. Nutzwertanalytische Verfahren erlauben eine relative Bewertung der Varianten untereinander. Die Modellierung erwünschter oder unerwünschter Effekte eines Standortes beziehungsweise einer Planung auf den Raum erfolgt in Geographischen Informationssystemem. Untenstehende Abbildung zeigt vereinfacht den Ablauf einer Planung.

Unternehmen, die im freien Wettbewerb stehen, könnten sich ein solches Vorgehen nicht leisten. Prozeßabläufe müssen nicht nur funktionieren; sie sollten auch möglichst optimal sein um Kosten, Zeit, Material und schädliche Umweltauswirkungen zu minimieren. Die öffentliche Planung muß sich nicht dem Wettbewerb stellen. Trotzdem steht sie in der Pflicht, nicht nur gute, sondern auch möglichst optimale Standorte für öffentliche Einrichtungen oder Infrastrukturen zu finden. Mit der gängigen Vorgehensweise kann dieses Ziel nicht immer erreicht werden. Auch Unternehmen beschränken sich bei der Standortsuche auf den Vergleich mehrerer Varianten. Mangels einer entsprechenden Methode konnten bisher keine Versuche einer globalen Optimierung unternommen werden.

Der Gedanke einer erst noch zu schaffenden Spatial Operations Research besteht darin, die vorhandenen Methoden auf explizit räumliche Optimierungsprobleme anzuwenden. Die in diesem Artikel vorgestellten Anwendungen haben bisher einen rein experimentellen Charakter. Sie sind aber voll funktionstüchtig und liefern innerhalb der eingeschränkten Fragestellungen optimale oder , je nach methodischer Beschränkung, zumindest suboptimale Lösungen. Da Geographische Informationssysteme in der Regel nicht über die erforderlichen Funktionalitäten verfügen, wurden vorhandene Daten über Schnittstellen in ein externes programmierbares KI-Modul exportiert.

OR bedient sich eines reichhaltigen Methodensets, welches hauptsächlich von der angewandten Mathematik und der Informatik zur Verfügung gestellt wird. Nicht alle Verfahren eignen sich für geographische Fragestellungen. Im folgenden wird eine subjektive und selektive Auswahl von Methoden, die aus dem Gebiet der Künstlichen Intelligenz stammen, vorgestellt. Der Problematik entsprechend handelt es sich ausschließlich um Suchverfahren

Um ein Standortproblem zu lösen wird geballte Rechenkraft eingesetzt. Ein Computerprogramm generiert alle theoretisch möglichen Lösungsvarianten zu einem Suchproblem und bewertet sie mit Hilfe einer integrierten Evaluierungsfunktion. Diejenige Lösung, die den besten Wert erzielt, wird als optimales Ergebnis ausgegeben. Je mehr Rechenkraft und –zeit zur Verfügung steht, desto komplexere Suchvorgänge können bearbeitet werden. Probleme, die eine endliche und überschaubare Anzahl von theoretischen Lösungsmöglichkeiten besitzen, können auf diese Weise optimal gelöst werden können. Für kombinatorische Probleme ist das Verfahren ungeeignet, da Zahl der theoretischen Möglichkeiten exponentiell oder gar faktoriell ansteigt Der wesentliche Vorteil der Methode besteht darin, daß sie verläßlich das beste Ergebnis im Sinne der Evaluierungsfunktion ermittelt.

Für Suchprobleme, die aufgrund ihrer Komplexität für die Blinde Suche nicht geeignet sind, werden tausende bis abertausende zufällige Lösungskandidaten generiert. Für jeden Kandidaten wird die Leistungsfähigkeit ermittelt und die jeweils beste Lösung gespeichert. Der Lösungsgenerator muß so programmiert sein, daß die zufällig erstellten Lösungen das Problem zumindest theoretisch auch zufriedenstellend lösen können. Die Qualität der erzielten Lösung hängt von der investierten Rechendauer ab. Ein wesentlicher Vorteil der Methode ist, daß sie parallelisiert werden kann, das heißt, daß auf mehreren Rechnern gleichzeitig nach Lösungen gesucht werden kann. Es bleibt zu berücksichtigen, daß die Methode nicht erschöpfend ist, sondern es sich hierbei um eine Heuristik handelt. Der Nachweis, daß es keine bessere Lösung gibt, als die bisher gefundene, kann nicht erbracht werden

Eine weitere Möglichkeit, die Suche innerhalb eines großen Suchraums in eine plausible Richtung zu lenken ist die kostenbasierte Suche. Das Verfahren bezieht sich ursprünglich auf die Suche innerhalb von Suchbäumen, aber auch Rasterkarten können als eine alternative Schreibweise für einen Suchbaum verwendet werden. Das Verfahren eignet sich für die Optimierung linienhafter Einrichtungen und erlaubt das Auffinden des kostengünstigsten Pfades zwischen einem Start- und einem Zielkpunkt. Verschiedene Kostenarten wie z.B: Baukosten, Lärm, Umweltschäden oder die Überwindung von Höhenunterschieden werden während der Suche für die in Frage kommenden Flächen ermittelt und zu einem Gesamtkostenfaktor addiert. Die gefundene Lösung ist im Sinne der Optimierungsfunktion optimal, allerdings sind die methodischen Probleme zur Verrechnung der unterschiedlichen Kostenarten ungelöst.

Die Grundidee der genetischen Verfahren ist der biologischen Evolution entlehnt. Zu einem Suchproblem wird eine Anfangspopulation von zufällig generierten Lösungskandidaten entworfen. Der Lösungsansatz jedes Individuums wird mittels einer Evaluierungsfunktion bewertet. Diejenigen Individuen, deren Lösungen vergleichsweise gut sind, vermehren sich. Die Kandidaten, deren Bewertung schlecht ausfällt sterben über einen gewissen Zeitraum hinweg aus Bei der Vermehrung wird die Lösung der Eltern an die der Kinder in leicht mutierter Form weitergegeben. Die erfolgreichen Kandidaten reproduzieren sich oft. Durch die ständige zufällige Mutation und Selektion entstehen auf evolutionäre Weise nach mehreren Generationen Lösungen, die gut an ihre Evaluierungsfunktion angepaßt sind. Die so generierten Lösungen sind nicht zwingend reproduzierbar. Auch ist eine absolute Bewertung der Lösungen nicht möglich, da die optimale Lösung nach wie vor nicht bekannt ist. Es läßt sich lediglich die Aussage treffen, daß eine Lösung besser ist, als eine andere. Dies ist zugegebener Maßen eine unzufriedenstellende Tatsache, aber das Verfahren ermöglicht das Finden suboptimaler Lösungen zu Problemen, die vorher als unlösbar galten (wie z.B. das Problem des Handlungsreisenden).

Veränderungen im Raum wie beispielsweise die Ausweisung eines Wohngebiets oder der Bau eines Einkaufszentrums verändern die Gewohnheiten und Bewegungsmuster der Menschen. Wenn es gelingt, menschliches Verhalten im Computer zu simulieren, könnten Folgeerscheinungen wie Änderung der Verkehrsströme oder die zu erwartende Laufkundschaft einer Einrichtung ermittelt werden. Agentenbasierte Simulation ist an sich kein Suchverfahren, aber es kann mit den o.g. Verfahren kombiniert werden.

Bei der Standortsuche für eine einzelne Einrichtung wie ein Baugebiet oder eine Müllverbrennungsanlage müssen mehrere Faktoren berücksichtigt werden. Mit einer Blinden Suche lassen sich sämtliche metrisch skalierte Indikatoren flächendeckend berechnen. Für jeden Bildpunkt können Sichtbeziehungen, Distanzen oder Bodenpreise ermittelt werden und mittels einer geeigneten Bewertungsfunktion zu einem Gesamtnutzen zusammengefasst werden. Die Gewichtung der einzelnen Faktoren obliegt dem Planer (und damit auch subjektiven Einflüssen). Die nächste Abbildung zeigt die Ermittlung der Anzahl der Bewohner um eine Einrichtung, von der Geruchsbelästigungen ausgehen. Für jede mögliche Windrichtung wird die Anzahl der Betroffenen aufgrund einer Bevölkerungsdichtekarte in einem bestimmten Radius ermittelt.

Bei Einrichtungen wie Filialbetrieben, Mobilfunkmasten oder Rettungswachen kommen zwei weitere Faktoren zur Geltung. Zum einen muß berücksichtigt werden, daß sich ihre Wirkungsbereiche gegenseitig beeinflussen. Zum anderen kommt eine Optimierung mit der Blinden Suche nicht mehr in Frage, da die Anzahl der theoretischen Platzierungsmöglichkeiten mit der Anzahl der möglichen Standorte und Einrichtungen faktoriell ansteigt. Beispielhaft soll das Vorgehen anhand der Positionierung von Mobilfunkmasten illustriert werden. In einem gegebenen Raum sollen eine bestimme Anzahl von Masten so verteilt werden, daß eine möglichst hohe Abdeckung des Gebiets erreicht wird. Für die Verteilung von X Masten auf einer Anzahl von Y möglichen Standorten gibt es Y ! / X ! unterschiedliche Möglichkeiten. Nach der Monte-Carlo Methode positioniert ein Lösungsgenerator die Masten zufällig über die Fläche. Sind alle Masten gesetzt, wird die Signalausbreitung modelliert und die Güte der Positionierung über eine Evaluierungsfunktion nutzwertanalytisch ermittelt. Dazu wird der Signalabdeckung in den unterschiedlichen Landnutzungen ein Gewicht zugewiesen. Es liegt nahe, der Signalabdeckung in Wohngebieten und auf Straßen ein höheres Gewicht zuzuweisen, als anderen Flächen. Der so ermittelte Nutzwert beschreibt die Güte der Lösung. Dieser Prozeß wird nun beliebig oft wiederholt. Diejenige Lösung, die den höchsten Nutzwert erzielt hat, wird gespeichert und während des Programmablaufs gegebenenfalls durch neuere, bessere Lösungen ersetzt. Die Qualität der Lösung verbessert sich mit der eingesetzten Rechenzeit, die tatsächlich optimale Lösung wird in endlicher Zeit nie erreicht. Eine andere Herangehensweise wäre ein genetisches Verfahren, welches ebenfalls die Qualität der Positionierungen mißt und durch Mutation (leichte Veränderungen der x- und y-Koordinaten der Masten) und Selektion eine gute Lösung findet.

Bei der Planung und Optimierung linienhafter Einrichtungen wie Straßen, Hochspannungsleitungen oder Pipelines muß ein Kompromiß zwischen Baukosten, schädlichen Umweltauswirkungen und technischen Anforderungen gefunden werden. Eine Trasse, die die gestellten Bedingungen optimal erfüllt kann mit einer kostenbasierten Suche gefunden werden. Dabei können Sichbarkeit, Lärmausbreitung oder Baukosten gleichzeitig entsprechend den planerischen Vorgaben optimiert werden. die linke Abbildung  zeigt eine solche optimale Trasse (weiß). In diesem Beispiel haben die Landnutzungen  unterschiedlichen Querungskosten. Die gefundene Trasse verläuft nicht entlang des kürzesten Weges sondern versucht sowohl die Querungskosten als auch die Baukosten (bedingt durch die Länge der Trasse) so gering wie möglich zu halten. In der echten Abbildung wurde die Trasse hinsichtlich den geringsten Höhenüberwindungskosten optimiert. 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.

Der bisherige Ansatz in der Angewandten Geographie zur Lösung von Praxisproblemen leidet unter der Schwäche, nur bereits vorhandene Lösungsansätze bewerten zu können. Die gezeigten Beispiele haben, wenn auch auf abstrakter Ebene, veranschaulicht, daß die im OR angewandten Verfahren prinzipiell auch in der Lage sind, Problemlösungen zu geographischen Fragestellungen zu generieren. Methodisch bedingt sind die gefundenen Lösungen nicht immer absolut bewertbar, eventuell nicht einmal reproduzierbar. Diese Eigenschaft teilen sie mit den bisherigen Verfahren. Dies ist aus wissenschaftlicher Sicht unbefriedigend. Die Angewandte Geographie steht jedoch in der Pflicht, Lösungen zu Problemen aus der Praxis anbieten zu können.

Im Rahmen eines SOR besteht die Aufgabe des Fachmanns darin, ein räumliches Optimierungsproblem in eine computergerechte Form zu bringen und die Definition einer guten Lösung zu erstellen. Den Prozeß der Suche und Optimierung kann der Computer in Verbindung mit KI-Methoden vornehmen. Natürlich muß der Mensch immer die letzte Instanz bleiben, die eine Lösung auf ihre Plausibilität und Umsetzbarkeit prüft. Wie ein zukünftiges Spatial Operations Research in der Angewandten Geographie aussehen könnte, zeigt folgende Abbildung.