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.
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.
- Citation du texte
- Alexander Winterstein (Auteur), 2007, Ein genetischer Algorithmus für das 2-Ebenen Transportproblem, Munich, GRIN Verlag, https://www.grin.com/document/83589
-
Téléchargez vos propres textes! Gagnez de l'argent et un iPhone X. -
Téléchargez vos propres textes! Gagnez de l'argent et un iPhone X. -
Téléchargez vos propres textes! Gagnez de l'argent et un iPhone X. -
Téléchargez vos propres textes! Gagnez de l'argent et un iPhone X. -
Téléchargez vos propres textes! Gagnez de l'argent et un iPhone X. -
Téléchargez vos propres textes! Gagnez de l'argent et un iPhone X. -
Téléchargez vos propres textes! Gagnez de l'argent et un iPhone X.