Durchführung der Transportoptimierung mit verschiedenen Verfahren

Inhaltsverzeichnis

1. Die Transportplanung
1.1 Das klassische Transportproblem
1.2 Modellannahmen

2. Die Verfahren der Transportoptimierung
2.1 Das Nordwest – Ecken – Verfahren
2.2 Das Matrixminimumverfahren oder Methode des kleinsten Elements
2.3 Das Vogelsche Approximationsverfahren
2.4 Das Stepping – Stone – Verfahren
2.5 Das MODI – Verfahren
2.6 Der Simplexalgorithmus
2.7 Weitere Verfahren

3. Beeinträchtigungen durch gesperrte Strecken

4. Beurteilung der Verfahren

Anhangsverzeichnis

Darstellungsverzeichnis

Literaturverzeichnis

1. Die Transportplanung

Das Kernproblem jeder Transportplanung ist in jedem Unternehmen mit verschiedenen Produktions- und Verkaufsstätten^[1] die Verteilung der produzierten Einheiten in den einzelnen Verkaufsorten. Es ist festzulegen, welcher Produktionsstandort 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.^[2] 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 Koordinationsaufwand, 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 Transport 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:

Abbildung in dieser Leseprobe nicht enthalten

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.).^[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.

2. Die Verfahren der Transportoptimierung

Das klassische Transportproblem, wie unter 1.1 beschrieben, hat immer mindestens eine optimale Lösung.^[6] 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:

Abbildung in dieser Leseprobe nicht enthalten

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 cij stellen den Aufwand pro Mengeneinheit dar. Die Nachfrage bij ist in der untersten Zeile der Spalte abgetragen, die produzierte Menge aij 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:

Abbildung in dieser Leseprobe nicht enthalten

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

Abbildung in dieser Leseprobe nicht enthalten

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

Abbildung in dieser Leseprobe nicht enthalten

weiterhin ist die Nichtnegativitätsbedingung aufzustellen:

Abbildung in dieser Leseprobe nicht enthalten

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.^[9] Ausgehend von diesem Punkt werden die Felder mit der maximal zulässigen Transportmenge belegt. In die Nordwest – Ecke ist das Minimum aus a1 und b1 einzutragen. Hierbei dürfen die Angebots- und Bedarfsfunktionen (sämtliche Nebenbedingungen) nicht verletzt werden.

Nach Belegung der linken oberen Ecke x11 mit der maximalen Nachfrage (4), erfolgt eine Belegung der Zellen x21 und x31 mit 0. Somit kann im ersten Schritt die 1. Spalte zur Vereinfachung der Rechnung gestrichen werden. Im zweiten Schritt wird die Zelle x12 mit dem Maximalbedarf (3) belegt und es werden die Zellen x22 und x32 mit 0 belegt. Da das Maximalangebot der ersten Zeile noch nicht erreicht ist, wird x13 mit 2 belegt. Das Maximalangebot ist jetzt mit 9 erreicht, daher wird x14 mit 0 besetzt. Nun wird x23 mit der Nachfrage, die noch realisiert werden kann, belegt (6), x33 ist ebenfalls mit 0 zu bestücken. X24 wird mit dem noch zu realisierenden Angebot vervollständigt (3), somit ist das Maximalangebot mit 9 erreicht. X34 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 Transportmenge unabhängig von den Transportkosten zugeordnet wird. Daher ist 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:

Abbildung in dieser Leseprobe nicht enthalten

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

Quelle: eigene Darstellung

Der Gesamtaufwand der Kosten beträgt 138 Geldeinheiten.^[12] 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 Einheitstransportkosten cij macht, wird das Verfahren des Matrixminimums nötig. Es wird nach dem Element in der Matrix gesucht, das die kleinsten (niedrigsten) Transportkosten 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 x31 mit 2 belegt. Somit sind x32, x33 und x34 mit 0 zu belegen, da das Maximalangebot von 2 in Riyadh erreicht ist. Im zweiten Schritt ist x24 mit dem vollen Bedarf (5) zu belegen, die Zellen x14 und x34 sind ebenfalls mit 0 zu besetzen. Aus den übrigen Feldern wird wieder das Minimum ausgewählt und mit der Nachfrage besetzt (x13 wird mit 8 belegt, x23 und x33 mit 0.). Dann wird x21 mit 2 belegt, die maximale Nachfrage ist mit 4 erreicht. X12 wird mit 1 belegt, da dann das maximale Angebot aus Jeddah mit 9 erreicht wird. Jetzt wird x22, 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:

Abbildung in dieser Leseprobe nicht enthalten

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 x22 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.^[15] Im nächsten Schritt erfolgt die Zuordnung im günstigsten Feld der Zeile oder Spalte, die die größte Differenz aufweist, x13 wird mit 8 belegt.^[16] Folglich sind x23 und x33 mit 0 zu besetzen. In der sich ergebenden Restmatrix wird wieder nach der größten Differenz gesucht, x12 wird mit 1 besetzt, da das Angebot aus Jeddah jetzt voll ausgeschöpft ist. X11 und x14 sind mit Null zu belegen. Dann wird x32 mit 2 belegt, das Angebot ist jetzt erreicht, deshalb sind x22, x31 und x34 durch Null zu ersetzen. X21 wird nun mit 4 belegt, da der Bedarf dann befriedigt ist, somit wird x24 mit 5 belegt, damit das Angebot voll ausgeschöpft wird.^[17]

Eine Lösung ist nun erkennbar:

[...]

^[1] Die Begriffe Verkaufsstätte und Abnehmerzentrum werden in dieser Arbeit synonym verwandt, ebenso die Begriffe Produktionsstätte und Produktionsstandort

^[2] Vgl. Günther/Tempelmeier, Produktion und Logistik, 3. überarb. U. erw. Auflage, 1997, S. 253

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

^[4] Vgl. Burchert/Hering/Rollberg, Logistik, Aufgaben und Lösungen, 2000, S. 235

^[5] Vgl. Günther/Tempelmeier, Produktion und Logistik, 3. überarb. U. erw. Auflage, 1997, S. 255

^[6] Vgl. Hellmann/Richter, Produktionstransportoptimierung, 1. Auflage, 1988, S. 44

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

^[8] Vgl. Burchert/Hering/Rollberg, Logistik, Aufgaben und Lösungen, 2000, S. 235

^[9] Vgl. Gohout, Operations Research, 2000, S. 90

^[10] Die vollständige Rechnung finden Sie im Anhang 1.

^[11] Vgl. Burchert/Hering/Rollberg, Logistik, Aufgaben und Lösungen, 2000, S. 235

^[12] Die Gesamtkosten werden durch Multiplikation der Transportmengen mit den vorher angegebenen Kosten cij und anschließende Addition errechnet.

^[13] Vgl. Gohout, Operations Research, 2000, S. 92

^[14] Die vollständige Rechnung finden Sie im Anhang 2.

^[15] Vgl. Hillier/Lieberman, Operations Research, Einführung, 5. Auflage, 1997, S. 188

^[16] Vgl. Burchert/Hering/Rollberg, Logistik, Aufgaben und Lösungen, 2000, S. 238

^[17] Die vollständige Rechnung finden Sie im Anhang 3.