Benutzer:Paul.Matthies/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-vollständig.

Einführung

Anwendungen der Facility-Location sind sehr vielfältig. Es können optimale Standorte von Krankenhäusern zur Krankenversorgung bestimmt weden, 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 paarweisen 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ücksischtigt 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, alle möglichen Standorte zu eröffnen.

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. Für die Kostenfunktion $c$ muss eine erweiterte Dreiecksungleichung gelten:

$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 Teilmeng $F'\subseteq F$ und eine Zuordnung $\phi :C\to F'$ mit

$\min \sum _{i\in F'}f_{i}+\sum _{j\in C}c_{\phi (j)j}.$

Lösbarkeit

Da es sich bei Facility Location um ein NP-schweres Problem handelt, werden zur Lösung Approximationsalgorithmen herangezogen, deren Lösung höchstens um einen konstanten Faktor k schlechter ist, als das Optimum.

Jain-Vazirani-Algorithmus

Kamal Jain und Vijay V. Vazirani stellten 2001 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 Logarithmus beträgt ${\mathcal {O}}(n^{2}\log n)$.

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.

Kategorie:Optimierung