Ein Ameisenalgorithmus zur Lösung von integrierten Produktions- und Distributionsplanungsproblemen

Inhaltsverzeichnis

1 Einleitung.. 1

2 Formulierung des integrierten Produktions- und Distributionsplanungsproblems.. 4

2.1 Beschreibung der Entscheidungssituation.. 6

2.2 Betrachtete Szenarien.. 7

2.3 Formalisierung des IPDP.. 8

3 Ant Colony Optimization.. 12

3.1 Die Idee von ACO.. 12

3.2 Graphentheoretische Grundlagen.. 14

3.3 Repräsentation von kombinatorischen Problemen.. 15

3.4 Die Konstruktionsprozesse.. 22

3.4.1 Die Funktionsweise von Konstruktionsprozessen.. 22

3.4.2 Arten von Konstruktionsprozessen.. 29

3.4.3 Der Konstruktionsprozess nach ACS.. 29

3.5 Die Struktur von ACO.. 31

3.6 Konvergenzaussagen zu ACO.. 32

4 Entwicklung einer ACS-Heuristik für das IPDP.. 34

4.1 Das Team Orienteering Problem mit Zeitfenstern.. 34

4.2 Das Distributionsplanungsproblem.. 34

4.2.1 Eine ACS-Heuristik zum DP.. 36

4.2.1.1 Das Optimierungsproblem zum DP.. 36

4.2.1.2 Der Konstruktionsgraph zum DP.. 37

4.2.1.3 Der Konstruktionsprozess.. 38

4.2.2 Erweiterung der Heuristik um eine iterierte lokale Suche.. 43

4.2.2.1 Der Insertion-Schritt.. 43

4.2.2.2 Der Shake-Schritt.. 47

4.2.2.3 Die Heuristik.. 47

4.2.3 Erweiterung von ILS um Limited Discrepancy Search.. 50

4.3 Die Planung der Produktionsreihenfolge.. 52

4.3.1 Die Funktionsweise der BGH-MDD-Heuristik.. 53

4.3.2 Die Erstellung der Startschedules.. 59

4.4 Erweiterung der DP-Heuristik für das IPDP.. 60

4.4.1 Berücksichtigung von Kosten.. 61

4.4.2 Berücksichtigung von Transportgütern und Transporterkapazitäten.. 62

4.4.3 Berücksichtigung des Scheduling und der Haltbarkeit.. 63

4.4.4 Anpassung der Lösungskonstruktion an Zielsetzung des IPDP.. 66

4.4.5 Einbeziehung von Mehrfachfahrten.. 67

4.5 Eine ACS-Heuristik zum IPDP.. 68

4.5.1 Das Problem der Stagnation.. 68

4.5.2 Die Eingabewerte.. 69

4.5.3 Der Gesamtalgorithmus im Pseudocode.. 70

5 Auswertungen zum Algorithmus ACS-IPDP.. 74

5.1 Vergleich des Algorithmus mit Resultaten zum TOPTW.. 74

5.2 Vergleich des Algorithmus mit den Resultaten zum IPDP aus [26].. 77

5.2.1 Das Basisszenario.. 77

5.2.2 Verschiedene Haltbarkeitsdauern.. 79

5.2.3 Mehrfachfahrten.. 79

5.2.4 Mehrfachfahrten mit auslastungsabhängigen Fahrtkosten.. 80

5.3 Einordnung der Ergebnisse.. 81

6 Das MATLAB-Programm.. 82

7 Zusammenfassung und Ausblick.. 84

Literaturverzeichnis.. 86

1 Einleitung

Heutzutage müssen sich viele Unternehmen in einem internationalen Umfeld behaupten. Der aus der Globalisierung resultierende Wettbewerbs- und Kostendruck stellt jegliche Prozesse eines Unternehmens auf den Prüfstand. Die effiziente Koordinierung der betrieblichen Produktions- und Distributionsabläufe stellt hierbei einen wichtigen Hebel zur Kostensenkung und damit zur Steigerung der Konkurrenzfähigkeit dar.

