Kurs:Einführung in Produktionsmanagement/Operative Planung/Logistik

Inhalt dieses Abschnittes sind zwei typische Arten von Logistikfragestellungen: Distributionslogistik und das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP).

Distributionslogistik

In der Distributionslogistik dreht sich alles um die Frage, wie etwas möglichst günstig von Ort A zu Ort B kommt. Dies beginnt schon bei der Frage, was wo im Hinblick auf den späteren Bestimmungsort produziert wird, geht über die Einrichtung von Distributionszentren in den Bereich der operativen Planung hinein und endet noch lange nicht bei der konkreten Streckenplanung. Dieser Bereich könnte allein einen ganzen Kurs füllen, deshalb beschränkt sich der Abschnitt hier lediglich auf einen kleinen Teilaspekt, für welchen einmal eine Heuristik und anschließend ein lineares Optimierungsmodell erstellt wird.

Dieser Aspekt betrifft eine Firma, die mehrere Werke besitzt, welche allesamt die gleiche Ware produzieren und gleichzeitig mehrere Kunden hat, welche diese Ware nachfragen. Die maximalen Produktionsmengen der Standorte sind ebenso gegeben, wie die Abnahmemengen der Kunden und die Kosten je Einheit für den Transport von jedem Werk zu jedem Kunden. Nun soll bestimmt werden, welches Werk an welchen Kunden wieviel liefert. Hierzu wird zunächst die sogenannte Vogel'sche Approximation verwendet.

Die Vogel'sche Approximation

Die Grundidee, die hinter der Vogel'schen Approximation steckt besteht darin, zuerst den Weg zu gehen, welcher, wenn man auf ihn verzichtet, die höchsten Kosten verursacht. Es wird also mit der relativen Verteuerung gearbeitet und nicht mit dem absoluten Preis.

Der Algorithmus der Vogel'schen Approximation ist der folgende:

1. Differenzbetrag des niedrigsten und zweitniedrigsten Eintrags jeder Zeile und Spalte ermitteln und den höchsten auswählen
2. in dieser Spalte bzw. Zeile so viel wie möglich beim niedrigsten Betrag transportieren
3. Felder, denen der Bedarf nun eindeutig zugeordnet werden kann, dementsprechend ausfüllen
4. mit Schritt 1 fortfahren, bis alle Bedarfe gedeckt sind

Beispiel zur Vogel'schen Approximation

Da dies recht abstrakt klingt hier ein Beispiel dazu:

	Stuttgart (0/50)	Hamburg (0/150)	München (0/100)
Frankfurt (0/100)	3	8	3
Berlin (0/200)	7	5	6

Dies ist die Ausgangstabelle, die erste Zahl hinter dem Ort gibt jeweils an, wieviel Bedarf bereits befriedigt bzw. wieviel Waren bereits versendet sind. Die zweite Zahl gibt jeweils den Bedarf bzw. die Maximalkapazität an. Die Zahlen in der Matrix stehen für die Transportkosten. Beispielsweise kostet also der Transport von Frankfurt nach Hamburg 8 Geldeinheiten.

Nun führen wir Schritt 1 des Algorithmus aus, in der Extra-Zeile und Spalte steht nun stets der Differenzbetrag zwischen dem niedrigsten und zweitniedrigsten Wert:

	Stuttgart (0/50)	Hamburg (0/150)	München (0/100)
Frankfurt (0/100)	3	8	3	0 (=3-3)
Berlin (0/200)	7	5	6	1 (=6-5)
	4 (=7-3)	3 (=8-5)	3 (=6-3)

Da es uns offensichtlich sehr teuer kommt von Berlin nach Stuttgart anstatt von Frankfurt nach Stuttgart zu transportieren, wählen wir Frankfurt-Stuttgart als unsere erste Strecke aus und transportieren möglichst viel auf dieser Strecke. Da in Stuttgart lediglich 50 Einheiten benötigt werden, ist dies unser Maximum (Schritt 2). Von Berlin nach Stuttgart wird dementsprechend nichts transportiert folglich ergibt sich eine Transportmenge von 0 für diese Strecke. Ab der folgenden Tabelle bezeichnen fett eingetragene Ziffern in der Distanzmatrix nun Transportmengen.

	Stuttgart (50/50)	Hamburg (0/150)	München (0/100)
Frankfurt (50/100)	50	8	3
Berlin (0/200)	0	5	6

Für das weitere Vorgehen brauchen nun mit Transportmengen gefüllte Felder nicht mehr beachtet werden. Wir fahren mit der soeben gegebenen Matrix nun mit Schritt 1 fort:

	Stuttgart (50/50)	Hamburg (0/150)	München (0/100)
Frankfurt (50/100)	50	8	3	5 (=8-3)
Berlin (0/200)	0	5	6	1 (=6-5)
	-	3 (=8-5)	3 (=6-3)

