Zum Inhalt springen

Warehouse Location Problem

aus Wikipedia, der freien Enzyklopädie

Das Warehouse Location Problem (WLP), auch als Uncapacitated Facility Location Problem (UFLP) oder Simple Plant Location Problem (SPLP) bekannt, ist ein diskretes Standortproblem, das vor allem in der Logistik auftritt. Dabei stehen mehrere mögliche Standorte für ein oder mehrere Lagerhäuser, von denen verschiedene Kunden zu beliefern sind. Die Standorte der Kunden und die von ihnen nachgefragten Warenmengen sind dabei schon bekannt. Gefragt wird danach, an welchen der Standorte man Lager errichten sollte. Bei vielen regional verteilten Lagern sind die Transportkosten im Allgemeinen geringer, da die Entfernungen zu den Kunden kürzer sind. Dafür sind die Kosten für den Bau dieser Lager hoch. Bei wenigen Lagern (im Extremfall nur einem) verhält es sich genau andersherum. 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 <math>I=\{1,\ldots,n\}</math> an Kunden mit einem Gut zu versorgen. Dazu können aus einer Menge von möglichen Standorten, Lager (engl. Warehouse) eröffnet werden. Sei <math>J=\{1,\ldots,m\}</math> diese Menge. Das Eröffnen eines Standorts <math>j</math> hat gewisse Fixkosten <math>f_j</math> zur Folge. Die Kosten der Belieferung von Kunde <math>i</math> durch Standort <math>j</math> können durch eine Kostenmatrix dargestellt werden. <math>c_{ij}</math> sind dabei die Kosten des Transports von <math>j</math> nach <math>i</math>.

Dies kann mit einer zu minimierenden Zielfunktion und ihren Nebenbedingungen modelliert werden. Zu beachten ist, dass <math>x_{ij}</math> als Gewichtungsfaktor zwischen 0 und 1 liegt und angibt, zu welchem Anteil der Kunde <math>i</math> durch den Standort <math>j</math> versorgt wird, während <math>y_j</math> eine Binärvariabe darstellt, die angibt, ob das Lager <math>j</math> überhaupt benötigt wird.

Dann ist der Ausdruck

<math>\sum_{i=1}^n \sum_{j=1}^m c_{ij} x_{ij} + \sum_{j=1}^m f_j y_j</math>

zu minimieren unter den Nebenbedingungen:

<math>\forall i \in I \colon \quad\quad \sum_{j=1}^m x_{ij} = 1</math>
<math>\forall i \in I \quad \forall j \in J \colon \quad\quad 0 \le x_{ij} \le y_j \in \{0,1\}</math>

Lösungsansätze

Das Problem kann mit Hilfe von Methoden des Operations Research gelöst werden. Dazu zählen 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. Bereits für die Entscheidung, welche Lager eröffnet werden sollen, gibt es <math>2^m-1</math> mögliche Teilmengen (denn man braucht mindestens ein Lager). Sofern mehr als ein Lager eingerichtet wird, muss zusätzlich für jeden Kunden festgelegt werden, zu welchen Anteilen er aus welchem Lager versorgt wird. Prinzipiell eröffnet dies unendlich viele Möglichkeiten, sodass eine vollständige Auflistung nicht möglich ist, allerdings kann auch <math>x_{ij} \in \{0,1\}</math> gewählt werden, indem man jeden Kunden aus dem Lager mit den geringsten Transportkosten versorgt.

