Home

Diskretes Standortproblem

Diskretes Standortproblem

Das diskrete kapazitierte Standortproblem besteht darin, aus einer Menge bekannter potentieller Standorte für Produktionsstätten mit beschränkten Kapazitäten diejenigen Standorte auszuwählen, von denen aus eine Menge von Nachfrageorten (Bedarfszentren) so beliefert werden kann, daß die Summe aus Fixkosten und Transportkosten minimiert wird. Zur Berechnung der Transportkosten wird auf eine Matrix zurückgegriffen, in der die Kosten pro Mengeneinheit zwischen allen potentiellen Standorten $i$ und allen Nachfrageorten $j$ zusammengefaßt sind.

Die Lösung dieses Problems beinhaltet zwei Teilprobleme:

  1.  Standortauswahl: Dies ist eine Ja/Nein-Entscheidung für jeden potentiellen Standort.
  2.  Transportproblem: Bestimmung der transportkostenminimalen Transportmengen zwischen den (ausgewählten) Standorten und den Nachfrageorten.

Die Lösung des Teilproblems (2.) hat einen Einfluß auf die Lösung des Teilproblems (1.) (und umgekehrt). Problem (1.) ist ein schwieriges kombinatorisches Problem, wobei für jede Lösungsalternative, d.h. für jeden Kombination von ausgewählten Standorten, das daraus resultierende Teilproblem (2.) gelöst werden muß.

In diesem Modul kann sowohl das Problem (2.) für manuell ausgewählte Standorte als auch das Problem (1.) der Auswahl der optimalen Standortkombination gelöst werden.

A. Dateneingabe

Sämtliche Daten (Transportkosten, Kapazitäten, Fixkosten, Nachfragemengen) werden in der Eingabetabelle festgelegt. Die editierbaren Tabellenzonen werden nach Auswahl der Anzahl Standorte und der Anzahl Bedarfszentren aufgebaut. Das sieht dann so aus:

Video

In der "0 oder 1"-Spalte kann man auswählen, welche potentiellen Standorte als Angebotsorte in ein Transportproblem aufgenommen werden sollen.

Ist die Option "Landkarte" ausgeschaltet, dann werden standardisierte Positionen der potentiellen Standorte und der Nachfrager angenommen und in einer einfachen Graphik angezeigt (siehe obiges Bild).

Ist die Option "Landkarte" angeschaltet, dann werden die potentiellen Standorte und die Nachfrageorte räumlich auf einer gedachten Landkarte angeordnet. Mit dem Graphen-Editor können die Positionen aller Orte dann durch Anklicken und Ziehen mit der Maus verändert werden. Die Entfernungen zwischen allen Orten werden manuell eingegeben, indem man sie durch einen Rechtsklick auf einen Pfeil oder im Hauptfenster direkt in der Eingabetabelle editiert. Die Landkartendarstellung dient nur zur besseren Veranschaulichung der Transportströme in der Lösung. 

Ist die Option "Landkarte" angeschaltet, dann sieht das Bild so aus:

In dem betrachteten Standortmodell wird davon ausgegangen, daß es nur potentielle Standorte (in diesen können Pfeile starten) und Nachfrageorte (in diesen können Pfeile enden) gibt. Stimmt ein potentialler Standort mit einem Nachfrageort überein, daß muß das in dem betrachteten Optimierungsproblem durch zwei Orte (ein potentieller Standort und ein Nachfrageort) und einem Verbindungspfeil mit den Transportkosten 0 abgebildet werden.

Knoten und Pfeile im Graphen können durch einen Rechtsklick mit der Maus editiert werden. Die geänderten Daten werden übernommen, wenn man und das "X" mit dem roten Hintergrund klickt.

Nach der Positionierung der Orte im Graphen-Editor und dem Rücksprung in das Hauptfenster können alle Daten (z.B. Kapazitäten, Kosten, etc.) bei Bedarf editiert werden. Auch die Bezeichungen der Orte sind editierbar.

Speicherung, Dateiformate:

Wenn die Option "Virtuelle Landkarte" eingeschaltet ist, dann werden die Daten in einer XML-Datei gespeichert, die auch Angaben für die Landkartendarstellung enthält.

Ist die Option "Virtuelle Landkarte" ausgeschaltet, dan werden die Daten in einer Textdatei (*.sfl) gespeichert und gelesen.

B. Problemlösung

1. Bestimmung der minimalen Transportkosten für eine gegebene Standortkombination

Hier wird nicht das kombinatorische Standortproblem optimal gelöst, sondern nur das mit einer Standortkombination verbundene klassische Transportproblem. Diese Option soll zeigen, welchen Einfluß die Festlegung von Standorten auf die daraus resultierenden Transportmengen und -kosten hat.