Diese Thematik fällt in den Kontext des sogenannten Supply Chain Managements (SCM). Per Definition stellt SCM die „Gestaltung, Lenkung und Entwicklung von Wertschöpfungsketten und -netzwerken“ dar [2]. Dies geschieht maßgeblich mit dem Ziel der Kostenminimierung. Der Begriff SCM lässt sich in drei Teilbereiche gliedern [2]:

• Das normative SCM umfasst das Design des Netzwerks und der Wertschöpfungskette und ist langfristig auf ca. 5 − 10 Jahre ausgelegt.

• Das strategische SCM sorgt im Wesentlichen für die Umsetzung und Konfiguration der im normativen SCM getroffenen Entscheidungen. Dies erfolgt über einen Zeitraum von einem bis zu mehreren Jahren.

• Das operationelle SCM befasst sich mit der konkreten Ausgestaltung der Materialflüsse in Beschaffung, Produktion und Vertrieb. Der Planungshorizont erstreckt sich hierbei von Wochen bis hin zu wenigen Monaten.

Gegenstand dieser Arbeit ist eine Problemstellung, welche dem operationellen SCM 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.

Die Behandlung derartiger Problemstellungen ist aufgrund der gesteigerten wirtschaftlichen Relevanz vermehrt Gegenstand der Forschung geworden. In [7] wird ein Überblick über die in diesem Kontext wichtigsten Veröffentlichungen bis zum Jahr 2008 gegeben. Erwähnenswert ist darüber hinaus das Werk von Viergutz [25]. Dort wird ein gemischtganzzahliges lineares Programm (engl. Mixed Integer Linear Programm, MILP) angegeben, welches Produktions- und Distributionsplanungsprobleme mit mehreren Transportern unter Einbeziehung von Mehrfachfahrten abbildet. Zur Lösung kleinerer Instanzen wird eine Modifizierung des in [3] angegebenen Branch-and-Bound-Verfahrens aufgezeigt. Außerdem wird eine Tabu-Suche zur Lösung größerer Probleminstanzen vorgeschlagen. Eine maßgebliche Generalisierung der von Viergutz behandelten Problemstellung stellt die jüngst erschienene Dissertation von Wendt [26] dar. Dort werden eine Reihe weiterer realitätsnaher Gegebenheiten der Produktions- und Distributionsplanung in einem MILP formuliert. Zudem wird für die Lösung eines speziellen Szenarios ein Branch-and-Bound-Verfahren entwickelt. Die allgemeineren Ausgestaltungen des dort formulierten IPDP werden mit Standardsoftware (IBM ILOG CPLEX) gelöst.

Ziel dieser Masterarbeit ist es, für ausgewählte Szenarien eines IPDP ein heuristisches Lösungsverfahren zu entwickeln. In der anschließenden Auswertung sollen die Ergebnisse mit den Berechnungen aus [26] verglichen werden. 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 [16]. 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. Eine gute Übersicht über die jüngsten Entwicklungen hierzu verschaffen [9] und [17].

Diese Arbeit legt in Kapitel 2 die Beschreibung des IPDP und dessen Szenarien dar, welche im Rahmen dieser Ausarbeitung behandelt werden. Es wird die Entscheidungssituation des IPDP erläutert und aufgezeigt welche realistischen Gegebenheiten durch diese Ausgestaltungen des IPDP abgebildet werden. Kapitel 3 startet mit einer Einführung zu Ameisenalgorithmen, indem dort zunächst die zu Grunde liegende Idee dieser Verfahrensklasse erläutert wird. Es folgt ein allgemeines Konzept, welches die Anwendung dieser Methodik auf beliebige kombinatorische Optimierungsprobleme ermöglicht. Kapitel 4 beginnt mit der Entwicklung eines Algorithmus für eine Relaxierung des in Kapitel 2 charakterisierten IPDP. Die Relaxierung wird dann sukkzessive erweitert, sodass dieses Kapitel schließlich in der Vorstellung eines Algorithmus zum IPDP mündet.

Fortgefahren wird in Kapitel 5 mit der Auswertung des vorgestellten Algorithmus. Dazu werden verschiedene Instanzen des IPDP betrachtet. Es erfolgt eine Einwertung des Algorithmus hinsichtlich der Eignung zur Lösung spezieller Ausgestaltungen des IPDP. Einen Überblick über die Anwendung des im Rahmen dieser Arbeit implementierten Programms gibt Kapitel 6. Den Abschluss bilden eine Zusammenfassung und ein Ausblick auf mögliche Erweiterungen und Anpassungen der entwickelten Heuristik zum IPDP.

