Die Standortwahl verständlich erklärt

Wer Lager, Werke oder Filialen plant, muss entscheiden, welche möglichen Standorte sich lohnen. Das ist eine Grundsatzentscheidung, die sich nur mit hohem Aufwand zurücknehmen lässt. Umso wichtiger ist zu wissen, wie weit eine gefundene Auswahl höchstens vom Besten entfernt ist. Diese Seite erklärt zuerst ohne Formeln, warum sich das bei der Standortwahl ohne Kapazitätsgrenze in den meisten Beispielen der Demo sehr genau ausrechnen lässt, und danach für Fachleute mit Modell, Formeln, Messwerten und Grenzen.

Zuletzt aktualisiert: 28. Oktober 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Welche Lager lohnen sich?

Stellen Sie sich einen Händler vor, der Kundschaft in einer ganzen Region beliefern will. Es gibt mehrere mögliche Orte für Lager, aber nicht jeder Ort wird gebraucht. Jedes eröffnete Lager kostet Miete und Personal, ganz gleich, wie viel dort umgeschlagen wird. Fachleute nennen das Fixkosten. Dazu kommen die Kosten der Fahrten: Je weiter ein Lager von seinen Kunden entfernt ist und je mehr diese bestellen, desto teurer wird es.

Jede Kundin und jeder Kunde wird vom nächsten geöffneten Lager beliefert. Außerdem kann ein Lager beliebig viele Kunden bedienen; eine Obergrenze für die Liefermenge, eine Kapazitätsgrenze, gibt es in dieser Fassung des Problems nicht. Die Frage lautet nur noch: Welche Lager machen wir auf? Mehr Lager bedeuten kürzere Wege, aber mehr Fixkosten. Weniger Lager sparen Miete, verlängern aber die Wege. Irgendwo dazwischen liegt die günstigste Auswahl.

Eine solche Standortwahl ist eine Grundsatzentscheidung: Man trifft sie selten, und rückgängig machen lässt sie sich nur mit hohem Aufwand. Deshalb will man nicht nur eine gute Auswahl finden, sondern auch wissen, wie gut sie ist.

Woher weiß man, ob eine Auswahl gut ist?

Alle Kombinationen durchzuprobieren funktioniert nur bei wenigen möglichen Orten, denn mit jedem weiteren Ort verdoppelt sich die Zahl der Kombinationen. In der Praxis nutzt man deshalb einfache Faustregeln, in der Fachsprache Heuristiken. Eine Regel öffnet nacheinander das Lager, das die Gesamtkosten am stärksten senkt. Eine andere beginnt mit allen Lagern und schließt nacheinander das entbehrlichste. Solche Regeln liefern schnell eine Auswahl, sagen aber nicht, wie weit sie vom Besten entfernt ist.

Dafür braucht man eine Untergrenze, in der Fachsprache Schranke: einen Kostenwert, unter dem keine Auswahl liegen kann. Liegen die Kosten der gefundenen Auswahl dicht über der Untergrenze, ist bewiesen, dass es kaum noch besser geht. Entscheidend ist, wie scharf die Untergrenze ist, also wie dicht sie unter den Kosten der tatsächlich besten Auswahl liegt, dem Optimum. Eine sehr niedrige Untergrenze stimmt zwar immer, sagt aber nichts.

Warum die Untergrenze hier so scharf ist

Eine Untergrenze gewinnt man mit einer Probe-Rechnung unter gelockerten Regeln (Fachwort: Relaxation). Man erlaubt, ein Lager nur zu einem Teil zu eröffnen und dafür nur einen Teil der Miete anzusetzen. Das Ergebnis ist nie teurer als die beste echte Auswahl, also eine gültige Untergrenze. Wie scharf sie wird, hängt davon ab, welchen Teil der Miete man für ein nur teilweise geöffnetes Lager ansetzt.

