„A Genetic Algorithm for Solving the Container Loading Problem“

H. Gehring und A. BortfeldtInt. Trans. Opl. Res., Vol.4, No. 5/6, pp. 401-418, 1997

Universität Karlsruhe (TH)

Institut für Anwendungen des Operations Research

(ANDOR)

Seminar: Heuristische Verfahren WS 03/04

13.01.2004

Raphael Paschke

13.01.2004 2

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Agenda

Einleitung Containerbeladeproblem Heuristiken Genetische Algorithmen (GA)

Umsetzung Optimierungsproblem Heuristik GA Hybridisierung

Test, Ergebnisse und Kritik Einhalten der Restriktionen Vergleich mit anderen Verfahren Kritik

Diskussion

13.01.2004 3

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Containerbeladeproblem

Im heutigen Warenumschlag, insbesondere im Seehandel, nimmt der nach DIN/ISO 830 genormte Standardcontainer aufgrund seiner Be- und Entladegeschwindigkeit, sowie seiner Kostenersparnisse eine überragende Stellung ein.

13.01.2004 4

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Aufgabenstellung

Ein einziger, in seinen Abmessungen gegebener Container ist mit kleineren, in ihrer Anzahl und Abmessungen bekannten Packstücken zu beladen.

Gesucht ist die Anordnung der Packstücke, wobei i.A.nur eine Teilmenge der Packstücke verwendet wird.

In Bezug auf die gewählte Zielfunktion soll der vorhandene Stauraum möglichst effizient genutzt werden.

Weiterhin sind verschiedene Restriktionen einzuhalten, z.B.

Befestigung Bodendruck Maß Zusammenstaubarkeit Plazierungsrestriktion Orientierung der Kisten Überstaubarkeit Geamtgewicht Gleichgewicht

13.01.2004 5

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Heuristiken

Einordnung in Verschnitt- und Packunsprobleme 3-dimensionales Packungsproblem Kombinatorisches Problem

Da bei NP-vollständigen Problemen das Zeitverhalten eines exakten Verfahrens nicht für alle möglichen Instanzen des Problems garantiert werden kann, verwendet man suboptimale Verfahren, die in akzeptabler Zeit, höchstens jedoch innerhalb der angegebenen Grenzen, Lösungen finden.

13.01.2004 6

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Genetischer Algorithmus I (GA)

Prinzipielle Funktionsweise Anlehnung an Natur

Wichtige Designentscheidungen für Algorithmus Repräsentation Initialisierung Zielfunktion & Fitnessfunktion Operatoren

Selektion der Eltern Rekombination Mutation Umweltselektion

Abbruchbedingung Wichtige Parameter

Population: Struktur, Grösse, etc. Wahrscheinlichkeiten für Operatoren Anzahl der Generationen

13.01.2004 7

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Genetischer Algorithmus II (GA)

Vorteile Verständlichkeit Flexibilität Integration von problemspezifischem Wissen Möglichkeit der Parallelverarbeitung wenig formale Voraussetzungen

Nachteile keine formale Entwurftechniken Parameter und Operatorenwahl entscheidend für

Lösungsgüte, i.A. nur empirisch bestimmbar Trade-Off zwischen Konvergenz und Lösungsgüte unklar,

bzw. a priori schwer bestimmbar keine allgemeinen Konvergenzbeweise

13.01.2004 8

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Optimierungsproblem

Beschreibung Container

rechteckiges Objekt c beschrieben durch Vektor der Abmessungen (xc, yc, zc)

ausgehend von linker, unterer Ecke des Containers als Koordinatenursprung eines kartesischen Systems

Packstücke rechteckige Objekte (Kisten) b=1,...,nb, beschrieben durch (bdim1, bdim2, bdim3; bvalue, bweight) falls viele Kisten mit gleichen Maßen:

Kistenvorrat schwach heterogenschwach heterogen ansonsten stark heterogenstark heterogen

Zielfunktion Verstautes Kistenvolumen Summierter Frachtwert andere sinnvolle Möglichkeiten

13.01.2004 9

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Optimierungsproblem

Zulässigkeit F1: Kisten

auf Containerboden oder auf Deckfläche einer anderen Kiste, geometrische Mittelpunkt einer Kiste unterstützt durch

