Metaheuristiken zur Lösung von Standardproblemen des Cutting and Packing

Mack, Daniel GND

Mehrdimensionale Cutting and Packing- (C&P-) Probleme gelten als besonders schwierige kombinatorische Optimierungsprobleme. Im Rahmen dieser Dissertation werden fünf Verfahren für Problemstellungen des C&P mit quaderförmigen Packstücken (Items) vorgestellt. Die Ergebnisse der vorliegenden Arbeit können wie folgt zusammengefasst werden. In der Literatur werden bevorzugt Metaheuristiken zur Lösung von C&P-Problemen verwendet. Allerdings sind bisher nur wenige Versuche bekannt, die Metaheuristik Simulated Annealing (SA) einzusetzen. In einem Verfahren dieser Arbeit wird SA neben Tabu Search (TS) als Nachbarschaftsverfahren angewendet. Die Integration von SA und TS zu einem neuen hybriden Ansatz und dessen anschließende Parallelisierung führt zudem zu sehr guten Resultaten, wie umfangreiche Tests belegen. Die Fragestellungen des Container Loading, Strip Packing und Bin Packing stehen in einem engen inneren Zusammenhang. Im Rahmen dieser Arbeit wird dies gezeigt, indem ein bestehendes Branch and Bound-Verfahren für das Containerbeladeproblem schrittweise zunächst zu einem Strip Packing-Verfahren und anschließend zu einem Bin Packing-Verfahren ausgebaut wird. Der verwendete Erweiterungsansatz lässt sich auf beliebige schichtbildende Verfahren verallgemeinern, bei denen ein Container mit separaten, vertikalen Schichten aus je einigen Stücken gefüllt wird. Die für mehrdimensionale C&P-Probleme in der Literatur angebotenen Benchmarkinstanzen sind meist von bescheidener Größe und umfassen im dreidimensionalen (3D) Fall meist nicht mehr als 200 Items. Zudem ist das Optimum meist unbekannt, was die Bewertung von Verfahren zusätzlich erschwert. Im Rahmen dieser Dissertation wird daher ein Instanzgenerator für mehrdimensionale C&P-Probleme beliebiger Größe mit bekanntem Optimum entworfen und angewendet. Neue zwei- und dreidimensionale Benchmarkinstanzen von bisher nicht gekannter Größe und teilweise mit bekanntem Optimum werden eingeführt und gelöst. So werden unter anderem 600 neue Testinstanzen mit bekanntem Optimum und 200 Items für das Strip Packing-Problem (SPP) verwendet, neben größeren neuen SPP-Instanzen mit 1.000 Items, welche aus den Packproblemen von BISCHOFF und RATCLIFF (1995) abgeleitet werden. Außerdem werden 1800 neue Instanzen für das Bin Packing-Problem mit durchschnittlich mehr als 1500 Packstücken eingeführt. Neben der Dimensionalität werden dabei auch die relative Packstückgröße sowie die Heterogenität der Packstückmenge systematisch variiert. Alle fünf Verfahren wurden in den Jahren 2003 bis 2009 entworfen. Insbesondere das bereits 2004 vorgestellte parallel-hybride Verfahren für das Containerbeladeproblem blieb bis zum Jahre 2008 ungeschlagen für schwach heterogene Benchmarkinstanzen.

Vorschau

Zitieren

Zitierform:

Mack, Daniel: Metaheuristiken zur Lösung von Standardproblemen des Cutting and Packing. Hagen 2011. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt

Volltextzugriffe:
Metadatenansicht:

12 Monate

Volltextzugriffe:
Metadatenansicht:

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export

powered by MyCoRe