Standortplanung Löser

Pseudocode

Das Problem wägt zwei gegenläufige Kosten ab: Standorte zu eröffnen kostet Geld, doch jeder eröffnete Standort verkürzt den Weg zu den Kunden. Exakt formuliert ist es ein ganzzahliges Programm; in der Praxis nimmt man eine gierige Heuristik mit lokaler Verbesserung.

// Exakt (klein): jede Teilmenge von Standorten prüfen
bestes = unendlich
für jede nichtleere Teilmenge S der Kandidatenstandorte:
    kosten = Summe eröffnungskosten[f] für f in S
    für jeden Kunden c:
        kosten += min über f in S von servicekosten[f][c]
    bestes = min(bestes, kosten)

// Gierig (groß): den Standort mit der größten Ersparnis öffnen
S = {}
wiederhole:
    f* = geschlossener Standort mit größter Kostensenkung
    wenn f* zu öffnen die Kosten nicht senkt: abbrechen
    S = S + {f*}

// Danach: lokale Suche mit Tausch, Öffnen und Schließen

Entscheidend ist, dass Kunden stets dem für sie günstigsten eröffneten Standort zugewiesen werden, der einzige echte Freiheitsgrad ist also die Wahl der zu öffnenden Teilmenge. Das verwandelt ein scheinbar kontinuierliches Problem in ein kombinatorisches über Teilmengen, und genau das macht es NP-schwer: es gibt 2 hoch n Teilmengen und keinen bekannten Weg, sie in Polynomialzeit zu durchlaufen.

Durchgerechnetes Beispiel, Schritt für Schritt

Entscheide bei drei Kandidatenstandorten und vier Kunden, welche Standorte zu eröffnen sind, indem alle Teilmengen verglichen werden.

Beispielgraph: Eröffnungskosten: F1 kostet 10, F2 kostet 8, F3 kostet 6. Servicekosten je Kunde: F1 bedient C1 und C2 für 2 und 3, C3 und C4 aber für je 9; F2 bedient C3 und C4 für 2 und 3, C1 und C2 aber für 8 und 7; F3 bedient alle vier für je 5.

1. Nur F1 öffnen. Eröffnungskosten 10, dazu 2 + 3 + 9 + 9 an Service, insgesamt 33. F1 ist hervorragend für seine beiden nahen Kunden und miserabel für die anderen beiden.
2. Nur F2 öffnen. Eröffnung 8, dazu 8 + 7 + 2 + 3, insgesamt 28. Es ist das Spiegelbild von F1.
3. F1 und F2 öffnen. Eröffnung 10 + 8 = 18, und nun wählt jeder Kunde seine beste Option: 2 + 3 + 2 + 3 = 10 an Service, insgesamt 28. Die Servicekosten sind unschlagbar, doch zwei Eröffnungen zu bezahlen frisst den gesamten Vorteil auf.
4. Nur F3 öffnen. Eröffnung 6, dazu 5 + 5 + 5 + 5 = 20 an Service, insgesamt 26. F3 ist für keinen einzelnen Kunden die beste Wahl und gewinnt dennoch.
5. Alle drei öffnen. Eröffnung 10 + 8 + 6 = 24, dazu 2 + 3 + 2 + 3 = 10, insgesamt 34. Mehr Standorte zu öffnen verschlechtert das Ergebnis.

Optimal ist es, ausschließlich F3 zu eröffnen, mit Gesamtkosten 26. Dabei lohnt es sich innezuhalten: F3 ist für keinen Kunden der bevorzugte Standort, und dennoch ist genau diese Teilmenge optimal. Eine Heuristik, die jeden Kunden seinem günstigsten Servicestandort zuordnet, würde F1 und F2 eröffnen und bei 28 landen. Allein der Ausgleich zwischen Eröffnungs- und Servicekosten zählt, und kundenweises Denken erfasst ihn nicht.

Komplexität und woher sie kommt

Zeit: NP-schwer; exakt O(2^n · n · m) · Speicher: O(n · m)

Bei n Kandidatenstandorten und m Kunden prüft die exakte Aufzählung alle 2 hoch n nichtleeren Teilmengen und ordnet für jede die m Kunden ihrem günstigsten eröffneten Standort zu, mit O(n) je Kunde, was O(2 hoch n mal n mal m) ergibt. Das ist nur bis etwa 20 bis 25 Standorte praktikabel. Das Problem ist NP-schwer, ein exakter Polynomialzeitalgorithmus ist also nicht zu erwarten. Die gute Nachricht: die Variante ohne Kapazitäten ist approximierbar, es gibt Algorithmen mit konstantem Faktor um 1,5 auf Basis von LP-Rundung und lokaler Suche. Das steht im Gegensatz zur Graphfärbung, für die keine brauchbare Approximation bekannt ist. Das gierige Verfahren, das je Schritt den Standort mit der größten Ersparnis öffnet, hat eine logarithmische Garantie und schneidet praktisch gut ab.