untere Kiste F2: Kiste seitenparallel zu Grenzflächen des Containers F3: Kisten vollständig innerhalb des Containers

Restriktionen C1: Orientierung bestimmter Kisten eingeschränkt C2: Verbot der Überstapelung C3: Gesamtgewicht des Containers C4: Stabilität der Kisten

unterstützte Fläche zu Gesamtbodenfläche der Kiste C5: Gleichgewichtsrestriktion für Container

13.01.2004 10

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Idee des Verfahrens

Einteilung der Menge der Kisten in disjunkte Türme mittels Greedy-Algorithmus, der die Stauraumverluste innerhalb der Basiskiste minimiert;

kombinatorische Komponente

Bedeckung des Containerbodens mit den Türmen mittels GA, der den Gesamtwert aller verpackten Kisten maximiert;

geometrische Komponente

Wiederholung der obigen Schritte mit neuem Parameter für Greedy-Algorithmus, bis Abbruchbedingung erfüllt und Ausgabe der besten Lösung.

Iteration

13.01.2004 11

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Heuristik

Definition Turm Genau eine Kiste als Basis eines Turmes möglich Jede weitere Kiste steht vollständig auf unterer Kiste

Beschreibung Turm it als Menge von Kisten TBoxes(j) j=1,...,ntboxes beschrieben durch (b, bdimx, bdimy, bdimz; bconerx, bcornery,

bcornerz)

Definition Turmmenge Menge, besthend aus allen erzeugten Türmen, die zusammen

alle verfügbaren Kisten beinhalten Beschreibung

Turmmenge TSet(it) it=1,...,ntowers beschrieben durch (tvalue, tloss, ntboxes, tdim1, tdim2; TBoxes)

13.01.2004 12

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Illustration Turm

13.01.2004 13

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Illustration Turmraumkonzept

„Turmraumkonzept“Bestimmen des freien Raumes oberhalb einer Kiste und Speicherung in Datenstruktur Keller (Stack)

13.01.2004 14

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Illustration Turmraum

13.01.2004 15

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Alg. Turmerzeugung I

13.01.2004 16

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Alg. Turmerzeugung II

13.01.2004 17

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Genetischer Algotihmus (GA)

Noch 2-dimensionales, geometrisches Problem zu lösen

Einführung „Eckenkonzept“ Definition:

Ecke (cornerx, cornery, cwidth) Punkt auf virtuellem Containerboden. Anordnungsecke, falls

cornerx mit x-Koordinate der vorderen Kante der Turmfläche eines bereits plazierten Turmes übereinstimmt

cornery mit y-Koordinate der linken Kante eines bereits plazierten Turmes übereinstimmt

höchstens durch vordere oder rechte Kante einer plazierten Grundfläche bedeckt wird

Die sogenannte „freie Breite einer Ecke“ wird definiert als y-Abstand zur nächsten Kiste bzw. Containerseite

13.01.2004 18

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Illustration „Eckenkonzept“

Anordnungseckenmenge CSet Enthält alle möglichen Plazierungen von Türmen,

zunächst nur (0,0,yc) Aktualisierung nach jedem Setzen eines Turmes

Wird durch lineare Relation geordnet corner1corner2 :

corner1.x<corner2.x corner1.x=corner2.y corner1.y<corner2.y

13.01.2004 19

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Beschreibung GA I

Repräsentation Genotyp Chrom(i), i=1,...,ntowers: SequenzSequenz der Plazierung der

Türme beschrieben durch Vektor (it, trot)

trot :=0, wenn grössere Dimension des Turmes in y-Achse

Initialisierung zufällige PermutationenPermutationen des Indexes it

Decodierung/Phänotyp Lösung Sol(i), i=1,...,ntowers: SequenzSequenz der Plazierungen beschrieben durch Vektor (it, trot,tcornerx,tcornery)

Evaluierung und Fitnessfunktion

npopkknpopnpopnpop

