Warehouse Location Problem

Das Warehouse Location Problem (WLP), auch als Uncapacitated Facility Location Problem (UFLP) oder Simple Plant Location Problem (SPLP) bekannt, beschreibt ein diskretes Standortproblem, das vor allem in der Logistik auftritt. Die mathematische Modellierung ermöglicht eine Lösung durch exakte Verfahren oder eine heuristische Lösungssuche.

Grundannahmen

Im einfachsten Fall gilt es zu Beginn einer Periode eine Menge an Kunden I={1,...n} mit einem Gut zu versorgen. Dazu können aus einer Menge von möglichen Standorten, Lager (engl. Warehouse) eröffnet werden. Sei J={1,...,m} diese Menge. Das Eröffnen eines Standorts hat gewisse Fixkosten f_j zur Folge. Die Kosten der Belieferung von Kunde i durch Standort j können durch eine Kostenmatrix dargestellt werden. c_ij sind dabei die Kosten des Transports von j nach i.

Dies kann mit einer zu minimierenden Zielfunktion und ihren Nebenbedingungen modelliert werden. Zu beachten ist, dass x_ij als Gewichtungsfaktor zwischen 0 und 1 liegt, während y_j eine Binärvariabe darstellt.

min $\sum_{i=1}^n \sum_{j=1}^m c_{ij} x_{ij} + \sum_{j=1}^m f_j y_j$

udN.

$\sum_{j=1}^m x_{ij} = 1 \qquad \forall i$

$x_{ij} \le y_j$

$x_{ij} \ge 0 \quad y_j \in \{0,1\}$

Lösungsansätze

Das Problem kann mit Hilfe von OR-Methoden gelöst werden. Dazu zählt zum einen Enumeration (beispielsweise durch Branch-and-Bound) oder der Einsatz von Heuristiken zur Bestimmung einer nicht unbedingt optimalen (Näherungs-)Lösung.

Das WLP ist NP-Schwer. Eine vollständige Enumeration liefert $\sum_{j=1}^m \binom n j = 2^n$ mögliche Teilmengen.

Der Einsatz von Branch-and-Bound Algorithmen (beispielsweise DuaLoc von Erlenkotter ^[1]) ist eine häufig verwendete Lösungsmethode. Diese arbeiten mit Hilfe eines Entscheidungsbaums und können unter günstigen(!) Umständen sehr schnell die beste Lösung ermitteln.

Eine heuristische Herangehensweise wird nicht zwangsläufig die optimale Lösung finden. Dennoch wird sie oft bevorzugt, da sie wesentlich schneller arbeitet. Ein einfaches Beispiel stellt der Greedy-Algorithmus dar, mit dessen Hilfe eine erste Lösung für das WLP gefunden werden kann.

Beispiel

Eine Firma hat drei mögliche Standorte für ein Lager ausgemacht.

Die Kostenmatrix c_ij betrage: $\begin{pmatrix} 0 & 2 & 3 \\ 4 & 0 & 3 \\ 2 & 3 & 0 \end{pmatrix}$

Mit Fixkosten von f₁:10 , f₂:12 und f₃:8

Interpretation: Die Belieferung von Kunde i durch Standort j, mit i=j, erzeugt in diesem Fall keine Transportkosten. Möglicherweise sind Lager und Kunde in diesem Fall am selben Ort. Die Eröffnung von drei Lagerhäusern ist dennoch nicht optimal, da die Fixkosten F = 10 + 12 + 8 = 30 betragen würden. In diesem einfachen Beispiel wäre es optimal Standort 3 auszuwählen, da die Summe der anfallenden Transportkosten (5) und der Fixkosten (8) für dieses Problem minimal sind.

Literatur

• Barahona, Chudak: Solving Large Scale Uncapacitated Location Problems, 2005
• Domschke, Drexl: Logistik: Standorte, 1996
• Love, Morris, Wesolowsky: Facilities Location: Models and Methods, 1988

Einzelnachweise

1. ↑ Jens Lindemann: Dissertation zum Thema Standortplanung. 9. September 2006, abgerufen am 3. Februar 2010.