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
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
Zielsetzung & Themen
Die vorliegende Arbeit untersucht den Einsatz eines prioritätsbasierten genetischen Algorithmus zur Lösung des 2-Ebenen Transportproblems. Ziel ist es, ein effizientes Verfahren aufzuzeigen, welches die kostenminimale Zulieferung von Fabriken über Verteilzentren an Kunden sicherstellt und dabei die Anzahl der zu öffnenden Verteilzentren optimiert.
- Mathematische Modellierung von Transportproblemen
- Grundlagen und Funktionsweise genetischer Algorithmen
- Entwicklung eines prioritätsbasierten Kodierungs- und Dekodierungsansatzes
- Analyse genetischer Operatoren wie Crossover, Mutation und Selektion
- Evaluation der Algorithmen-Effektivität anhand von Testdaten
Auszug aus dem Buch
3.2.1 Dekodierungsalgorithmus
In Abbildung 4 seien Kostenmatrix, Kapazitätsrestriktionen mit zugehörigem Transportbaum und prioritätsbasierte Kodierung gegeben. In Abbildung 5 ist die Prozedur zum Dekodieren der Chromosomen abgebildet. Es wird der Knoten mit der höchsten Priorität aus K und J (Menge der Quellen und Lager) ausgewählt, im Beispiel Lager 1 mit einer Priorität von 7. Die Quelle mit den geringsten Transportkosten ist laut Kostenmatrix die Quelle 1 mit c11=11. Im Schritt 4 wird das Minimum der Lagerkosten g11 = min{550, 300} = 300 bestimmt, die Nachfrage des Lagers b1 = 300 – 300 = 0 und Kapazität der Quelle a1 = 550 – 300 = 250 entsprechend neu berechnet. Sobald die Nachfrage eines Lagers gestillt ist (bj=0), wird die Priorität des Lagers auf Null gesetzt und der Knoten mit der nun höchsten Priorität wird ausgewählt. In Abbildung 6 ist die entsprechende Ablaufverfolgung zu dieser Dekodierungsprozedur zu erkennen. Der Algorithmus endet, wenn alle Nachfragen befriedigt sind.
Zusammenfassung der Kapitel
1 Einleitung: Diese Einleitung führt in die Problematik der Transportkostenoptimierung in der Logistik ein und erläutert die Zielsetzung der Arbeit sowie den methodischen Fokus auf genetische Algorithmen.
2 Transportprobleme: Hier werden die mathematischen Grundlagen und Unterschiede zwischen dem klassischen einstufigen Transportproblem und dem komplexeren zweistufigen Transportmodell dargelegt.
3 Genetische Algorithmen: Dieses Kapitel erläutert die allgemeine Funktionsweise genetischer Algorithmen und vertieft den spezifischen prioritätsbasierten Ansatz sowie die eingesetzten Operatoren.
4 Zahlenbeispiele: Die Effektivität des entwickelten Algorithmus wird hier anhand von sieben generierten Testproblemen bewertet und mit einem klassischen, baumbasierten Ansatz verglichen.
5 Fazit: Die Arbeit schließt mit einer zusammenfassenden Bewertung des Potentials genetischer Algorithmen im Supply Chain Management und einem Ausblick auf zukünftige Optimierungsmöglichkeiten.
Schlüsselwörter
Genetische Algorithmen, 2-Ebenen Transportproblem, Logistik, Transportkosten, Optimierung, Transportbaum, Prioritätsbasierte Kodierung, Dekodierung, Crossover, Mutation, Selektion, Supply Chain Management, Fitnessfunktion, NP-schwere Probleme, Rechenaufwand.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit beschäftigt sich mit der kostenminimalen Transportplanung in einer zweistufigen Lieferkette mittels genetischer Algorithmen.
Was sind die zentralen Themenfelder?
Die Kerngebiete umfassen Transportoptimierung, die Anwendung heuristischer Suchverfahren (Genetische Algorithmen) und die Modellierung komplexer Netzwerkstrukturen.
Was ist das primäre Ziel der Untersuchung?
Das Hauptziel ist die Anwendung eines prioritätsbasierten genetischen Algorithmus, um eine kostenoptimale Lösung für das 2-Ebenen Transportproblem zu finden.
Welche wissenschaftliche Methode wird verwendet?
Zum Einsatz kommen stochastische Optimierungsverfahren, konkret genetische Algorithmen mit speziellen Kodierungsschemata und Operatoren wie WMX-Crossover.
Was wird im Hauptteil behandelt?
Der Hauptteil widmet sich der Funktionsweise der Algorithmen, der mathematischen Formulierung der Transportprobleme und der Beschreibung der genetischen Operatoren.
Welche Schlüsselwörter charakterisieren die Arbeit?
Besonders prägend sind Begriffe wie Genetische Algorithmen, 2-Ebenen Transportproblem, Transportbaum und Prioritätsbasierte Kodierung.
Warum ist eine spezielle Kodierung bei Transportbäumen nötig?
Da einfache Prüfernummern zu unzulässigen Lösungen führen können, muss eine spezifische Dekodierung die Repräsentation in zulässige Problemlösungen sicherstellen.
Warum schneidet der prioritätsbasierte Ansatz in den Beispielen besser ab?
Der prioritätsbasierte genetische Algorithmus (pb-GA) findet auch bei größeren Probleminstanzen noch optimale Lösungen, während das st-GA-Verfahren hierbei an Grenzen stößt.
Welche Rolle spielt die Fitnessfunktion für den Algorithmus?
Sie ist entscheidend für die Bewertung der Lösungskandidaten und die Steuerung der Selektionswahrscheinlichkeit im „Roulette Wheel“-Verfahren.
- Quote paper
- Alexander Winterstein (Author), 2007, Ein genetischer Algorithmus für das 2-Ebenen Transportproblem, Munich, GRIN Verlag, https://www.grin.com/document/83589
