Facility Location

Bei einem Facility Location Problem (FL) handelt es sich um ein Optimierungsproblem, in dem es darum geht aus einer Menge an Standorten eine Teilmenge als Versorgungsstandorte auszusuchen, dass diese unter den gegebenen Bedingungen optimal platziert sind. Das exakte Finden solcher Teilmengen gilt als algorithmisch schwierig und ist im Allgemeinen NP-hart.

Einführung

Anwendungen der Facility-Location sind sehr vielfältig. Es können optimale Standorte von Krankenhäusern zur Krankenversorgung bestimmt werden, für Firmen stellt sich zum Beispiel die Standortfrage von Fabriken, aber auch im Zuge der ständig fortschreitenden Expansion des Internets stellt sich die Frage der geschickten Positionierung von Servern.

Allgemein kann ein FL folgendermaßen formuliert werden: Aus gegebenen Mengen von Verbrauchern und Anbietern und gegebenen Kosten soll aus der Menge der Anbieter eine Teilmenge gefunden werden, so dass jeder Verbraucher von genau einem Anbieter versorgt wird und dabei die Kosten minimiert werden. Eine weitere Variante eines FL entsteht, wenn gefordert wird, dass jeder Verbraucher von mindestens einem Anbieter versorgt wird.

Die Kosten setzen sich dabei aus den paarweise vorliegenden Verbindungskosten zwischen Verbrauchern und Anbietern und den Kosten für die Eröffnung und/oder dem Betrieb eines Anbieters zusammen.

Bild 1: Die Filialen einer Supermarktkette Bild 2: Die möglichen Standorte der Zentrallager (rot) Bild 3: Eine Möglichkeit der Zuordnung Bild 4: Einer weitere Möglichkeit der Zuordnung

Beispiel

Den Filialen einer Supermarktkette sollen Zentrallager zugeteilt werden, in denen die Produkte gelagert und dann an die einzelnen Filialen geliefert werden. Die Lieferwege sollten dabei minimiert werden. Die Verbindungskosten c_ij berechnen sich also direkt aus der Distanz der Filiale i zum Standort j. Die Kosten der Eröffnung eines Standortes kann sich aus den Baukosten, den Grundstückskosten und den Unterhaltskosten zusammensetzen. Mit den Unterhaltskosten würden auch Standortvor- und -nachteile wie lokale Lohnkosten etc. berücksichtigt werden.

Je nach Höhe der Kosten der verschiedenen Standorte kann es günstiger sein nur einen Standort zu eröffnen und damit aber höhere Transportkosten zu tragen bis dahin, jeden der möglichen Standorte zu eröffnen.

Für dieses Beispiel gibt es mehr als 10 Billiarden Kombinationsmöglichkeiten (Kombinatorische Explosion). Ein moderner Computer bräuchte für die direkte Berechnung mehr als 300 Jahre.

Modellierung

Ein FL wird normalerweise als vollständiger bipartiter Graph G = (V,E) modelliert, wobei die Bipartion V aus der Vereinigung der beiden disjunkten Mengen F der Anbieter (facilities) und C der Verbraucher (customer) entsteht. Zusätzlich werden zwei positive Abbildungen $c:F\times C\to\mathbb R^+_0$ (Verbindungskosten) und $f:F\to\mathbb R^+_0$ (Eröffnungs-/Betriebskosten) definiert. Gilt für die Kostenfunktion c eine erweiterte Dreiecksungleichung, so spricht man vom metrischen Facility Location Problem:

$c(i,j):=c_{ij}\leq c_{ij'}+c_{i'j}+c_{i'j'}\ \forall i,i'\in F, j,j'\in C$.

Gesucht ist eine Teilmenge $F'\subseteq F$ und eine Zuordnung $\phi:C\to F'$ die:

$\sum_{i\in F'}f_i+\sum_{j\in C}c_{\phi(j)j}$

minimiert.

Lösbarkeit

Da es sich bei Facility Location um ein NP-schweres Problem handelt, werden zur Lösung Approximationsalgorithmen herangezogen. Im Gegensatz zu dem metrischen Facility Location Problem, das sich mit konstanter Güte approximieren lässt, kann das allgemeine Facility Location Problem (bei dem die Dreieicksungleichung also nicht gelten muss) nicht besser als $\mathcal{O}(\log n)$ approximiert werden. Im Folgenden sind einige Approximationsalgorithmen aufgeführt, die das metrische Facility Location Problem mit konstanter Güte approximieren:

Jain-Vazirani-Algorithmus

Kamal Jain und Vijay Vazirani stellten 2001^[1] einen Algorithmus vor, der auf einer primal-dualen Variante eines Linearen Programmes beruht. Dabei konnten sie nachweisen, dass das Ergebnis eine 3-Approximation ist, also höchstens dreimal schlechter ist als das Optimum. Die Laufzeit des Algorithmus beträgt $\mathcal{O}(m \log m)$, mit $m=\left|E(G)\right|$.

Mahdian-Ye-Zhang-Algorithmus

Mohammad Mahdian, Yinyu Ye und Yiawei Zhang veröffentlichten 2002 eine Variante eines Greedy-Algorithmus', der eine Lösung eines FL-Problems mit der Güte 1,52 approximiert. Der wesentlich bessere Faktor, um den sich die Lösung maximal vom Optimum unterscheidet muss allerdings mit einer höheren Laufzeit ($\mathcal{O}(n^3)$, mit $n=\left|V(G)\right|$) als der des Jain-Vazirani-Algorithmus bezahlt werden. ^[2]

Einzelnachweise

1. ↑ Kamal Jain, Vijay V. Vazirani: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. Journal of the ACM. 48 (2001). S. 274-296.
2. ↑ Mohammad Mahdian, Yinyu Ye, Yiawei Zhang: Improved Approximation Algorithms for Metric Facility Location Problems. 2002

Literatur

• Vašek Chvátal: Linear Programming. W. H. Freeman and Company, New York, 1983, ISBN 0-716-71587-2.

Weblinks

• Peter Kling: Facility Location. 2008. (PDF-Datei; 503 kB)