Benutzer:Paul.Matthies/Facility location

aus Wikipedia, der freien Enzyklopädie

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c_{ij}} berechnen sich also direkt aus der Distanz der Filiale Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} zum Standort Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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ü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 modelliert, wobei die Bipartion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V} aus der Vereinigung der beiden disjunkten Mengen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F} der Anbieter (facilities) und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} der Verbraucher (customer) entsteht. Zusätzlich werden zwei positive Abbildungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c:F\times C\to\mathbb R^+_0} (Verbindungskosten) und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f:F\to\mathbb R^+_0} (Eröffnungs-/Betriebskosten) definiert. Für die Kostenfunktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} muss eine erweiterte Dreiecksungleichung gelten:

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server 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 Teilmeng und eine Zuordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \phi:C\to F'} mit

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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[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 Logarithmus beträgt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}(n^2 \log n)} .

Jamal-Ye-Zhang-Algorithmus

[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

Kategorie:Optimierung

Abgerufen von „https://de.wikiup.org/index.php?title=Benutzer:Paul.Matthies/Facility_location&oldid=68769079“