2 Formulierung des integrierten Produktions- und Distributionsplanungsproblems

Zu Grunde gelegt wird ein produzierendes Unternehmen, welchem zu Beginn einer Planungsperiode eine Menge von Kundenaufträgen vorliegen. Diese Kundenaufträge erfragen allesamt die Herstellung und Lieferung eines Produktes in einer bestimmten Menge und in einem vorgegebenen Zeitraum. Die Aufträge können jeweils entweder angenommen oder abgelehnt werden. Die zu liefernden Güter weisen überdies eine begrenzte Haltbarkeit auf. Zur Herstellung der Produkte stehen dem Unternehmen beschränkte Produktionskapazitäten zur Verfügung. Die anschließende Auslieferung an die Kunden erfolgt über eine eigene Transpoterflotte.

Aus Unternehmenssicht sind drei Entscheidungen zu treffen. Die Abfolge dieser Entscheidungen wird in Abbildung 2.1 dargestellt.

Abb. 2.1: Der 3 - stufige Entscheidungsprozess des Unternehmens (vlg. [ 26 ])

[Abbildungen und Tabellen sind nicht enthalten in dieser Leseprobe.]

Zunächst muss das Unternehmen aus den potentiell zu bearbeitenden Aufträgen eine Auswahl treffen (Selektion). Anschließend erfolgt die Herstellung dieser ausgewählten Aufträge (Produktion), ehe die Auslieferung an die Kunden durchgeführt wird (Distribution). Jede einzelne Entscheidung für sich zu treffen sorgt i.A. für Konflikte. So beeinflusst eine Selektionsentscheidung immer auch die nachfolgenden Prozesse der Produktion und Distribution. Ebenso hat die Produktionsreihenfolge der Güter Einfluss auf die Distribution. Ein Beispiel soll verdeutlichen, dass eine unabhängige Betrachtung dieser drei Probleme i.A. die falsche Vorgehensweise darstellt.

Abb. 2.2: Mögliche Konflikte bei isolierter Planung

[Abbildungen und Tabellen sind nicht enthalten in dieser Leseprobe.]

In Abbildung 2.2 sind dazu die drei Stufen der Planung beim IPDP aufgezeigt. Isoliert betrachtet ergeben sich jeweils unterschiedliche Zielsetzungen in diesen einzelnen Schritten. Das Ziel der Gewinnmaximierung sorgt bei der Selektion dafür, dass jeder potentiell gewinnbringende Auftrag, welcher in obiger Zeichnung jeweils durch einen rechteckigen Balken dargestellt ist, angenommen wird. Bei fehlender Berücksichtigung der Distributionsgegebenheiten kann es somit passieren, dass ein Auftrag angenommen wird, welcher mit der zur Verfügung stehenden Transporterkapazität nicht ausgeliefert werden kann. Die Produktion nimmt sich zum Ziel, alle angenommenen Aufträge möglichst schnell herzustellen. Ohne Wissen über die anschließende Distributionsreihenfolge kann es daher vorkommen, dass ein Auftrag zu früh produziert wird und die Haltbarkeit des Produktes bei Auslieferung an den entsprechenden Kunden nicht mehr gewährleistet ist. Letztlich können in Abbildung 2.2 nur drei der fünf angenommenen Aufträge ordnungsgemäß ausgeführt werden. Dies sind nur zwei exemplarisch dargelegte Konflikte, welche aus der isolierten Betrachtung der Planungsschritte Selektion, Produktion und Distribution resultieren können. Es wird deutlich, dass ein integrierter Ansatz zur Behandlung des IPDP notwendig ist, um derartige Abstimmungsprobleme zu vermeiden.

2.1 Beschreibung der Entscheidungssituation

