Inhaltsverzeichnis II

Inhaltsverzeichnis   

1.  Die Transportplanung  1

1.1  Das klassische Transportproblem  1

1.2  Modellannahmen.  2

2.  Die Verfahren der Transportoptimierung.  3

2.1  Das Nordwest - Ecken - Verfahren  4

2.2  Das Matrixminimumverfahren oder Methode des kleinsten Elements.  5

2.3  Das Vogelsche Approximationsverfahren.  6

2.4  Das Stepping - Stone - Verfahren.  7

2.5  Das MODI - Verfahren  9

2.6  Der Simplexalgorithmus  11

2.7  Weitere Verfahren  13

3.  Beeinträchtigungen durch gesperrte Strecken.  14

4.  Beurteilung der Verfahren.  16

Anhangsverzeichnis. 17   

Darstellungsverzeichnis   28

Literaturverzeichnis   29

Durchführung der Transportoptimierung mit verschiedenen Verfahren 1

1. Die Transportplanung

Das Kernproblem jeder Transportplanung ist in jedem Unternehmen mit verschiedenen Produktions- und Verkaufsstätten ¹ die Verteilung der produzierten Einheiten in den einzelnen Verkaufsorten. Es ist festzulegen, welcher Produkti-onsstandort welches Abnehmerzentrum mit welcher Menge des Produkts beliefert.

Im Mittelpunkt der Transportplanung steht die Wahl der Transportwege und die Bestimmung der jeweiligen Transportmengen, aus denen dann die einzelnen Touren entstehen. ² Bei der Tourenplanung sind Entscheidungen über die aggregierten Transportströme zu treffen.

Eine Koordination der Transportströme ist nach zwei Kriterien möglich und mit der Planung vorzunehmen. Als erstes kann eine feste Zuordnung von Abnehmerzentren zu Produktionsstätten erfolgen, was zu geringem Koordinations-aufwand, aber nicht zu minimalen Transportkosten führt. Eine zweite Zuordnung kann in Abhängigkeit von der spezifischen Bedarfssituation der Abnehmerzentren erfolgen, hier steht die transportkostenminimale Belieferung der Verkaufsstätten im Vordergrund. 3

Ausgangspunkt meiner Ausführungen wird eine beliebige Zuordnung der Abnehmerzentren zu den Produktionsstandorten sein. Das klassische Transportproblem lässt sich somit definieren.

1.1 Das klassische Transportproblem

Entscheidend beim klassischen Transportproblem sind die aufgestellten Ziel-und Nebenfunktionen. Als Zielfunktion ist der Aufwand der Kosten beim Trans-port der Mengeneinheiten zu minimieren. Die Nebenfunktionen definieren sich als beschränkte Lieferkapazitäten der Produktionsorte und eine Befriedigung der Bedarfsmengen in den Verkaufsstätten.

Das Modell Transport, welches sich nun aufstellen lässt, kann folgend als Gleichung dargestellt werden:

¹ Die Begriffe Verkaufsstätte und Abnehmerzentrum werden in dieser Arbeit synonym verwandt, ebenso die Begriffe Produktionsstätte und Produktionsstandort

² Vgl. Günther/Tempelmeier, Produktion und Logistik, 3. überarb. U. erw. Auflage, 1997, S. 253

³ Vgl. Günther/Tempelmeier, Produktion und Logistik, 3. überarb. U. erw. Auflage, 1997, S. 254

Durchführung der Transportoptimierung mit verschiedenen Verfahren 2

Minimiere 1.

I ∑ = = J 1,2, j b x 2. ...,

ij ij

= i 1

J ∑ = = ,..., I 1,2 i a x 3.

ij ij

= j 1

≥ 0 x 4.

ij

Die Zielfunktion wird hier durch eine Minimierung des Aufwands (1.) ausgedrückt, mit den Nebenbedingungen, dass der Abtransport aller gelagerten und produzierten Mengen (3.) erfolgt und ebenso die Deckung der Nachfrage gewährleistet wird (2.). Voraussetzung hierbei ist die Nichtnegativitätsbedingung (4.). ⁴ Zur Lösung des Problems stehen mehrere exakte Verfahren zur Verfügung, auf die ich im späteren Verlauf dieser Arbeit eingehen werde.

1.2 Modellannahmen

Das Modell Transport beruht auf wenigen wesentlichen Annahmen, die folgend genannt werden:

• Eine einperiodige Betrachtung,

• lediglich die Erfassung einer Produktart erfolgt,

• als entscheidungsrelevante Kosten werden nur die reinen Transportkosten betrachtet,

• ein linearer Kostenverlauf liegt vor, d.h. die Transportkosten je Mengeneinheit auf einem spezifischen Transportweg werden als konstant angenommen,

• eine beliebige Zuordnung von Produktions- und Verkaufsstätten ist möglich und

• es erfolgt keine Beschränkung streckenspezifischer Transportkapazitäten. 5

Diese Annahmen sind wichtig, um eine mathematische Lösung zu generieren. Alle in der vorliegenden Arbeit ausgeführten Verfahren beruhen auf diesen Restriktionen.