Ein Bild dazu: Ein Lager kostet Miete. In der lockeren Rechnung verteilt man die Miete anteilig auf die ganze Kundschaft. Beliefert ein Lager nur einen von sehr vielen Kunden, setzt man nur einen winzigen Bruchteil der Miete an. Die Rechnung kommt dadurch auf zu niedrige Kosten, und die Untergrenze liegt weit unter den Kosten der besten echten Auswahl.

In der strengen Rechnung gilt: Sobald ein Lager auch nur einen einzigen Kunden vollständig beliefert, zählt die ganze Miete, gleichgültig, wie wenige andere Kunden dort noch dazukommen. Damit wird die Miete fast voll angesetzt, und die Rechnung bleibt nah an den echten Kosten. In der Demo trifft diese strenge Rechnung bei fast allen Beispielkarten genau die Kosten der besten echten Auswahl. Fachleute nennen die strenge Rechnung stark und die lockere schwach.

Beide Rechnungen gehören zur selben Aufgabe. Der Unterschied liegt nur in der Formulierung. Die Demo misst das und zeigt außerdem: Je höher die Fixkosten sind, desto weniger Lager lohnen sich, und desto größer wird der Abstand der lockeren Untergrenze zum Besten. Die strenge bleibt auf den Beispielkarten der Demo nah am Besten.

Was hilft, und wo wird es trotzdem schwer?

Auf den zufällig erzeugten Karten der Demo kommen die einfachen Faustregeln dem Besten nahe. Die scharfe Untergrenze sorgt dafür, dass man das auch weiß, statt es nur zu hoffen. Die Regel, mit allen Lagern zu beginnen und zu schließen, schneidet in der Demo auf diesen Karten in der Mehrzahl der Fälle besser ab als die Regel, Lager nacheinander dazuzunehmen.

Schwer wird es bei Aufgaben, in denen die Kosten nur wenige ganzzahlige Werte annehmen, sodass viele Wege oder Auswahlen exakt gleich viel kosten. Fachleute sprechen von Gleichständen. Dort liegt die Untergrenze in der Demo deutlich weiter unter dem Besten, und keine der Faustregeln ist durchgängig die beste. Der übliche Grund: Bei exakt gleichen Kosten kann die Probe-Rechnung Lager halb öffnen und zwischen gleich guten Auswahlen mischen, und das ergibt Kosten unter jeder echten Auswahl. Die Demo zeigt das an einer eigens konstruierten Aufgabe, nicht an einem Praxisfall.

Wie ernst ist das Modell zu nehmen?

Die Demo ist ein stark vereinfachtes Modell: Die Karten sind zufällig erzeugt, die Kosten wachsen gleichmäßig mit der Entfernung, die Lager haben keine Kapazitätsgrenze, und es gibt nur eine Ebene ohne Zwischenlager und ohne Tourenplanung. Sie zeigt, wie sich die Rechnung verhält, nicht welche Standorte für ein bestimmtes Unternehmen richtig wären.

Für eine Entscheidung heißt das: Eine gute Auswahl allein genügt nicht, man will wissen, wie viel besser es höchstens noch gehen könnte. Fragen Sie Ihren Planer oder Anbieter deshalb: Wie viel günstiger könnte die beste Auswahl höchstens sein als Ihr Vorschlag, und womit ist das belegt? Ein großer Abstand kann am Vorschlag liegen oder nur an einer lockeren Formulierung der Rechnung. Das gilt für Aufgaben ohne Kapazitätsgrenze; sobald Lager begrenzt sind, kann die Untergrenze wieder schwächer werden.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Modell: Kandidaten \(I\), Kunden \(J\), Fixkosten \(f_i\), Zuordnungskosten \(c_{ij}\) (Nachfrage mal Entfernung). Ohne Kapazitätsgrenze (Uncapacitated Facility Location, UFL) nimmt jeder Kunde den billigsten offenen Standort; zu entscheiden ist nur, welche Standorte offen sind.
• Netze: erzeugte Karten mit Standorten und Kunden ohne Fremddaten, Kosten linear in Entfernung und Nachfrage (Luftlinie in Zehntel-Einheiten, ganzzahlig). Standard: 25 Kandidaten, 50 Kunden, Fixkosten-Faktor 100 %, Zufalls-Seed 1.
• Verfahren: exaktes Optimum und beide LP-Schranken mit HiGHS, die Heuristiken Add, Drop und Interchange sowie Dual Ascent als Schranke ohne LP-Löser.
• Kontrast: Dieselbe Ja/Nein-Entscheidung kommt im Fixkosten-Netzdesign vor; dort war die LP-Schranke schwach (im Mittel 70,7 % des Optimums), hier ist sie fast exakt.