Die Entscheidungssituation des Unternehmens beim IPDP soll nun detailliert beleuchtet werden. Beim ersten Planungsschritt, der Selektion, kann eine Bestellung entweder angenommen oder abgelehnt werden. Resultierend aus einer Ablehnung sind Nichtbelieferungskosten an den Auftraggeber zu zahlen. Ist eine Bestellung angenommen, so muss diese vollständig produziert und fristgerecht ausgeliefert werden. Zur Produktion verfügt das Unternehmen über einen Produktionsstandort, welcher im Folgenden Depot genannt wird. Im Depot stehen eine oder mehrere homogene Maschinen zur Verfügung, um die Aufträge zu produzieren. Entschieden werden muss sowohl über die Zuordnung der Aufträge zu den Maschinen, als auch über die Produktionsreihenfolge der einer Maschine zugeordneten Aufträge. Es wird hierbei angenommen, dass bei der Produktion keine Rüstkosten/-zeiten vorliegen. Dies bedeutet, dass nach Fertigstellung eines Auftrags auf einer Maschine kein Umrüstungsaufwand (unter Zeit- wie Kostenaspekten) zur Bearbeitung eines beliebigen Folgeauftrags auf derselben Maschine anfällt. Die Produktion eines Auftrags muss unterbrechungsfrei durchgeführt werden. Sie darf also nicht in mehrere Teilschritte aufgeteilt werden und muss, sofern einmal begonnen, zu Ende geführt werden. Eine Maschine kann stets nur einen Auftrag gleichzeitig bearbeiten. Überdies weisen die hergestellten Produkte nur eine beschränkte Haltbarkeitsdauer auf. Die Haltbarkeit beginnt abzulaufen, sobald die Produktion des jeweiligen Produkts beendet ist. Nach Fertigstellung der Produktion aller für eine Auslieferungsfahrt eines Transporters vorgesehenen Produkte, erfolgt die Distribution. Hierzu stehen homogene Transporter bereit, welche jeweils eine beschränkte Ladekapazität aufweisen. Jeder der für eine Fahrt vorgesehenen Kundenbedarfe beansprucht eine bestimmte Ladekapazität des zugehörigen Transporters. Durch die Nutzung eines Transporters fallen sowohl Fixkosten für den Gebrauch, als auch distanzabhängige Kosten für die Auslieferungsfahrt an. Für jeden Transporter im Fuhrpark ist zu entscheiden, ob er genutzt wird oder nicht. Für die Tourenplanung ist festzulegen, wann der Transporter das Depot verlässt und wann und in welcher Reihenfolge er die Belieferung der Kunden auf seiner Tour durchführt. Die Produktauslieferung beim Kunden beansprucht eine Servicedauer. Der Beginn dieser Servicedauer, welche die zur Entladung benötigte Zeit beim Kunden repräsentiert, muss hierbei innerhalb eines kundenspezifischen Zeitfensters liegen. Zudem muss beim Servicestart die Haltbarkeit des Produkts sichergestellt sein. Der Servicestart ist also ausschlaggebend für die Einhaltung der Zeitfenster- und Haltbarkeitsvorgaben, nicht der Zeitpunkt der Beendigung des Services beim Kunden[1]. Kommt ein Transporter vor Zeitfensterbeginn beim Kunden an, so muss mit der Entladung bis zum Öffnen des Belieferungszeitfensters gewartet werden. Die Rückkehr der Transporter zum Depot muss bis zu einem vorgegebenen Zeitpunkt erfolgen. Dem Depot wird daher ebenfalls ein Zeitfenster zugeordnet.

Das Unternehmen muss nun aus den für den Planungszeitraum eingegangenen Aufträgen selektieren, einen Produktionsplan bestimmen und einen Auslieferungsplan festlegen. Dies soll unter der Maßgabe geschehen, dass der Gewinn des Unternehmens maximiert wird. Dieser ergibt sich aus den Einnahmen durchgeführter Aufträge abzüglich der Nichtbelieferungskosten, der Transporterfixkosten sowie der Fahrtkosten der Transporter.

2.2 Betrachtete Szenarien

In dieser Arbeit werden verschiedene Ausgestaltungen des IPDP betrachtet. Eine Übersicht über die abgedeckten Variationen findet sich in der nachfolgenden Tabelle 2.1:

Tab. 2.1: Behandelte Ausprägungen des IPDP

[Abbildungen und Tabellen sind nicht enthalten in dieser Leseprobe.]