⁴ Vgl. Burchert/Hering/Rollberg, Logistik, Aufgaben und Lösungen, 2000, S. 235

⁵ Vgl. Günther/Tempelmeier, Produktion und Logistik, 3. überarb. U. erw. Auflage, 1997, S. 255

Durchführung der Transportoptimierung mit verschiedenen Verfahren 3

2. Die Verfahren der Transportoptimierung

Das klassische Transportproblem, wie unter 1.1 beschrieben, hat immer mindestens eine optimale Lösung. ⁶ Zur Darstellung und Lösung des Problems eignet sich die Form der Matrix am besten.

Im vorliegenden Fall (Zementproduktion in Arabien) lässt sich die Ausgangssituation wie folgt darstellen:

Tabelle 1: Ausgangsmatrix

Quelle: Vgl. Burchert/Hering/Rollberg, Logistik, Aufgaben und Lösungen, 2000, S. 234 Die in den Spalten unter den Städten eingetragenen Werte c ij stellen den Auf-wand pro Mengeneinheit dar. Die Nachfrage b ij ist in der untersten Zeile der Spalte abgetragen, die produzierte Menge a ij als maximale produzierbare Menge in der rechten Spalte. 7

Aus der Matrix lassen sich die Zielfunktion und die Nebenbedingungen herleiten:

die Zielfunktion, die später minimiert wird:

+ + + + + + + + + + + = 3x 11x 9x 1x 2x 13x 15x 3x 11x 3x 6x 6x Z

34 33 32 31 24 23 22 21 14 13 12 11

die Nebenbedingungen für die maximal lieferbare Menge aus den Produktions-orten Jeddah, Dammam und Riyadh:

= + + + 9 x x x x

14 13 12 11

= + + + 9 x x x x

24 23 22 21

= + + + 2 x x x x

34 33 32 31

und die Nebenbedingungen für die Bedarfsdeckung in den Verkaufsorten Riyadh, Abha, Medina und Jubail: 8

⁶ Vgl. Hellmann/Richter, Produktionstransportoptimierung, 1. Auflage, 1988, S. 44

⁷ Vgl. Aufzeichnungen aus dem Wahlfach Transportoptimierung, 3. Semester, WS 2000/2001, Dozent der Veranstaltung: Frau Mathäus

⁸ Vgl. Burchert/Hering/Rollberg, Logistik, Aufgaben und Lösungen, 2000, S. 235

Durchführung der Transportoptimierung mit verschiedenen Verfahren 4

+ + 4 x x x x

41 31 21 11

= + + + 3 x x x x

42 32 22 12

= + + + 8 x x x x

43 33 23 13

= + + + 5 x x x x

44 34 24 14

weiterhin ist die Nichtnegativitätsbedingung aufzustellen:

x ij ≥ . 0

Hierbei handelt es sich um ein geschlossenes Modell, bei dem der Bedarf dem Aufkommen an Zement vollkommen entspricht.

2.1 Das Nordwest - Ecken - Verfahren

Der in der Literatur als einfachster Startalgorithmus genannter ist der der Nordwest - Ecken - Regel (NWR). Ausgangspunkt ist die linke, obere Ecke der Ausgangsmatrix. ⁹ Ausgehend von diesem Punkt werden die Felder mit der maximal zulässigen Transportmenge belegt. In die Nordwest - Ecke ist das Minimum aus a 1 und b 1 einzutragen. Hierbei dürfen die Angebots- und Bedarfsfunktionen (sämtliche Nebenbedingungen) nicht verletzt werden.

Nach Belegung der linken oberen Ecke x 11 mit der maximalen Nachfrage (4), erfolgt eine Belegung der Zellen x 21 und x 31 mit 0. Somit kann im ersten Schritt die 1. Spalte zur Vereinfachung der Rechnung gestrichen werden. Im zweiten Schritt wird die Zelle x 12 mit dem Maximalbedarf (3) belegt und es werden die Zellen x 22 und x 32 mit 0 belegt. Da das Maximalangebot der ersten Zeile noch nicht erreicht ist, wird x 13 mit 2 belegt. Das Maximalangebot ist jetzt mit 9 erreicht, daher wird x 14 mit 0 besetzt. Nun wird x 23 mit der Nachfrage, die noch realisiert werden kann, belegt (6), x 33 ist ebenfalls mit 0 zu bestücken. X 24 wird mit dem noch zu realisierenden Angebot vervollständigt (3), somit ist das Maximalangebot mit 9 erreicht. X 34 kann nur noch mit 2 belegt werden, da nur noch diese lieferbare Menge zur Verfügung steht. 10

Jedoch ist diese Rechnung problematisch, da die maximal mögliche Trans-portmenge unabhängig von den Transportkosten zugeordnet wird. Daher ist

⁹ Vgl. Gohout, Operations Research, 2000, S. 90

¹⁰ Die vollständige Rechnung finden Sie im Anhang 1.