Durch Setzen eines Wertes 0 oder 1 in der Spalte "0 oder 1" (entspricht einer Binärvariablen im mathematischen Optimierungsmodell) kann der betreffende Standort geöffnet (1) oder geschlossen (0) werden. Für die so definierte Standortkombination wird dann durch den Button "Berechnen" das resultierende klassische Transportproblem zur Bestimmung der minimalen Transportkosten für die gegebene Standortkombination gelöst.

Für die Berechnung der Gesamtkosten werden die Fixkosten aller gewählten Standorte berücksichtigt, die auch tatsächlich genutzt werden, da von ihnen Transportströme ausgehen.

Alle Zahlenangaben müssen ganzzahlig sein.

2. Bestimmung der minimalen Gesamtkosten (exakte Lösung des Standortproblems)

Hier gibt es mehrere Möglichkeiten: 

a) Online-Optimierung mit dem Neos-Server und Gurobi

Man kann für jedes Problem auch die optimale Lösung bestimmen lassen, indem man die AMPL-Schnittstelle des online verfügbaren Neos-Servers nutzt. Im Produktions-Management-Trainer wählt man unter Optionen -> AMPL-Datei (Neos) erzeugen. Es erscheint dann ein Dateiauswahlfenster, in dem man den Namen der zu erzeugenden AMPL-Dateien festlegt. Hat man z.B. "SPLP" angegeben, dann werden die AMPL-Dateien SPLP.MOD, SPLP.DAT und SPLP.RUN erzeugt. Als nächstes öffnet man die folgende Internet-Seite in einem Browser:

https://neos-server.org/neos/solvers/milp:Gurobi/AMPL.html

Auf dieser Seite sind in der "Web Submission Form" die Modelldatei (SPLP.MOD), die Datendatei (SPLP.DAT) und die Kommandodatei (SPLP.RUN) anzugeben. Dann betätigt man den Button "Submit to Neos" und nach einiger Zeit wird die optimale Lösung des Problems angezeigt.

b) Optimierung auf dem lokalen PC mit der Studentenversion von AMPL und CPLEX

Unter https://ampl.com/try-ampl/download-a-free-demo/#windows kann man die Studentenversion von AMPL herunterladen: entweder ampl.mswin32.zip oder ampl.mswin64.zip.

In dieser ZIP-Datei befindet sich ein Unterverzeichnis, das auf den PC kopiert werden muß. Im Produktions-Management-Trainer wählt man die Option AMPL-Datei (lokal) erzeugen. Es erscheint ein Dateiauswahldialog, in dem man das AMPL-Verzeichnis angeben sollte. In diesem Verzeichnis startet man dann die Datei "ampl.exe" und gibt man den Befehl "include SPLP.run;" ein. Dieser Befehl startet die Lösung des Problems. Die Ergebnisse werden in der Datei SPLP.AUS gespeichert.

c) Optimierung auf dem lokalen PC mit GAMS

Unter https://ampl.com/try-ampl/download-a-free-demo/#windows kann man die Studentenversion von GAMS herunterladen. Ist GAMS auf dem Rechner installiert, dann kann mit dem Menüpunkt "GAMS-Datei erzeugen" für das aktuell betrachtete Problem das GAMS-Modell in einer Datei, z.B. "clsp.gms", gespeichert werden. Diese Datei kopiert man dann in das GAMS-Arbeitsverzeichnis (...\Documents\GAMS\Studio\workspace\) und löst die Probleminstanz mit GAMS. Mit dem Menüpunkt "GAMS-Lösung importieren" kann dann die Lösungsdatei, z.B. "clsp.out" eingelesen werden. Dabei ist darauf zu achten, daß vor dem Importieren die im PMT-Modul geladenen Daten den Beispiels nicht verändert werden.

d) Nur für Python-Nutzer: Optimierung mit Python auf dem lokalen PC (Voraussetzung: Installiertes Python und Python-MIP)

Python-Menü

Wählt man den letzten Menüpunkt "Optimierung mit Python-MIP aus" aus, dann wird das mathematische Optimierungsmodell in einer für Python-MIP lesbaren Form erzeugt und gelöst. Die optimale Lösung wird dann wie üblich angezeigt.

Falls Python nicht installiert ist, dann wird der letzte Menüpunkt nicht angezeigt.

Für Beispiel 1 könnte die Optimierung mit Python wie folgt aussehen. Zunächst bestimmen wir die Transportmengen - und kosten, wenn alle Standorte gewählt werden.

Nun bestimmen wir die optimale Lösung mit Hilfe von Python-MIP:

Symbole:

b(i) Kapazität des potentiellen Standortes i
d(j) Nachfragemenge des Bedarfszentrums j
c(i,j) Transportkosten pro Mengeneinheit von Standort i zum Abnehmerzentrum j
f(i) Fixkosten des potentiellen Standortes i

Literatur:

- Günther/Tempelmeier (2020a)

Datenschutz | © 2021 POM Prof. Tempelmeier GmbH | Imprint