Die Formeln

Starke Formulierung: Die Kopplung \(x_{ij}\le y_i\) gilt je Kunde und Standort. Bei ganzzahligem \(y\) ist \(x\) von selbst ganzzahlig, denn jeder Kunde nimmt den billigsten offenen Standort.

\[\min\sum_i f_iy_i+\sum_{i,j}c_{ij}x_{ij}\quad\text{u.d.N.}\quad\sum_i x_{ij}=1\ \ \forall j,\quad x_{ij}\le y_i\ \ \forall i,j,\quad y_i\in\{0,1\},\ x_{ij}\ge0.\]

Schwache Formulierung: \(\sum_j x_{ij}\le |J|\,y_i\) statt \(x_{ij}\le y_i\). Die LP-Lösung setzt \(y_i=\frac1{|J|}\sum_jx_{ij}\) und zahlt nur den gelieferten Bruchteil der Fixkosten; die starke Kopplung verlangt dagegen für jeden Kunden den ganzen Standort.

Dual der starken LP (nach Elimination der Multiplikatoren von \(x_{ij}\le y_i\)):

\[\max\sum_j v_j\quad\text{u.d.N.}\quad\sum_j\max(0,v_j-c_{ij})\le f_i\ \ \forall i.\]

Dual Ascent (Erlenkotter 1978) startet mit \(v_j=\min_ic_{ij}\) und hebt die Kundenwerte an, bis ein Standort knapp wird, also \(f_i=\sum_j\max(0,v_j-c_{ij})\) gilt. \(\sum_jv_j\) ist eine untere Schranke ohne LP-Löser. Öffnet man knappe Standorte so, dass kein Kunde zu zwei offenen mit \(v_j>c_{ij}\) beiträgt (Komplementarität), sind die Kosten gleich \(\sum_jv_j\), und die Lösung ist bewiesen optimal. Die Anpassung ist gegenüber Erlenkotters DUALOC vereinfacht.

Befunde

Alle Zahlen stammen aus den Tests der Demo (tests/test_claims.py) und gelten für erzeugte Netze mit festen Zufalls-Seeds (ab 100000: 40 Netze für die Verteilung, 20 je Wert der Fixkosten-Reihe), sofern nichts anderes genannt ist. Als „Kartennetze“ gelten Netze mit 25 Kandidaten, 50 Kunden und Fixkosten-Faktor 100 %. Prozentwerte der LP-Schranken beziehen sich auf das Optimum; die der Heuristiken geben den Abstand über dem Optimum an.