Durch den Wegfall des Bedarfes in Stuttgart wird es nun auf einmal sehr teuer, wenn der Transport von Frankfurt nach München nicht durchgeführt wird (Mehrkosten von 5). Dementsprechend transportieren wir auf dieser Strecke nun möglichst viel, also alles was in Frankfurt noch zur Verfügung steht - 50 Einheiten (Schritt 2). Daraus folgt folgende Tabelle:

	Stuttgart (50/50)	Hamburg (0/150)	München (50/100)
Frankfurt (100/100)	50	8	50
Berlin (0/200)	0	5	6

Hieraus ist nun gut zu erkennen, dass sich einige Strecken nun von allein ergeben: Zwischen Berlin und München müssen nun 50 Einheiten transportiert werden, um den Restbedarf von 50 Einheiten in München zu decken. Weiterhin kann nichts mehr von Frankfurt nach Hamburg transportiert werden, da die gesamte Produktion aus Frankfurt nun schon nach München und Stuttgart geht. Also ergibt sich zunächst folgende Tabelle:

	Stuttgart (50/50)	Hamburg (0/150)	München (100/100)
Frankfurt (100/100)	50	0	50
Berlin (50/200)	0	5	50

Nun bleibt gar nichts anderes mehr übrig, als den Bedarf von Hamburg durch einen Transport von 150 Einheiten aus Berlin zu befriedigen, und unsere Lösung sieht wie folgt aus:

	Stuttgart (50/50)	Hamburg (150/150)	München (100/100)
Frankfurt (100/100)	50	0	50
Berlin (200/200)	0	150	50

Überlegungen zum Algorithmus

Wenn der Algorithmus verstanden wurde, ist es empfehlenswert vor dem Weiterlesen über folgende Fragen nachzudenken:

• Welche Konsequenzen bei der Ausführung ergeben sich, wenn mehr produziert wird, als an Bedarf vorhanden ist?
• Was für Probleme können generell bei der Ausführung des Algorithmus' auftreten?
• Mit welchen Einschränkungen könnte ich zu kämpfen haben?
• Wozu könnte ich diese Lösungen, welche ja nicht zwangsläufig optimal sind, verwenden?

Im folgenden wollen wir uns jeder dieser Fragen etwas ausführlicher widmen.

Welche Konsequenzen bei der Ausführung ergeben sich, wenn mehr produziert wird, als an Bedarf vorhanden ist?

Dies ist ein relativ kleines Problem: Man stelle sich einfach vor, in Frankfurt würden insgesamt 500 Einheiten produziert werden. Dann hätte man im ersten Teil des letzten dritten Schrittes sicher nicht das Maximum von Frankfurt nach Hamburg transportiert, sondern ebenso wie bereits geschehen, die entsprechende Menge von München aus. Folglich ist in dem beschriebenen Fall lediglich darauf zu achten, dass vertikal die Reihen nicht im dritten Schritt gefüllt werden.

Was für Probleme können generell bei der Ausführung des Algorithmus' auftreten?

Zum einen wird nicht überprüft, ob der Bedarf überhaupt gedeckt werden kann. Dies scheint auf den ersten Blick nicht weiter wild zu sein, da es ja ganz schnell geht. Erweitert man den Algorithmus allerdings um das Verbot bestimmter Routen (Du darfst nicht von A nach B transportieren), kann es sehr schwierig werden, diese Überprüfung durchzuführen. Ein wesentlich komplizierter zu handhabendes Problem ist dagegen das Auftreten gleich hoher höchster Differenzbeträge. Hier gibt uns der Algorithmus keinen Hinweis darauf, wie weiter vorzugehen ist, und dieses Problem ist im Hinblick auf die beste Lösung auch nicht trivial zu lösen.

Mit welchen Einschränkungen könnte ich zu kämpfen haben?

Eine wichtige Einschränkung ist die Unmöglichkeit der Behandlung von Fixkosten. Wenn oben in Lastwagenladungen gezählt wurde, ist es kein Problem, wenn es aber nun nur Einzelgüter sind, auf jeden Lastwagen 100 Stück davon passen und je angefangenen Lastwagen signifikante Fixkosten auftreten, ist die Lösung auf einmal deutlich schlechter. Ein weiteres Problem ist der Ein-Güter-Fall - nur bei hinreichend großen Überkapazitäten liefert dieses Verfahren für den Mehrgüterfall noch akzeptabele Lösungen.

Wozu könnte ich diese Lösungen, welche ja nicht zwangsläufig optimal sind, verwenden?

