Gegenstand dieser Arbeit ist eine Problemstellung, welche dem operationellen Supply Chain Management zugehörig ist. Es wird von einem produzierenden Unternehmen ausgegangen, das kundenseitig Aufträge zur Produktion erhält. Zur Herstellung der von den Kunden in Auftrag gegebenen Güter hält das Unternehmen Produktionsstätten mit Maschinen vor. Die Auslieferung der produzierten Güter an die Kunden erfolgt über einen eigenen Fuhrpark von Transportern. Der Umstand, dass die Herstellung der Produkte direkt mit der Auslieferung an die Endkunden verbunden ist und überdies eine beschränkte Haltbarkeit der produzierten Güter angenommen wird, erfordert einen integrierten Lösungsansatz. Dies bedeutet, dass Produktion und Distribution aufeinander abgestimmt und daher nicht separat geplant werden sollen. Es ergibt sich ein integriertes Produktions- und Distributionsplanungsproblem, im Folgenden mit IPDP abgekürzt.
Ziel dieser Arbeit ist es, für ausgewählte Szenarien eines IPDP ein heuristisches Lösungsverfahren zu entwickeln. Als Werkzeug zur Lösung des IPDP wird eine relativ junge Verfahrensklasse eingesetzt, die der sogenannten Ameisenalgorithmen. Ameisenalgorithmen gehören zur Klasse der naturanalogen Optimierungsverfahren. Wie die Bezeichnung bereits impliziert, gibt das Verhalten von Ameisen bzw. deren Selbstorganisationsfähigkeit im Bereich der Arbeitsteilung, Brutaufzucht, des kooperativen Transports oder der Futtersuche die Inspiration zum Design dieser Art von Algorithmen. Das in dieser Arbeit vorgestellte Verfahren orientiert sich an dem Verhalten von Ameisen bei der Futtersuche. Derartige auf futtersuchende Ameisen basierende Algorithmen wurden bereits erfolgreich auf viele NP-schwere kombinatorische Optimierungsprobleme aus verschiedensten Bereichen angewendet.
Inhaltsverzeichnis
1 Einleitung
2 Formulierung des integrierten Produktions- und Distributionsplanungsproblems
2.1 Beschreibung der Entscheidungssituation
2.2 Betrachtete Szenarien
2.3 Formalisierung des IPDP
3 Ant Colony Optimization
3.1 Die Idee von ACO
3.2 Graphentheoretische Grundlagen
3.3 Repräsentation von kombinatorischen Problemen
3.4 Die Konstruktionsprozesse
3.4.1 Die Funktionsweise von Konstruktionsprozessen
3.4.2 Arten von Konstruktionsprozessen
3.4.3 Der Konstruktionsprozess nach ACS
3.5 Die Struktur von ACO
3.6 Konvergenzaussagen zu ACO
4 Entwicklung einer ACS-Heuristik für das IPDP
4.1 Das Team Orienteering Problem mit Zeitfenstern
4.2 Das Distributionsplanungsproblem
4.2.1 Eine ACS-Heuristik zum DP
4.2.1.1 Das Optimierungsproblem zum DP
4.2.1.2 Der Konstruktionsgraph zum DP
4.2.1.3 Der Konstruktionsprozess
4.2.2 Erweiterung der Heuristik um eine iterierte lokale Suche
4.2.2.1 Der Insertion-Schritt
4.2.2.2 Der Shake-Schritt
4.2.2.3 Die Heuristik
4.2.3 Erweiterung von ILS um Limited Discrepancy Search
4.3 Die Planung der Produktionsreihenfolge
4.3.1 Die Funktionsweise der BGH-MDD-Heuristik
4.3.2 Die Erstellung der Startschedules
4.4 Erweiterung der DP-Heuristik für das IPDP
4.4.1 Berücksichtigung von Kosten
4.4.2 Berücksichtigung von Transportgütern und Transporterkapazitäten
4.4.3 Berücksichtigung des Scheduling und der Haltbarkeit
4.4.4 Anpassung der Lösungskonstruktion an Zielsetzung des IPDP
4.4.5 Einbeziehung von Mehrfachfahrten
4.5 Eine ACS-Heuristik zum IPDP
4.5.1 Das Problem der Stagnation
4.5.2 Die Eingabewerte
4.5.3 Der Gesamtalgorithmus im Pseudocode
5 Auswertungen zum Algorithmus ACS-IPDP
5.1 Vergleich des Algorithmus mit Resultaten zum TOPTW
5.2 Vergleich des Algorithmus mit den Resultaten zum IPDP aus [26]
5.2.1 Das Basisszenario
5.2.2 Verschiedene Haltbarkeitsdauern
5.2.3 Mehrfachfahrten
5.2.4 Mehrfachfahrten mit auslastungsabhängigen Fahrtkosten
5.3 Einordnung der Ergebnisse
6 Das MATLAB-Programm
7 Zusammenfassung und Ausblick
Zielsetzung & Themen
Diese Masterarbeit entwickelt ein heuristisches Lösungsverfahren auf Basis von Ameisenalgorithmen (Ant Colony Optimization, ACO) für ein integriertes Produktions- und Distributionsplanungsproblem (IPDP). Das Ziel ist die Maximierung des Unternehmensgewinns durch eine koordinierte Planung von Auftragsselektion, Produktionsreihenfolge und Tourenplanung unter Berücksichtigung von Kapazitäts- und Haltbarkeitsrestriktionen.
- Entwicklung einer ACS-Heuristik für das IPDP
- Integration von Scheduling-Methoden (BGH-MDD) in die Lösungsfindung
- Optimierung mittels iterierter lokaler Suche (ILS) und Limited Discrepancy Search (LDS)
- Evaluation an Benchmark-Instanzen im Vergleich zu bestehenden Algorithmen
Auszug aus dem Buch
3.1 Die Idee von ACO
Ameisen leben in einem komplexen sozialen Gefüge, einer Ameisenkolonie. Jede Ameise hat eine spezifische Rolle in diesem Ameisenstaat, dessen Erfolg auf der Gemeinschaft beruht. Das Hauptkommunikationsmittel unter Ameisen stellen hierbei nicht visuelle Reize, sondern chemische Duftstoffe, sogenannte Pheromone, dar. Eines dieser Pheromone, das sogenannte „Trail-Pheromon“, spielt bei der Futtersuche einiger Ameisenarten eine wichtige Rolle [16]. Schwärmen Ameisen aus ihrem Nest aus, um Futterquellen ausfindig zu machen, sondern sie auf ihren Wegen permanent Trail-Pheromone aus. Diese Pheromone dienen als Orientierungshilfe für die Artgenossen. Je mehr Pheromone in einer Wegrichtung aufzufinden sind, desto wahrscheinlicher folgen Ameisen dieser Spur. Mit der Zeit verdunsten diese Pheromone und deren Signalwirkung schwächt sich.
Das sogenannte Double Bridge Experiment zu Beginn der 90er-Jahre zeigte, dass Ameisen durch die Kommunikation mittels Pheromonen kürzeste Wege zur Futterquelle ausfindig machen können [16].
Zusammenfassung der Kapitel
1 Einleitung: Einführung in das Supply Chain Management und Definition des integrierten Produktions- und Distributionsplanungsproblems (IPDP) als Gegenstand der Arbeit.
2 Formulierung des integrierten Produktions- und Distributionsplanungsproblems: Detaillierte Darstellung der Entscheidungssituation, der betrachteten Szenarien und formale Definition des IPDP.
3 Ant Colony Optimization: Vermittlung der theoretischen Grundlagen von Ameisenalgorithmen, der Graphentheorie und der Funktionsweise der Konstruktionsprozesse.
4 Entwicklung einer ACS-Heuristik für das IPDP: Schrittweise Entwicklung des Algorithmus, beginnend bei verwandten Problemen (TOPTW, DP) bis hin zur vollständigen IPDP-Heuristik mit ILS und LDS.
5 Auswertungen zum Algorithmus ACS-IPDP: Empirische Leistungsbewertung des Algorithmus anhand von Benchmark-Instanzen und Vergleich mit bestehenden Lösungsansätzen.
6 Das MATLAB-Programm: Kurze Anleitung zur Nutzung des implementierten Programms und Erläuterung der Benutzeroberfläche.
7 Zusammenfassung und Ausblick: Resümee der Arbeit und Diskussion potenzieller zukünftiger Forschungsansätze.
Schlüsselwörter
Produktionsplanung, Distributionsplanung, IPDP, Supply Chain Management, Ameisenalgorithmus, ACS, Metaheuristik, Kombinatorische Optimierung, Tourenplanung, Scheduling, Lokale Suche, ILS, LDS, Pheromon, Optimierung
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit befasst sich mit der effizienten Abstimmung von Produktions- und Auslieferungsprozessen in produzierenden Unternehmen, um Kosten zu senken und die Wettbewerbsfähigkeit zu erhöhen.
Was sind die zentralen Themenfelder der Arbeit?
Die zentralen Felder sind das Supply Chain Management, speziell die Integration von operativer Produktionsplanung und Distributionslogistik unter Nebenbedingungen wie Haltbarkeit und Kapazitäten.
Was ist das primäre Ziel oder die Forschungsfrage?
Das Ziel ist die Entwicklung und Evaluierung eines heuristischen Verfahrens auf Basis des Ant Colony System (ACS), um komplexe IPDP-Instanzen profitmaximierend zu lösen.
Welche wissenschaftliche Methode wird verwendet?
Es wird eine metaheuristische Methode eingesetzt, basierend auf dem Ant Colony Optimization (ACO) Ansatz, ergänzt durch lokale Suchverfahren (ILS) und Limited Discrepancy Search (LDS).
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil umfasst die theoretischen Grundlagen von ACO, die schrittweise Herleitung der Heuristik von einem einfachen Distributionsproblem (DP) zum IPDP sowie die Implementierung der Produktionsreihenfolgeplanung.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit lässt sich durch Begriffe wie IPDP, Produktions- und Distributionsplanung, ACO, Metaheuristik, Scheduling und kombinatorische Optimierung charakterisieren.
Wie unterscheidet sich die ACS-Heuristik von herkömmlichen Ansätzen?
Die Heuristik integriert die Produktionsplanung direkt in den Konstruktionsprozess des Ameisenalgorithmus, statt sie separat zu behandeln, was eine bessere Abstimmung der Teilprobleme ermöglicht.
Warum wurde LDS zur Verbesserung der lokalen Suche eingesetzt?
LDS wurde implementiert, um den Suchraum effektiver zu erkunden, indem gezielte Abweichungen von der heuristischen Entscheidung zugelassen werden, was bei Stagnation des Algorithmus zu besseren Ergebnissen führen kann.
- Quote paper
- Jan Weidner (Author), 2016, Ein Ameisenalgorithmus zur Lösung von integrierten Produktions- und Distributionsplanungsproblemen, Munich, GRIN Verlag, https://www.grin.com/document/372473
