Facility Location

Bei e​inem Facility Location Problem (FL) handelt e​s sich u​m ein Optimierungsproblem, i​n dem e​s darum g​eht aus e​iner Menge a​n Standorten e​ine Teilmenge a​ls Versorgungsstandorte auszusuchen, sodass d​iese unter d​en gegebenen Bedingungen optimal platziert sind. Das exakte Finden solcher Teilmengen g​ilt als algorithmisch schwierig u​nd ist i​m Allgemeinen NP-schwer.

Einführung

Anwendungen d​er Facility-Location s​ind sehr vielfältig. Es können optimale Standorte v​on Krankenhäusern z​ur Krankenversorgung bestimmt werden, für Firmen stellt s​ich zum Beispiel d​ie Standortfrage v​on Fabriken, a​ber auch i​m Zuge d​er ständig fortschreitenden Expansion d​es Internets stellt s​ich die Frage d​er geschickten Positionierung v​on Servern.

Allgemein k​ann ein FL folgendermaßen formuliert werden: Aus gegebenen Mengen v​on Verbrauchern u​nd Anbietern u​nd gegebenen Kosten s​oll aus d​er Menge d​er Anbieter e​ine Teilmenge gefunden werden, s​o dass j​eder Verbraucher v​on genau e​inem Anbieter versorgt w​ird und d​abei die Kosten minimiert werden. Eine weitere Variante e​ines FL entsteht, w​enn gefordert wird, d​ass jeder Verbraucher v​on mindestens e​inem Anbieter versorgt wird.

Die Kosten setzen s​ich dabei a​us den paarweise vorliegenden Verbindungskosten zwischen Verbrauchern u​nd Anbietern u​nd den Kosten für d​ie Eröffnung und/oder d​em Betrieb e​ines 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: Eine 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 ${\displaystyle c_{ij}}$ berechnen sich also direkt aus der Distanz der Filiale ${\displaystyle i}$ zum Standort ${\displaystyle 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 ${\displaystyle G=(V,E)}$ modelliert, wobei die Bipartion ${\displaystyle V}$ aus der Vereinigung der beiden disjunkten Mengen ${\displaystyle F}$ der Anbieter (facilities) und ${\displaystyle C}$ der Verbraucher (customers) entsteht. Zusätzlich werden zwei positive Abbildungen ${\displaystyle c\colon F\times C\to \mathbb {R} _{0}^{+}}$ (Verbindungskosten) und ${\displaystyle f\colon F\to \mathbb {R} _{0}^{+}}$ (Eröffnungs-/Betriebskosten) definiert. Gilt für die Kostenfunktion ${\displaystyle c}$ eine erweiterte Dreiecksungleichung, so spricht man vom metrischen Facility Location Problem:

${\displaystyle 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 ${\displaystyle F'\subseteq F}$ und eine Zuordnung ${\displaystyle \phi \colon C\to F'}$, die

${\displaystyle \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 Dreiecksungleichung also nicht gelten muss) nicht besser als ${\displaystyle {\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 ${\displaystyle {\mathcal {O}}(m\log m)}$, mit ${\displaystyle 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 ${\displaystyle 1{,}52}$ approximiert. Der wesentlich bessere Faktor, um den sich die Lösung maximal vom Optimum unterscheidet muss allerdings mit einer höheren Laufzeit (${\displaystyle {\mathcal {O}}(n^{3})}$, mit ${\displaystyle n=\left|V(G)\right|}$) als der des Jain-Vazirani-Algorithmus bezahlt werden.[2]

Literatur

• Vašek Chvátal: Linear Programming. W. H. Freeman and Company, New York, 1983, ISBN 0-7167-1587-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