Kontinuierliche Standortprobleme in Polygonen

Das mathematische Problem der planaren Standortplanung taucht in einer Reihe von praktischen Zusammenhängen auf, z. B. in der Ökonomie. Dabei geht es darum, aus einer Menge von möglichen Standorten so eine Auswahl zu treffen, daß der Abstand zu einer die Nachfrage beschreibenden Menge optimiert wird. Die zahlreichen bisher in der Literatur veröffentlichten Untersuchungen gehen von diskreten Nachfrageverteilungen aus. Wir betrachten nun kontinuierliche Nachfrageverteilungen: als Zielfunktion wird der durchschnittliche Abstand für alle Punkte innerhalb eines betrachteten Polygons verwendet, diese stellen gleichzeitig die Menge zulässiger Standorte dar.

 

Abbildung: P(x, y) und sein Spiegelpunkt P'(-x, -y) sind die beiden Minimalstellen für den L₁-Abstand

Wir erhielten sehr unterschiedliche Ergebnisse für unterschiedliche Fragestellungen: Wird der Abstand mit der sogenannten Manhattan-Metrik gemessen, so läßt sich für ein zusammenhängendes Plazierungspolygon ohne Löcher die Plazierung eines einzigen Zentrums mit möglichst kleinem durchschnittlichen Abstand durch einen sehr schnellen Algorithmus lösen. Im Falle von Bereichen mit Löchern läßt sich immerhin noch ein Algorithmus angeben, der die Aufgabe in O(n²)löst; dieser läßt sich auch anwenden, wenn der Plazierungsbereich nicht zusammenhängend ist. Wird der Abstand anhand kürzester Wege gemessen, die den zulässigen Bereich nicht verlassen dürfen (sogenannte geodätische Abstände), so lassen sich die entsprechenden Fragestellungen für einen zusammenhängenden Bereich mit jeweils wenig mehr Aufwand beantworten. Sollen mehrere Zentren gleichzeitig plaziert werden, wird die Aufgabe gleich sehr viel komplexer: Für geodätischen Manhattan-Abstand und Polygone mit Löchern können wir zeigen, daß das Problem NP-schwer ist. Für euklidische Abstände sind bereits einfachste Fragestellungen mit lediglich fünf diskreten Nachfragepunkten und uneingeschränkter Plazierungsmenge in einem bestimmten algebraischen Sinne nicht algorithmisch lösbar, so daß man für die Verallgemeinerung auf kontinuierliche Nachfrageverteilung nicht auf effiziente algorithmische Lösungen hoffen kann.