Frage	Befund
Standardnetz (25 Kandidaten, 50 Kunden, Fixkosten-Faktor 100 %, Zufalls-Seed 1)	Das Optimum kostet 39 967 und öffnet 8 Standorte. Starke LP 100,0 %, schwache LP 63,6 %.
Wie nah liegt die starke Schranke am Optimum (40 Kartennetze)?	Starke LP im Mittel 99,99 % (schlechtestes Netz 99,65 %); der LP-Wert ist in 38 von 40 Netzen gleich dem Optimum. Das Optimum öffnet 7 bis 10 Standorte (Mittel 8,7).
Und die schwache Schranke (40 Kartennetze)?	Im Mittel 61,0 % (schlechtestes Netz 53,7 %, bestes 69,3 %).
Wie hängen Schranken und Standortzahl von den Fixkosten ab (Faktor 25 / 50 / 100 / 200 / 400 %, 20 Netze je Wert)?	Offene Standorte im Mittel 13,55 / 11,35 / 8,65 / 6,5 / 4,4. Starke LP 100,0 %, mit LP-Wert gleich Optimum in 20 / 20 / 19 / 19 / 19 von 20 Netzen. Schwache LP 81,1 / 71,4 / 61,1 / 52,1 / 46,1 %.
Wie nah kommen die Heuristiken (Abstand zum Optimum, 40 Kartennetze)?	Add im Mittel 1,87 % (Median 1,01 %, schlechtestes Netz 7,96 %, exakt in 6 Netzen). Drop 0,11 % (Median 0,00 %, schlechtestes 0,84 %, exakt in 27). Interchange 0,11 % (Median 0,00 %, schlechtestes 1,37 %, exakt in 32). Drop ist in 32 Netzen besser als Add und in einem schlechter.
Wie scharf ist Dual Ascent (40 Kartennetze)?	Ohne Anpassung im Mittel 87,8 % (schlechtestes Netz 76,7 %); mit Anpassung 99,4 % (schlechtestes 97,3 %, in 30 Netzen mindestens 99 %). Im Standardnetz schwankt die Schranke je nach Reihenfolge der Kunden ohne Anpassung zwischen 32 870 und 37 781, mit Anpassung zwischen 33 924 und 39 944.
Wann wird UFL schwer (Gleichstandsnetze: 30 × 30, ganzzahlige Kosten 1 bis 5, Fixkosten 3 oder 4, 40 Netze)?	Starke LP im Mittel 97,3 % (schlechtestes Netz 95,3 %); der LP-Wert ist nur in 1 von 40 Netzen gleich dem Optimum. Schwache LP 69,9 %. Add 3,07 %, Drop 5,02 %, Interchange 1,79 %; Add ist in 20 Netzen besser als Drop, in 8 schlechter, also umgekehrt wie auf den Karten.
Kleinstes Beispiel mit gebrochener LP (Lehrnetz „LP gebrochen“, 3 Standorte, 4 Kunden)	Das Optimum kostet 25, die starke LP kommt nur auf 24,5 (98,0 %), die schwache auf 18,25 (73,0 %).

Die Demo hält auch fest, was sich nicht bestätigt hat: Dual Ascent ohne Anpassung liefert keine Schranke nahe der LP, und die Auswahl aus den knappen Standorten liegt im Mittel 4,0 % über dem Optimum und ist nur in 4 Kartennetzen als optimal bewiesen. Die Formulierung macht den Unterschied zwischen 61 % und fast 100 %, nicht das Modell.

Grenzen

• Unkapazitiert: Mit Kapazitäten und Single-Sourcing ist die Schranke wieder schwach; das ist das nächste Stück der Linie mit Lagrange-Relaxation.
• Stilisierte Netze: erzeugte Karten ohne Fremddaten, Kosten linear in Entfernung und Nachfrage, eine Ebene (kein Location-Routing), keine feste Standortzahl (p-Median). Die Gleichstandsnetze sind eine Konstruktion, kein Praxisfall.
• Gleichstände: Auf ihnen gelten die Befunde der Kartennetze nicht; dort ist der LP-Wert nur in 1 von 40 Netzen gleich dem Optimum, und die Rangfolge von Add und Drop kehrt sich um.
• Dual Ascent: mit vereinfachter Anpassung, nicht Erlenkotters volle DUALOC-Anpassung.
• Aufwand: „bewertete Nachbarn“ sind eine Zählung, keine Uhr; sie gewichtet jede Bewertung gleich, obwohl eine Bewertung mit der Zahl der offenen Standorte teurer wird.

Quellen

• Erlenkotter, D. (1978): A Dual-Based Procedure for Uncapacitated Facility Location. Operations Research 26(6), 992–1009.
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/standortplanung-demo.

Die genannte Arbeit wurde für diese Seite nicht nachgeschlagen; die Angabe zu Erlenkotter (1978) stammt aus der README der Demo, Zeitschrift und Seitenzahlen sind aus dem Gedächtnis ergänzt.