Das Ziel des packing besteht darin, die beste Möglichkeit zu finden, eine Gruppe von Elementen bestimmter Größen in Behälter mit festen packing zu verpacken. Eine typische Anwendung ist das effiziente Beladen von Kartons auf Lieferwagen. Aufgrund von Kapazitätseinschränkungen ist es oft nicht möglich, alle Artikel zu verpacken. In diesem Fall besteht das Problem darin, eine Teilmenge der Elemente mit einer maximalen Gesamtgröße zu finden, die in die Container passt.
Es gibt viele Arten von Verpackungsproblemen. Die beiden wichtigsten sind Probleme mit Rucksack und Bin-Packing.
Probleme mit Rucksack
Bei dem einfachen Rucksackproblem handelt es sich um einen einzelnen Behälter (einen Rucksack). Die Artikel haben sowohl Werte als auch Größen und das Ziel ist, eine Teilmenge der Artikel mit dem maximalen Gesamtwert zu verpacken.
Im Sonderfall, in dem der Wert gleich der Größe ist, besteht das Ziel darin, die Gesamtgröße der verpackten Artikel zu maximieren.
OR-Tools bietet in seiner Algorithmusbibliothek mehrere Solver für Rucksackprobleme.
Es gibt auch allgemeinere Versionen des Rucksackproblems. Hier einige Beispiele:
Mehrdimensionale Rucksackprobleme, bei denen die Artikel mehr als eine physische Menge haben, z. B. Gewicht und Volumen, und der Rucksack eine Kapazität für jede Menge hat. Der Begriff Dimension bezieht sich hier nicht unbedingt auf die üblichen räumlichen Abmessungen Höhe, Länge und Breite. Zu den Problemen können jedoch räumliche Dimensionen gehören, z. B. die Suche nach der optimalen Methode, rechteckige Verpackungen in einen rechteckigen Aufbewahrungsbehälter zu verpacken.
Mehrere Rucksackprobleme, bei denen es mehrere Rucksäcke gibt und das Ziel darin besteht, den Gesamtwert der verpackten Gegenstände in allen Rucksäcken zu maximieren.
Beachten Sie, dass Sie ein mehrdimensionales Problem mit einem einzelnen Rucksack oder ein Problem mit mehreren Rucksacken mit nur einer Dimension haben können.
Das Bin-Packing-Problem
Eines der bekanntesten Verpackungsprobleme ist das bin-packing, bei dem es mehrere Container (sogenannte bin-packing) mit gleicher Kapazität gibt. Im Gegensatz zum Problem mit mehreren Rucksacken wird die Anzahl der Container nicht festgelegt. Stattdessen besteht das Ziel darin, die kleinste Anzahl von Klassen für alle Elemente zu finden.
Hier ist ein einfaches Beispiel, um den Unterschied zwischen dem Problem mit mehreren Rucksacken und dem Behälterproblem zu veranschaulichen. Angenommen, ein Unternehmen hat Lieferwagen, die jeweils eine Kapazität von 18.000 Pfund und 130.000 Pfund zu liefernde Artikel haben.
Mehrere Rucksäcke: Sie haben fünf Lkws und möchten eine Teilmenge der Elemente mit maximalem Gewicht auf ihnen laden.
Behälter packen: Sie haben 20 Lkw (mehr als genug, um alle Gegenstände zu verpacken) und möchten die wenigen Lkws nutzen, die alle Platz bieten.
In den folgenden Abschnitten wird beschrieben, wie Sie verschiedene Arten von Verpackungsproblemen mit ODER-Tools lösen, beginnend mit dem Rucksackproblem.