Da wir im Anschluss ein Verfahren vorstellen werden, bei dem wir immer die optimale Lösung finden werden und eine Reihe der obigen Einschränkungen aufhebbar sind, hat diese Frage durchaus ihre Berechtigung. Hier muss zum einen beachtet werden, dass das Verfahren noch aus Zeiten stammt, in denen die Rechenleistung alles andere als unbegrenzt war (was allerdings keine Berechtigung dafür darstellt, es heute noch zu lehren). Viel wichtiger ist, dass man für den Fall, dass wenn man ganzzahlige Lösungen sucht auch mit modernen Rechnern bei einer hohen Anzahl von Orten schnell sehr lange Rechenzeiten bekommt. An dieser Stelle kann mit der Vogel'schen Approximation eine bereits gute obere Schranke gefunden werden, welche die eigentliche Optimierung unter Umständen radikal beschleunigen kann. Außerdem ist dieses Verfahren auch für andere Problemstellungen geeignet, bei denen sich das Aufstellen von Optimierungsmodellen als eventuell nur begrenzt sinnvoll erweist.

Zusammenfassung der Vor- und Nachteile

Vorteile

• relativ gute Lösung
• erfordert sehr wenig Rechenzeit (keine aufwendigen Matrixoperationen)
• ermöglicht schnelles Auffinden von zulässigen ganzzahligen Lösungen
• ist auch per Hand schnell durchführbar

Nachteile

• Lösung ist oftmals nicht optimal
• Algorithmus ist kaum sinnvoll um Fixkosten und nur schwierig um Mehr-Produkt-Fälle erweiterbar

Übungsaufgaben mit Lösungen

• bisher leider noch keine vorhanden

Solver für Vogel'sche Approximation

• folgt in Kürze

Modell zur Linearen Programmierung

Das oben beschriebene Problem lässt sich auch als ein lineares Programmierungsmodell umsetzen. Dies ist auch relativ simpel. Auf der rechten Seite befindet sich eine allgemeine Formulierung, auf der linken Seite das fertige Modell mit den Werten aus dem obigen Beispiel.

Indexmengen $i\in I=\lbrace$Frankfurt (F), Berlin (B)$\rbrace$ $j\in J=\lbrace$Stuttgart (S), Hamburg (H), Muenchen (M)$\rbrace$	Indexmengen $i\in I$ Produktionsorte $j\in J$ Abnahmezentren
Parameter in dieser Variante nicht nötig	Parameter $a_{i}$ Maximale Produktionsmenge in Produktionsort i $b_{j}$ nachgefragte Menge des Gutes in Abnahmeort j $c_{ij}$ Transportkosten je Stück für den Transport von i nach j
Entscheidungsvariablen $x_{ij}$ Transportmenge von i nach j	Entscheidungsvariablen $x_{ij}$ Transportmenge von i nach j
Zielfunktion ${\begin{matrix}min&&3x_{FS}+8x_{FH}+3x_{FM}\\&&+7x_{BS}+5x_{BH}+6x_{BM}\end{matrix}}$	Zielfunktion $min\quad \sum _{i\in I}\sum _{i\in I}c_{ij}\cdot x_{ij}$
Nebenbedingungen Einhaltung der maximalen Produktionsmengen $x_{FS}+x_{FH}+x_{FM}\leq 100$ $x_{BS}+x_{BH}+x_{BM}\leq 200$ Befriedigung des Bedarfs $x_{FS}+x_{BS}\geq 50$ $x_{FH}+x_{BH}\geq 150$ $x_{FM}+x_{BM}\geq 100$ Nicht-Negativität der Transportmengen $x_{FS},x_{FH},x_{FM},x_{BS},x_{BH},x_{BM}\geq 0$	Nebenbedingungen Einhaltung der maximalen Produktionsmengen $\sum _{j\in J}x_{ij}\leq a_{i}\qquad \forall i\in I$ Befriedigung des Bedarfs $\sum _{i\in I}x_{ij}\geq b_{j}\qquad \forall j\in J$ Nicht-Negativität der Transportmengen $x_{ij}\geq 0\qquad \forall i\in I,j\in J$

Das Problem des Handlungsreisenden

Das Problem des Handlungsreisenden ist eines der klassischen Probleme des Fachgebietes "Operations Research". Ein effizienter Algorithmus zur Lösung des Problems wird hier nicht vorgestellt werden, da dieses Problem jedoch ein in vielen Fällen sehr bedeutendes ist, soll es inhaltlich zumindest kurz umrissen werden. Ziel ist es eine Anzahl vorgegebener Orte auf dem kürzesten Wege nacheinander abzufahren und wieder zum Ausgangsort zurückzukehren. Diese Art von Problemen ist beispielsweise zu lösen, wenn bereits feststeht, dass ein Transporter bestimmte Waren an eine Kundengruppe liefern soll, deren Reihenfolge jedoch noch nicht feststeht.

Weiterführendes

• folgt