Der Einsatz von Branch-and-Bound-Algorithmen (beispielsweise DuaLoc von Erlenkotter)<ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:Jens Lindemann|Jens Lindemann: }}{{#if:|{{#if:Standortplanung international agierender Unternehmen|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Standortplanung international agierender Unternehmen}}]{{#if:PDF; 2,6 MB| (PDF; 2,6 MB)}}{{#if:Dissertation an der Universität Hamburg| Dissertation an der Universität Hamburg{{#invoke:Vorlage:Internetquelle|Endpunkt|titel=Dissertation an der Universität Hamburg}}}}}}|{{#if:https://ediss.sub.uni-hamburg.de/bitstream/ediss/1501/1/dissertation.pdf%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Standortplanung international agierender Unternehmen}}}}|[{{#invoke:URLutil|getNormalized|1=https://ediss.sub.uni-hamburg.de/bitstream/ediss/1501/1/dissertation.pdf}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Standortplanung international agierender Unternehmen}}}}]}}{{#if:PDF; 2,6 MB| (PDF; 2,6 MB{{#if:Dissertation an der Universität Hamburguni-hamburg.de2006-09-09{{#if: 2024-01-22 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}} 

          | )
          | {{#if:{{#ifeq:de|de||{{#if:|1}}}}| ; 
              | )}}}}}}{{#if:Dissertation an der Universität Hamburg| Dissertation an der Universität Hamburg{{#invoke:Vorlage:Internetquelle|Endpunkt|titel=Dissertation an der Universität Hamburg}}}}}}}}{{#if:https://ediss.sub.uni-hamburg.de/bitstream/ediss/1501/1/dissertation.pdf%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://ediss.sub.uni-hamburg.de/bitstream/ediss/1501/1/dissertation.pdf}}%7C%7C}}}}{{#if:Standortplanung international agierender Unternehmen|{{#if:{{#invoke:WLink|isValidLinktext|1=Standortplanung international agierender Unternehmen|lines=0}}||}}}}{{#if: uni-hamburg.de| In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=uni-hamburg.de}}}}{{#if: | {{{hrsg}}}{{#if: 2006-09-09|,|{{#if: 2024-01-22 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: 2006-09-09| {{#if:{{#invoke:DateTime|format|2006-09-09|noerror=1}}
            |{{#invoke:DateTime|format|2006-09-09|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=2006-09-09|class=Zitationswartung}} }}{{#if: |,|{{#if: 2024-01-22 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2024-01-22 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:2006-09-09|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:1885031||(?)}}}}}}{{#if: 2024-01-22|;}}}}{{#if: 2024-01-22| {{#if:2006-09-09{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2024-01-22 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2024-01-22|class=Zitationswartung}} }} {{#invoke:DateTime|format|2024-01-22|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:de|de||{{#if:|1}}}}|{{#if:Dissertation an der Universität Hamburguni-hamburg.de2006-09-09{{#if: 2024-01-22 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if:PDF; 2,6 MB | |  (}}
       }}{{#ifeq:{{#if:de|de|de}}|de||
          {{#invoke:Multilingual|format|{{{sprache}}}|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: 2006-09-09{{#if: 2024-01-22 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if: 

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}} 

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch: 

   |0|=Vorlage:Toter Link/Core{{#if: https://ediss.sub.uni-hamburg.de/bitstream/ediss/1501/1/dissertation.pdf
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://ediss.sub.uni-hamburg.de/bitstream/ediss/1501/1/dissertation.pdf
      | {{#if:{{#invoke:URLutil|isWebURL|https://ediss.sub.uni-hamburg.de/bitstream/ediss/1501/1/dissertation.pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://ediss.sub.uni-hamburg.de/bitstream/ediss/1501/1/dissertation.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://ediss.sub.uni-hamburg.de/bitstream/ediss/1501/1/dissertation.pdf
       | {{#if:{{#invoke:URLutil|isWebURL|https://ediss.sub.uni-hamburg.de/bitstream/ediss/1501/1/dissertation.pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://ediss.sub.uni-hamburg.de/bitstream/ediss/1501/1/dissertation.pdf }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: https://ediss.sub.uni-hamburg.de/bitstream/ediss/1501/1/dissertation.pdf
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://ediss.sub.uni-hamburg.de/bitstream/ediss/1501/1/dissertation.pdf
      | {{#if:{{#invoke:URLutil|isWebURL|https://ediss.sub.uni-hamburg.de/bitstream/ediss/1501/1/dissertation.pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://ediss.sub.uni-hamburg.de/bitstream/ediss/1501/1/dissertation.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://ediss.sub.uni-hamburg.de/bitstream/ediss/1501/1/dissertation.pdf
       | {{#if:{{#invoke:URLutil|isWebURL|https://ediss.sub.uni-hamburg.de/bitstream/ediss/1501/1/dissertation.pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://ediss.sub.uni-hamburg.de/bitstream/ediss/1501/1/dissertation.pdf }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref> ist eine häufig verwendete Lösungsmethode. Diese arbeiten mit Hilfe eines Entscheidungsbaums und können zumindest 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. Einfache Beispiele stellen der ADD- und der DROP-Algorithmus (beides Greedy-Algorithmen) dar, mit deren Hilfe eine erste Lösung für das WLP gefunden werden kann. Häufig werden diese beiden Verfahren in Kombination angewendet.

Beispiel

Ein Unternehmen hat drei mögliche Standorte für ein Lager ausgemacht.

Die Kostenmatrix <math>c_{ij}</math> betrage: <math>\begin{pmatrix} 0 & 2 & 3 \\ 4 & 0 & 3 \\ 2 & 3 & 0 \end{pmatrix}</math>

Die Fixkosten seien <math>f_1 = 10</math>, <math>f_2 = 12</math> und <math>f_3 = 8</math>.

Diese Daten können folgendermaßen interpretiert werden: Die Belieferung von Kunde <math>i</math> durch Standort <math>j</math> mit <math>i = j</math> erzeugt 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 <math>F = 10 + 12 + 8 = 30</math> 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 ist.

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

<references />

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Warehouse_Location_Problem&oldid=1885031“