solf k ,,1)1()1(

2

1

2)(

npop

k kk solfsolf1

1)(0)(

13.01.2004 20

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Beschreibung GA II

Genetische Operatoren Selektion der Eltern: stochastisch

Wahrscheinlichkeit direkt aus Fitnessfunktion Umweltselektion:deterministisch

sofortiges Ersetzen der schlechtesten Lösung Crossover: Permutationserhaltende Operatoren

Uniform Order Based Partially Mapped Cycle

Drehungsvarianten werden von Eltern übernommen Mutation

Inversion Scramble Sublist

Drehungsvarianten zufällig aus (0,1) gewählt

! A priori kaum zu entscheiden, welcher Operator am besten; Verfahrenstest

13.01.2004 21

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Beschreibung GA III

Parameter Eltern- und Nachkommenpopulation:

Anzahl der Individuuen konstant: npop=50 Struktur Inkrementeller GA

Wahrscheinlichkeiten für Operatoren: pm=0,5

pc=0,5

Anzahl der Generationen fest, somit zugleich Abbruchbedingung: ngen=300

13.01.2004 22

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Alg. Decodierung&Evaluation

13.01.2004 23

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Hybridisierung

Problemspezifisches Wissen miteinbringen: Startpopulation

Türme der Grösse nach mittels „Eckenkonzept“ setzen Decodierung

„Nachbesserung“ mittels heuristischer Regeln: R1: aktuelle Plazierung direkt nicht möglich, allerdings

nach 90° Drehung möglich, dann drehen und setzen R2: falls aktuelle Plazierung nicht in realem Container,

aber eine andere Plazierungsmöglichkeit in realem Container besteht, dann wähle erste Alternative

R3: falls plazierbarer, alternativer Turm mit nicht-kleinerer Grundfläche, aber geringerem Stauraumverlust existiert, dann wähle entsprechende Alternative

R4: falls durch Plazierung eine zu kleine Fläche entstehen sollte und eine Drehung möglich ist, dann plaziere dementsprechend

13.01.2004 24

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Einhalten der Restriktionen

Restriktionen C1: Orientierung bestimmter Kisten eingeschränkt C2: Einschränkung der Überstapelung C3: Gesamtgewicht des Containers C4: Stabilität der Kisten, definiert als unterstützte Fläche zu Geamtbodenfläche der Kiste C5: Gleichgewichtsrestriktion für Container

C1 leicht bei Erzeugung der Turmsets zu erreichen C2 Stauraum oberhalb Kiste im Kellerspeicher

gesperrt C3:

bei Erzeugung der Türme Gewicht berechnen bei Decodierungsprozess jeweils vor dem Setzen auf

zulässiges Gesamtgewicht prüfen C4 ist immer erfüllt C5 kann nur durch Verschiebung verbessert werden,

allerdings nicht strikt erfüllt werden

13.01.2004 25

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Verfahrenstest

Parameter Verkleinern der Populationsgrösse npop führt zu

schlechteren Ergebnissen Vergrösserung der Generationenanzahl ngen führt zu

keiner wesentlichen Verbesserung Vergleich Operatoren

Rechenzeiten nahezu identisch Auslastungen differieren kaum Auswahl: Uniform order based Crossover mit sramble

sublist Mutation Vergleich mit reiner Zufallssuche

ohne Hybridisierung ist GA schlechter, allerdings bei weniger als der halben Rechenzeit

mit Hybridisierung zeigt GA vor allem bei mittleren und maximalen Auslastungen signifikante Verbesserungen gegenüber reiner Zufallssuche bei leicht erhöhter Rechenzeit

13.01.2004 26

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Verfahrensvergleich

Implementiert in C , P130; nbmax=500 Vergleich gegenüber Verfahren des selben Autors

„einfache“ Heuristik Bortfeldt(90): signifikant schlechtere Ergebnisse, z.T. mehr als 5% weniger

Volumenauslastung, vor allem bei stark heterogenem Kistenvorrat nur GA erfüllt nur C4 (Stabilität) Rechenzeitvorteil: 4-10

TabuSearch Bortfeldt/Gehring(98): bessere Ergebnisse, im Schnitt 3% fallen monoton mit zunehmender Heterogenität deutlich erhöhte Rechenzeiten GA(Turm) streut weniger, findet häufiger optimale Lösungen

GA Bortfeldt/Gehring(01): mit „Schichtenkonzept“ durchgängig leicht verbesserte Ergebnisse erfüllt alle Restriktionen, C5 nur schwach deutlich erhöhte Rechenzeiten GA(Schicht) streut weniger, aber höhere Anzahl unverstauter

Kisten

13.01.2004 27

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Vergleich zu anderen Autoren: LOH&NEE(92)

15 eigene Probleme Mass für Auslastung auf Basis Frachtrate im Mittel der Beste (Maß!?) GA findet 13 Optima, Loh&Nee 11

NGOI(94) BISCHOFF&RATCLIFF(95)

15 Testfälle zu je 100 numerischen Beispielen Algorithmus für schwach heterogene Kisten GA besser v.a. bei stark heterogenem Vorrat besser Streuung durchgängig erheblich niedriger nur Orientierungsrestriktion

13.01.2004 28

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Illustration Schichtenkonzept

13.01.2004 29

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Kritik I

Annahmen&Idee F2: kann einschränkend sein F1&F2&F3 sollen Verpackungsmaterial einsparen homogener Inhalt der Kisten Minimierung des Stauraumverlustes für Heuristik

fragwürdig Heuristik ist in Richtung Anzahl und Volumen getrimmt Vielleicht: Heuristik entscheidend für Lösungsgüte C5 nur von bedingter Wichtigkeit

Turmkonzept Türme verschlanken nach oben hin horizontale und vertikale Freiräume / „Löcher“ Lückenstabilität C4: Überdeckungen Verschiedene Turmräume existent

13.01.2004 30

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Kritik I

Eckenkonzept Richtung der Befüllung durch „einseitigen“ virtuellen

Container Andere Ordnungen / zufällig initialisiert

GA&Hybridisierung Starke Streuung durch Operatoren und

Wahrscheinlichkeiten Hybridisierung entscheidender Teil

Allgemein Stark heterogener Kistenvorrat überhaupt sinnig für eine

Optimierung?

13.01.2004 31

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Kritik II

Inhaltliches Sicherlich interessanter Ansatz F2 sicherlich nur bedingt einschränkend Turm- und Eckenkonzept machen trotz Komplexität schnelle

Lösungsfindung möglich für schwach homogener Kistenvorrat sicherlich eine

brauchbare Lösung

Formales Arbeit in Anbetracht der notwendigen Aufwandes an

Nomenklaturen übersichtlich und strukturiert Verfahren (eigentlich) direkt aus Arbeit

implementierbar, alle notwendigen Angaben sind vorhanden Testfälle nachvollziehbar

13.01.2004 32

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Verpackungsmaterial?

13.01.2004 33

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Verpackungsmaterial?

13.01.2004 34

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Diskussion

Weitere Fragen?

Vielen Dank für Ihre Aufmerksamkeit

13.01.2004 35

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Literaturverzeichnis

A Genetic Algorithm for Solving the Container Loading ProblemH. Gehring und A. BortfeldtInt. Trans. Opl. Res., Vol.4, No. 5/6, pp. 401-418, 1997

Ein Tabu Search-Verfahren für Containerbeladeprobleme mit schwach heterogenem Kistenvorrat. A. Bortfeldt und H. GehringOR Spektrum, Band 20, S. 237-250, 1998,

A parallel tabu search algorithm for solving the container loading problemH. Gehring und A. BortfeldtDiskussionsbeitrag Nr. 324, Fachbereichs Wirtschaftswissenschaft, FernUniversität Hagen, 2002.

A hybrid genetic algorithm for the container loading problem.A. Bortfeldt und H. GehringEuropean Journal of Opl. Research, Vol. 131 No. 1, pp.143-16, 2001.

Ein verteilt-paralleler genetischer Algorithmus für ContainerbeladeproblemeH. Gehring und A. BortfeldtDiskussionsbeiträge Nr. 271, Fachbereich Wirtschaftswissenschaften, FernUniversität Hagen, 1999

13.01.2004 36

Einleitung

Umsetzung

Ergebnisse, Test, Kritik

Diskussion

Literaturverzeichnis

Das ContainerbeladeproblemMax SchäferUniversität Saarbrücken, Seminar Evolutionäre Algorithmen / Genetisches Progammieren, WS 97/98

Cutting and Packing in Production and DistributionH. Dyckhoff und U. FinkePhysica-Verlag 1992

How to Solve It: Modern HeuristicsZ. Michalewicz und D. FogelSpringer,2002