Ein genetischer Algorithmus für das 2-Ebenen Transportproblem

Inhaltsverzeichnis

Abbildungsverzeichnis

Abkürzungsverzeichnis

1 Einleitung

2 Transportprobleme
2.1 Einstufiges Transportproblem
2.2 Zweistufiges Transportproblem

3 Genetische Algorithmen
3.1 Funktionsweise von genetischen Algorithmen
3.2 Prioritätsbasierter genetischer Algorithmus
3.2.1 Dekodierungsalgorithmus
3.2.2 Kodierungsalgorithmus
3.2.3 2-Ebenen Transportproblem
3.3 Genetische Operatoren
3.3.1 Crossover
3.3.2 Mutation
3.3.3 Selektion

4 Zahlenbeispiele

5 Fazit

Literaturverzeichnis

Abbildungsverzeichnis

Abbildung 1: Transportproblem

Abbildung 2: Transshipment-Problem

Abbildung 3: Funktionsweise eines genetischen Algorithmus

Abbildung 4: Beispiel für Transportbaum und dessen Kodierung

Abbildung 5: Dekodierungsalgorithmus für die prioritätsbasierte Kodierung

Abbildung 6: Ablaufverfolgung der Dekodierungsprozedur

Abbildung 7: Kodierungsalgorithmus für den Transportbaum

Abbildung 8: Ablaufverfolgung der Kodierungsprozedur

Abbildung 9: Schaubild Chromosom, Transportbaum und Transportkosten

Abbildung 10: Dekodierungsprozedur von Chromosomen

Abbildung 11: Dekodierungsprozedur für das zweite Segment des Chromosomens

Abbildung 12: Dekodierungsprozedur für das erste Segment des Chromosomens

Abbildung 13: 1-Punkt Crossover

Abbildung 14: Schaubild des WMX-Operators

Abbildung 15: Pseudocode des WMX-Operators

Abbildung 16: Mutation

Abbildung 17: Schaubild einer Insert-Mutation

Abbildung 18: Schaubild einer Swap-Mutation

Abbildung 19: Pseudo-Code des prioritätsbasierten genetischen Algorithmus

Abbildung 20: Größe der Testprobleme

Abbildung 21: Rechenbetonte Ergebnisse der verschiedenen Kombinationen

Abbildung 22: Rechenbetonte Ergebnisse für st-GA und pb-GA

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung

In der Logistik stellen die Transportkosten eine bedeutsame Komponente dar. Beim klassischen Transportproblem ist die kostenminimale Zuordnung der Lieferungen von den Lagern zu den Kunden das Ziel. In dieser Seminararbeit wird der Fall des 2-Ebenen Transportproblems behandelt, welcher zusätzlich noch die Zulieferung von den Fabriken zu den Verteilzentren betrachtet und Aufschluss darüber geben soll, wie viele Verteilzentren geöffnet werden müssen. Hierfür werden die Vorteile der genetischen Algorithmen ausgenutzt, welche unter anderem speziell bei diesen rechenaufwendigen Problemen Anwendung finden.

Zunächst werden das einstufige und das zweistufige Transportproblem erläutert. Im Anschluss wird die allgemeine Funktionsweise von genetischen Algorithmen erklärt und später auf den prioritätsbasierten genetischen Algorithmus, entwickelt von Gen und Cheng (1997) speziell für das 2-Ebenen Transportproblem, und den genetischen Operatoren intensiv eingegangen. Im Abschluss wird deren Wirksamkeit anhand von Zahlenbeispielen aufgezeigt.

2. Transportproblem

Abbildung 1: Transportproblem

Abbildung in dieser Leseprobe nicht enthalten

Quelle: Eigene Darstellung, vgl. Suhl, Mellouli (2006), S. 184.

2.1 Einstufiges Transportproblem

Beim einstufigen Transportproblem (siehe Abbildung 1 für ein Beispiel) bieten mehrere Anbieter A i (i = 1, …, m) eine bestimmte Menge ai eines bestimmten Gutes an. Denen gegenüber stehen mehrere Nachfrager B j (j = 1, …, n) mit einem bestimmten Bedarf bj dieses Gutes. Das gesamte Angebot der Anbieter entspricht dem gesamten Bedarf der Nachfrager. Die Transportkosten einer Mengeneinheit von A i nach B j beträgt cij. Bei diesem klassischen Fall ist ein Transportplan gesucht, welcher alle Nachfrager befriedigt und bei welchem die Transportkosten minimal sind.^[1] Mathematisch formuliert sieht dieses Modell wie folgt aus:^[2]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Transshipment-Problem