Durchführung der Transportoptimierung mit verschiedenen Verfahren 5

auch die ermittelte Lösung meist nicht optimal und es werden Verbesserungsverfahren nötig. 11

Die generierte Lösung ergibt sich wie folgt. Die Transportmengen sind mit:

= = = = = = angegeben. 2 x 3 x 6 x 2 x 3 x 4 x

34 24 23 13 12 11

Tabelle 2: Lösung der Nordwest - Ecken - Regel

Quelle: eigene Darstellung

Der Gesamtaufwand der Kosten beträgt 138 Geldeinheiten. ¹² Ein mögliches Verbesserungsverfahren ist das MODI - Verfahren, auf das ich im späteren Verlauf näher eingehe.

2.2 Das Matrixminimumverfahren oder Methode des kleinsten Elements

Da das Nordwest - Ecken - Verfahren keinen Gebrauch von den Einheitstrans-portkosten c ij macht, wird das Verfahren des Matrixminimums nötig. Es wird nach dem Element in der Matrix gesucht, das die kleinsten (niedrigsten) Trans-portkosten hat. Dieses Feld wird maximal belegt. Das Maximalangebot und die Maximalnachfrage finden auch hier Berücksichtigung. In weiteren Iterationsschritten werden die danach übrigen Matrixminima mit der maximalen noch möglichen Menge belegt. 13

Im ersten Schritt wird x 31 mit 2 belegt. Somit sind x 32 , x 33 und x 34 mit 0 zu belegen, da das Maximalangebot von 2 in Riyadh erreicht ist. Im zweiten Schritt ist x 24 mit dem vollen Bedarf (5) zu belegen, die Zellen x 14 und x 34 sind ebenfalls mit 0 zu besetzen. Aus den übrigen Feldern wird wieder das Minimum ausgewählt und mit der Nachfrage besetzt (x 13 wird mit 8 belegt, x 23 und x 33 mit 0.). Dann wird x 21 mit 2 belegt, die maximale Nachfrage ist mit 4 erreicht. X 12 wird mit 1 belegt, da dann das maximale Angebot aus Jeddah mit 9 erreicht wird.

¹¹ Vgl. Burchert/Hering/Rollberg, Logistik, Aufgaben und Lösungen, 2000, S. 235

¹² Die Gesamtkosten werden durch Multiplikation der Transportmengen mit den vorher angegebenen Kosten c ij und anschließende Addition errechnet.

¹³ Vgl. Gohout, Operations Research, 2000, S. 92

Durchführung der Transportoptimierung mit verschiedenen Verfahren 6

Jetzt wird x 22 , die Zelle mit den höchsten Transportkosten, mit 2 bestückt, damit der Bedarf gedeckt wird. 14

Als Lösung ergeben sich die folgenden Transportmengen:

= = = = = = . 2 x 5 x 2 x 2 x 8 x 1 x

31 24 22 21 13 12

Tabelle 3: Lösung des Matrixminimumverfahrens

Quelle: eigene Darstellung

Die Gesamtkosten sind mit 78 anzugeben. Diese Methode ist gegenüber der Nordwest - Ecken - Regel ein Fortschritt, bietet aber nur in den ersten Schritten kostengünstige Ansätze, in den folgenden Schritten werden ungünstige Zuteilungen getroffen, im Rechenbeispiel wird dies bei der Zelle x 22 erkennbar. Auch hier ist noch nicht die Optimallösung erreicht.

2.3 Das Vogelsche Approximationsverfahren

Diese Methode wurde nach dem englischen Wissenschaftler W. R. Vogel benannt, der sie entwickelte und in dem Buch „Mathematical Programming“ 1958 der Öffentlichkeit vorstellte. Bei der Vogelschen Approximationsmethode wird für jede betrachtete Zeile oder Spalte eine Kostenwertdifferenz berechnet, sie entspricht der Differenz zwischen dem kleinsten und dem nächstkleinsten Kostenwert der betrachteten Zeile oder Spalte. ¹⁵ Im nächsten Schritt erfolgt die Zu-ordnung im günstigsten Feld der Zeile oder Spalte, die die größte Differenz aufweist, x 13 wird mit 8 belegt. ¹⁶ Folglich sind x 23 und x 33 mit 0 zu besetzen. In der sich ergebenden Restmatrix wird wieder nach der größten Differenz gesucht, x 12 wird mit 1 besetzt, da das Angebot aus Jeddah jetzt voll ausgeschöpft ist. X 11 und x 14 sind mit Null zu belegen. Dann wird x 32 mit 2 belegt, das Angebot ist jetzt erreicht, deshalb sind x 22 , x 31 und x 34 durch Null zu ersetzen. X 21

¹⁴ Die vollständige Rechnung finden Sie im Anhang 2.

¹⁵ Vgl. Hillier/Lieberman, Operations Research, Einführung, 5. Auflage, 1997, S. 188

¹⁶ Vgl. Burchert/Hering/Rollberg, Logistik, Aufgaben und Lösungen, 2000, S. 238