Wann Standortplanung passt und wann nicht

Welche Variante passt, hängt davon ab, ob die Standorte Kapazitätsgrenzen haben und wie viele Kunden es gibt.

Häufige Fehler

• Kunden zuordnen, bevor die Öffnungsentscheidung steht. Die Zuordnung ist trivial, sobald die geöffnete Menge feststeht: jeder Kunde geht zu seinem günstigsten eröffneten Standort. Umgekehrt zu denken und zuerst den Lieblingsstandort jedes Kunden zu wählen führt zu Überöffnung, wie das Beispiel zeigt, in dem diese Logik 28 statt des Optimums 26 liefert.
• Annehmen, mehr Standorte helfen immer. Alle drei im Beispiel zu öffnen kostet 34 und ist damit schlechter als nur F3 mit 26. Jede Eröffnung fügt Fixkosten hinzu, die sich über die Serviceersparnis amortisieren müssen, und das tun sie häufig nicht.
• Vorhandene Kapazitätsgrenzen ignorieren. Die Variante ohne Kapazitäten erlaubt es einem Standort, alle Kunden zu bedienen. Gibt es in der Realität eine Nachfrageobergrenze, kann die kapazitätsfreie Optimallösung schlicht unzulässig sein, und es braucht die kapazitierte Formulierung.
• Euklidische Distanz verwenden, wo die echten Kosten anders liegen. Servicekosten enthalten oft Fahrzeit, Maut, Zeitfenster oder Zonentarife. Sie durch Luftlinie zu ersetzen verändert das Problem und häufig auch die Antwort.
• Das Ergebnis als endgültig behandeln, obwohl die Nachfrage schwankt. Standortwahl ist eine langfristige Entscheidung auf Basis einer Nachfrageprognose. Es lohnt sich zu prüfen, ob die optimale Teilmenge auch unter abweichenden Nachfragen optimal bleibt, bevor irgendetwas gebaut wird.

Häufig gestellte Fragen

Was ist das Standortproblem?

Gegeben eine Menge von Kandidatenstandorten mit Eröffnungskosten und eine Menge von Kunden mit Servicekosten von jedem Standort aus, fragt das Problem, welche Standorte zu eröffnen sind, um die Summe aus Eröffnungs- und Servicekosten zu minimieren. Es modelliert die Wahl von Lagerstandorten, die Platzierung von Servern, die Planung von Filialnetzen und die Standortwahl für Rechenzentren.

Warum ist die Standortwahl schwierig?

Weil die Kundenzuordnung trivial ist, sobald die Öffnungsentscheidung feststeht, das gesamte Problem also auf die Wahl einer Teilmenge von Standorten zusammenschrumpft. Bei n Kandidaten gibt es 2 hoch n Teilmengen und keinen bekannten Weg, sie in Polynomialzeit zu durchsuchen. Das Problem ist NP-schwer, wobei die Variante ohne Kapazitäten immerhin eine Approximation mit konstantem Faktor zulässt.

Was ist der Unterschied zwischen Standortwahl mit und ohne Kapazitäten?

Ohne Kapazitäten kann ein eröffneter Standort beliebig viele Kunden bedienen. Mit Kapazitäten hat jeder Standort eine Nachfragegrenze, sodass Kunden zu einem teureren Standort ausweichen müssen, weil der nächstgelegene bereits ausgelastet ist. Die kapazitierte Variante ist deutlich schwieriger und ihre Lösungen sind strukturell anders.

Senkt das Öffnen weiterer Standorte immer die Kosten?

Nein. Jede Eröffnung fügt Fixkosten hinzu, die sich nur rechtfertigen, wenn die Serviceersparnis sie übersteigt. Im obigen Beispiel kostet das Öffnen aller drei Standorte 34, während das Öffnen eines einzigen 26 kostet. Genau dieser Ausgleich zwischen Fix- und variablen Kosten ist der Kern des Problems.

Was ist der Unterschied zwischen Standortwahl und K-Means?

K-Means teilt Punkte in k Gruppen und minimiert die Distanz innerhalb jeder Gruppe, ganz ohne Eröffnungskosten und mit vorab festgelegtem k. Die Standortwahl entscheidet, wie viele und welche Standorte eröffnet werden, und wägt dabei Eröffnungs- gegen Servicekosten ab. K-Means ist ein Clusteringproblem, die Standortwahl eine wirtschaftliche Entscheidung.