Abbildung in dieser Leseprobe nicht enthalten

Quelle: Eigene Darstellung, vgl. Suhl, Mellouli (2006), S. 186.

2.2 Zweistufiges Transportproblem

Das zweistufige Transportproblem ist ein Spezialfall des mehrstufigen Transportproblems. Die Menge der Knoten Abbildung in dieser Leseprobe nicht enthalten beim mehrstufigen Transportproblem lassen sich in drei Teile gliedern, in die Menge der Angebotsknoten N a, in die Menge der Nachfrageknoten N b und in die Menge der Transshipment- bzw. Umladeknoten N u. Letztere können mehrere Schichten umfassen. Liegen diese einschichtig vor, spricht man von einem zweistufigen Transportproblem, auch Transshipment-Modell oder Umladeproblem (siehe Abbildung 2 für ein Beispiel) genannt.^[3] Allgemein lässt sich ein Umlade-Problem als gerichteten und bewerteten Graphen G = (N, E, c) verstehen. Gesucht ist wie beim einstufigen Transportproblem ebenfalls der kostenminimale Transportplan. Das mathematische Modell beschreibt sich wie folgt:^[4]

Abbildung in dieser Leseprobe nicht enthalten

3. Genetische Algorithmen

In diesem Kapitel werden neben der allgemeinen Funktionsweise der genetischen Algorithmen der prioritätsbasierte genetische Algorithmus und die drei Operatoren Crossover, Mutation und Selektion beschrieben.

Ein genetischer Algorithmus (GA) ist eine Variante der stochastischen Suche, bei welcher Nachfolgezustände aus der Kombination von zwei Anfangszuständen erzeugt werden.^[5] Basierend auf dem natürlichen Vorbild, sollen GAs analytisch schlecht lösbarer Optimierungsprobleme lösen, indem sie die Lösungszustände solange verändern und miteinander kombinieren, bis sie das Ergebnis bestmöglich präsentieren.^[6]

3.1 Funktionsweise der Genetischen Algorithmen

Zuerst wird zufällig eine Anfangspopulation P0 erzeugt (siehe Abbildung 3 als Beispiel). Mit Hilfe einer Fitnessfunktion wird für die Lösungskandidaten eine Bewertung, ein Fitnesswert bestimmt.^[7] Anhand dieser Werte berechnet sich die Wahrscheinlichkeit, mit welcher mittels Selektion (vergleiche Kapitel 3.3.3) die Auswahl des Kandidaten mit dem höchsten Fitnesswert erfolgt.^[8] Daraus ergeben sich die Fortpflanzungspaare. Andere Varianten der Selektion wählen zufällig, ohne Beachtung möglicher Schwellenwerte, die Fortpflanzungspaare aus. Aus diesen werden durch Rekombination (vergleiche Kapitel 3.3.1), auch Crossover genannt, neue Individuen generiert. Der Mutations-Operator (vergleiche Kapitel 3.3.2) erlaubt es, Lösungen zu finden, welche nicht in der in der Anfangspopulation enthalten sind. Die grobe Struktur eines genetischen Algorithmus lässt sich wie folgt darstellen:

BEGIN

Erstelle eine Anfangspopulation P0

WHILE NOT Stopp-Bedingung DO

Wende genetische Operatoren an, um Pt von Pt-1 zu generieren

Überprüfe Stopp-Bedingung

END

END^[9]

[...]

^[1] Vgl. Suhl, Mellouli (2006), S. 184.

^[2] Vgl. Dempe, Schreier (2006), S. 74.

^[3] Vgl. Suhl, Mellouli (2006), S. 185 f.

^[4] Vgl. Domschke, Drexl (2005), S. 93.

^[5] Vgl. Russel, Norvig (2005), S. 157.

^[6] Vgl. Dawid (1996), S. 37 f.

^[7] "Die Fitnessfunktion ist entscheidend für die Berechnung der Überlebenswahrscheinlichkeit jedes Chromosoms." Quelle: Gerdes, Klawonn, Kruse (2004), S. 68.

^[8] Vgl. Weicker (2002), S. 70.

^[9] Vgl. Dawid (1996), S. 38 ff.