Celem problemów z packing jest znalezienie najlepszego sposobu zapakowania zestawu produktów o określonych rozmiarach do pojemników o stałej packing. Typowe zastosowanie to wydajne załadowywanie pojemników na ciężarówki. Często nie można zapakować wszystkich produktów ze względu na ograniczenia pojemności. W takim przypadku problemem jest znalezienie podzbioru produktów o maksymalnym całkowitym rozmiarze, które będą pasować do kontenerów.
Jest wiele rodzajów problemów z pakowaniem. Do 2 najważniejszych czynników należą problemy z plecakiem oraz pakowanie pojemników.
Problemy z Knapsack
W ramach prostego zadania plecaka występuje tylko jeden kontener (plecak). Elementy mają zarówno wartości, jak i rozmiary. Celem jest spakowanie podzbioru produktów o maksymalnej łącznej wartości.
W szczególnych przypadkach, gdy wartość jest równa rozmiarowi, celem jest zmaksymalizowanie całkowitego rozmiaru wypakowanych produktów.
W bibliotece algorytmów OR-Tools udostępnia kilka rozwiązań do rozwiązywania problemów knapsack.
Istnieją też bardziej ogólne wersje problemu plecaków. Oto kilka przykładów:
Wielowymiarowe zadania z plecakiem, w których przedmioty mają więcej niż jedną wielkość fizyczną, np. wagę i objętość, a pojemność plecaka jest pojemna dla każdej liczby sztuk. W tym przypadku termin wymiar niekoniecznie odnosi się do typowych wymiarów przestrzennych: wysokości, długości i szerokości. Niektóre problemy mogą jednak obejmować wymiary przestrzenne, na przykład znalezienie optymalnego sposobu pakowania prostokątnych pudełek do prostokątnego pojemnika.
Wiele problemów związanych z paczkami, w których jest wiele plecaków, a celem jest zmaksymalizowanie łącznej wartości zapakowanych przedmiotów we wszystkich plecakach.
Pamiętaj, że możesz mieć wielowymiarowy problem z jednym plecakiem lub z kilkoma z nimi obejmującymi tylko jeden wymiar.
Problem z pakowaniem
Jednym z najbardziej znanych problemów z pakowaniem jest bin-packing, w którym występuje wiele pojemników (nazywanych bin-packing) o jednakowej pojemności. W przeciwieństwie do problemu wielu plecaków liczba pojemników nie jest stała. Celem jest znalezienie jak najmniejszej liczby kontenerów, w których mieszczą się wszystkie elementy.
Oto prosty przykład ilustrujący różnicę między problemem z wieloma plecakami a pakowaniem opakowań. Załóżmy, że pewna firma ma ciężarówki, z których każda waży 540 kg wagę i 50 tys. funtów towarów do dostarczenia.
Wiele plecaków: masz pięć ciężarówek i chcesz wczytać podzbiór elementów o maksymalnej wadze.
Pakowanie ciężarówek: masz 20 ciężarówek (a to im wystarczy, by pomieścić wszystkie przedmioty) i chcesz użyć jak najmniejszej liczby ciężarówek, które zmieści się wszystkie.
W tych sekcjach znajdziesz rozwiązania różnych problemów z pakowaniem, począwszy od zadania plecaka za pomocą narzędzi typu LUB.