Im rechten Teil der Tabellenspalte „Optionen“ ist jeweils die allgemeinere Ausprägung des IPDP gegeben. Auf die jeweilige unternehmerische Bedeutung der Punkte 1 − 4 aus Tabelle 2.1 wird im Folgenden eingegangen:

1. Es kann sein, dass ein Transporter nach Absolvieren einer Auslieferungsfahrt eine weitere Tour tätigen soll. Der Transporter kehrt also leer von seiner ersten Tour zurück, wird erneut beladen und führt dann nochmals eine Auslieferungsfahrt durch. Fixkosten fallen für diesen Transporter in der betrachteten Planungsperiode dann nicht erneut an. Denkbar ist z.B. ein Fall, bei dem der an der Kapazitätsgrenze beladene Transporter vom Depot losfährt, um einen nahegelegenen Großkunden zu beliefern. Die Rückkehr von diesem Auftrag erfolge so früh, dass derselbe Transporter eine Reihe weiterer Kunden am gleichen Arbeitstag bedienen kann. Es muss kein zusätzlicher Transporter eingeplant werden und es fallen somit keine weiteren Fixkosten an. Aus unternehmerischer Sicht ist dieses Vorgehen daher sinnvoll.

2. Die von den identischen Maschinen produzierten Produkttypen können unterschiedlich sein und folglich verschiedene Haltbarkeiten aufweisen. Denkbar ist sowohl die Produktion lang haltbarer Güter (z.B. Kunststoff, Stahl, Konserven), als auch die Produktion von Gütern mit einer sehr begrenzten Haltbarkeitsdauer (z.B. verderbliche Lebensmittel, Arzneimittel). Die Abstimmung des Produktionsstartzeitpunkts mit dem Zeitpunkt der Belieferung des Kunden ist hierbei essentiell, um zu gewährleisten, dass die Güter „frisch“ beim Kunden ankommen.

3. Die Erhebung auslastungsabhängiger Fahrtkosten spiegelt einen weiteren realistischen Faktor wider, welcher beispielsweise durch die positive Korrelation zwischen dem Gewicht der Ladung und dem Benzinverbrauch des Transporters erklärt werden kann.

4. Die Anzahl der zur Verfügung stehenden Maschinen ist variabel. Durch Änderung dieses Wertes lassen sich Erkenntnisse über das Potential eines Unternehmens gewinnen, welches es durch Erweiterung seiner Produktionskapazitäten ausschöpfen könnte.

Neben den in dieser Ausarbeitung untersuchten Ausprägungen 1 − 4 sind weitaus mehr Faktoren denkbar, um das IPDP zu erweitern und zusätzliche realistische Gegebenheiten der Selektion, Produktion und Distribution zu berücksichtigen. So sind bei der Selektion die Punkte Verbundenheit von Bestellungen, Priorisierung von Bestellungen oder verpflichtend zu beliefernde Kunden zu nennen. Die Produktion kann an verschiedenen Standorten stattfinden, verschiedene Maschinentypen vorhalten, die Unterbrechung von Aufträgen einbeziehen und überdies reihenfolgeabhängige Rüstkosten aufweisen. Außerdem kann die Auslieferung um die realitätsnahen Aspekte Lieferungsaufteilung und Belieferung in mehreren Zeitfenstern erweitert werden. Diese vorgenannten Erweiterungen wurden bereits in [26] behandelt und in einem MILP modelliert. Die Einbeziehung all dieser Aspekte im Rahmen einer neuen heuristischen Herangehensweise, wie sie in dieser Ausarbeitung erfolgt, würde den Rahmen dieser Arbeit übersteigen. Daher wird der Fokus hier auf die oben genannten Punkte 1 − 4 gelegt.

2.3 Formalisierung des IPDP

Im Folgenden soll die in Abschnitt 2.1 beschriebene Entscheidungssituation zum IPDP, unter Einbeziehung der im vorherigen Abschnitt 2.2 aufgezeigten Variationen, formalisiert werden. Notation und Struktur dieses Abschnitts sind an [26] angelehnt.

[...]

---

[1] Dies ist konsistent mit der Berücksichtigung von Servicezeiten in [18] und wird aus Gründen der Vergleichbarkeit der Ergebnisse aus Abschnitt 5.1 mit den dortigen Resultaten übernommen.