Algorytm pakowania 3d dla wysyłki przedmiotu

Otrzymałem zadanie zbudowania prognozy wysyłki, która sugeruje najlepsze zakwaterowanie towarów na jak najmniejszej liczbie pudełek:

1. Istnieje skończony zestaw znanych rozmiarów prostokątnych pudełek

2. Istnieje wiele dowolnych prostokątnych przedmiotów, które należy zapakować w pudełka

3. Im mniej pól, tym lepiej. Ponieważ wysyłka dwóch pudeł 1x1x1 jest znacznie droższa niż jedno pudełko 1x2x1. To powinno być tutaj priorytetem.

4. Należy również zoptymalizować korzystanie z mniejszych skrzynek, jak to możliwe, jako priorytet drugiego poziomu. (np .: jeśli jest oferowany wybór między jednym większym pudełkiem a dwoma małymi, powinien wybrać większe pudełko)

5. Elementy można obracać, aby pasowały do ​​pudełka, ale obrót musi być ograniczony do przyrostów co najmniej 45 ° (w moich badaniach wydaje się, że niektóre konfiguracje pozwalają na obrót o 45 stopni, aby lepiej dopasować prostokątne pudełka do większego prostokątnego pudełka) , a mianowicie obrót o 90 °.

6. Pudełka mają limit wagi, a przedmioty mają dowolną wagę (np .: przedmiot o rozmiarze 1x1x1 może być cięższy niż inny przedmiot 2x2x2)

Trochę przestudiowałem i znalazłem kilka abstrakcyjnych algorytmów dotyczących pakowania bin i problemu z plecakiem, i otrzymałem następującą nieco brutalną siłę, podobną do algorytmu najlepszego dopasowania:

1. Posortuj elementy w malejącej kolejności objętości (najpierw większe) na liście „elementów do spakowania”

2. Dla każdego elementu na tej liście:

   1. Wybierz mniejsze pudełko, które znajduje się na liście „używane pudełka” i ma wystarczającą ilość pozostałego limitu objętości i wagi, aby zmieścić przedmiot (użyję dopasowania tutaj, aby dopasować wymiary i wagę)

   2. Jeśli nie ma takiego pudełka, utwórz nowe pudełko ze znanego zestawu możliwych rozmiarów pudeł, który jest najmniejszym rozmiarem, który może pasować do wymiarów i wagi przedmiotu i dodaj go do listy „używanych pudeł”.

   3. Jeśli pudełko pasuje do elementu (używając funkcji dopasowania poniżej), dodaj go do listy „elementów tego pudełka” i usuń go z listy „elementów do dopasowania”, zaznaczając jego względną pozycję 3d wewnątrz pudełka.

   4. Powtarzaj od 2.1, aż na liście „elementów do spakowania” nie będzie żadnego elementu do zamontowania.

Funkcja kontroli dopasowania używana w kroku 2 powyżej:

1. Sprawdź, czy pozostała objętość pudełka pasuje do objętości przedmiotu. Jeśli nie, zwróć false.

2. Sprawdź, czy suma masy „elementów pudełka” plus bieżąca waga przedmiotu jest mniejsza lub równa limitowi wagi pudełka. Jeśli nie, zwróć false.

3. Sprawdź listę „elementów pudełka”, aby wybrać pierwszą współrzędną pudełka, która ma najmniejszy komponent Y i która ma wystarczająco dużo miejsca na szerokość, głębokość i wysokość elementu, biorąc pod uwagę inne elementy umieszczone jako niedostępne miejsce.

4. Jeśli element nie pasuje w bieżącej orientacji, obróć go o jeden z 6 możliwych obrotów, nie przyjmując dla uproszczenia obrotu o 45 °. (Obroty, których wynikiem są rozmiary, które już przetestowane można pominąć. Np .: obrócenie pudełka o 180 ° daje takie same wymiary jak pozycja pierwotna, ponieważ wszystkie pudełka i przedmioty mają ten sam rozmiar dla przeciwległych ścian i dlatego można je pominąć.)

5. Jeśli element nie został obrócony wszystkimi możliwymi sposobami powrotu do pierwotnej orientacji, spróbuj ponownie od kroku 3.

6. Jeśli wszystkie obroty były sprawdzone i nie znaleziono dopasowania, rozważ bieżącą współrzędną jako niedostępną przestrzeń.

7. Jeśli nie ma dostępnego miejsca do sprawdzenia, zwróć false. W przeciwnym razie spróbuj ponownie od kroku 3.

Chcę wiedzieć, czy istnieje najlepsze rozwiązanie mojego problemu, biorąc pod uwagę przedstawione ograniczenia.

To wydaje się działać na teorii, ale nie próbowałem tego na kodzie. Chciałbym wiedzieć, czy idę w dobrym kierunku, czy są lepsze, wydajniejsze sposoby na zrobienie tego.

Referencje byłyby świetne.

Edytować:

Znalazłem interesujący interfejs API innej firmy, który robi to, co chcę, ale będzie musiał zostać odłączony, aby nie mieć do nich dostępu.

Oto niektóre przykłady:

• http://v2.3dbinpacking.com/demo/main
• http://www.packit4me.com/api

Edycja 2:

Przykładem rzeczywistego problemu do rozwiązania byłoby:

• Posiadam 4 rozmiary pudeł WxHxD: 10x12x18, 12x16x24, 16x20x30, 24x32x40
• Mam zamówienie na 4 przedmioty, czyli 1 o rozmiarze 6x8x10, 2x 22x14x30 i 1x 22x4x20

Jak dopasować te elementy do dowolnej liczby pudeł o jednym lub większej liczbie rozmiarów, używając jak najmniejszej liczby pudełek, używając możliwie najmniejszych pudeł i pozostawiając możliwie najmniej wolnego miejsca?

Pakowanie pojemników jest bardzo trudne obliczeniowo. Pomyśl o połowie problemu: chcesz zapakować produkt w pudła transportowe bez marnowania w pudełku. Optymalne rozwiązanie tego wymagałoby przejścia przez wszystkie możliwe podzestawy i wszystkie możliwe układy 3D produktu, który musi być wysyłany w jednej ciężarówce. Dam ci optymalne rozwiązanie, ponieważ mam przyjaciela, który robi sześć niemożliwych rzeczy przed śniadaniem.

Teraz musisz tylko zabrać wszystkie pudła do ciężarówki bez marnotrawstwa. Mój przyjaciel robi swoją drugą niemożliwą rzecz i daje ci rozwiązanie. Niestety przy wybranych powyżej rozmiarach skrzynek w ciężarówce jest pusta przestrzeń, którą można by zmniejszyć, gdybyś wybrał inne (większe lub mniejsze) pudła w pierwszym zadaniu. Jeśli zmienisz rozmiar jednego pudełka, w najlepszym razie będziesz musiał ponownie zapakować ciężarówkę; w najgorszym wypadku może być konieczne przepakowanie wszystkich pudełek, co jest równie trudne, jak problem, z którym zaczęliśmy. I podobnie jak w przypadku pierwszego etapu, musisz wypróbować wszystkie możliwe aranżacje 3D.

Uważam, że Podręcznik projektowania algorytmów Skieny był pomocny przy zastanawianiu się, jaka klasa algorytmów pasuje do danego rodzaju problemów, ale przede wszystkim dowiedziałam się, że dobre rozwiązania nawet przyziemnych problemów pojawiają się w obliczu trudności obliczeniowych. Większość tego, czego potrzebujesz, mieści się w klasie problemów związanych z pakowaniem pojemników, a ten artykuł jest dobrym punktem wyjścia. Warto zauważyć, że jednymi z najlepszych algorytmów do tego są produkty komercyjne, ponieważ zadanie to pojawia się wszędzie w logistyce (do jakiej najmniejszej liczby wagonów kolejowych mogę dostać moje towary? I tak dalej). Jeśli właściwa heurystyka może zaoszczędzić producentowi 100 wagonów miesięcznie, trzeba zarobić znaczne pieniądze.

Niestety literatura na temat optymalizacji heurystyki nie jest tak duża jak na algorytmy. Jeśli spróbujesz to zrobić sam, gwarantuję, że do drugiego miesiąca będziesz śnić o przesuwaniu prostokątnych pryzmatów. Miałem problem z nowymi rozwiązaniami, który gdybym musiał to zrobić ponownie, prawdopodobnie zwróciłbym się do ekspertów (lub ich oprogramowania).

Dzięki @JTrana za doskonałe rozwinięcie mojego komentarza.

Tworząc nowe algorytmy, a ostatnio zrobiłem sam algorytm pakujący (wiem, że wciąż ma on pewien potencjał optymalizacji), zawsze stosuję najprostsze podejście:

Jak miałbym to zrobić jako człowiek i spróbować przetłumaczyć go na algorytm: od mojego nauczyciela (robotyki) AI Rolfa Pfeifer Nadal pamiętam, że pozorna inteligencja może być czasami tworzona na podstawie bardzo prostych reguł, więc zamiast nadinżynierii Staram się unerengineer

1. Zidentyfikuj zbyt duże przedmioty (przedmioty, które nie mieszczą się w danym polu)
2. Spróbuj znaleźć najlepsze możliwe pudełko (porównując całkowitą objętość i wymiary przedmiotu)
3. Zamawiaj przedmioty od dużych do małych oraz pudełka (spacje) od małych do dużych
4. Dopasuj największy przedmiot do możliwie najmniejszej przestrzeni
5. Jeśli największy przedmiot nie znajdzie, przeskocz nad nim i spróbuj następnego, aż nic więcej się nie zmieści

6. Dla pozostałych elementów wyszukaj nowe najlepsze pole. ...

   X. zawsze myśl o wyjątkowych zdarzeniach (przedmioty o dużych rozmiarach, dziwne formy, jeśli pudełko zawiera tylko 1 przedmiot, czy nie byłoby lepiej wysłać przedmiot bez pudełka? Itp.), Ale możesz zrobić heurystykę również w formie decyzji drzewo.

Oczywiście są jeszcze inne zastrzeżenia, im dalej dostaniesz, podaję te pomysły jako punkt wyjścia. Stamtąd istnieje wiele sposobów. Jedną z możliwości byłoby podzielenie pudełka na małe kostki (np. 5 cm x 5 cm x 5 cm) i śledzenie ich jako zajęte / wolne, inne podejście można nazwać 3d tetris itp.

Dzięki takiemu podejściu niekoniecznie musisz się martwić o wybuch kombinacyjny. Z drugiej strony eksplozja kombinacyjna może się zdarzyć, jeśli mówimy o mnóstwie przedmiotów, ale z drugiej strony: czy naprawdę sądzisz, że firma sprawdzi listę pakowania pozycji po pozycji? Nie, podchodzą do rozwiązania typu dziel i zwyciężaj: Podziel złożoność, używając standardowych woluminów (np. Palet lub pudeł o stałej wielkości). Więc nawet ze względów praktycznych, weź pod uwagę, że nie tylko pociągi, czasem czas pracownika to także pieniądze. pociąg może załadować x palet, każda paleta ma ustaloną objętość, więc pakuj elementy do palety, ale z drugiej strony być może paleta składa się z kilku rzędów, więc używaj stałych pól dla przedmiotów, które następnie są ładowane do palet, a następnie ładowane do pociągów.

Przynajmniej tak ja jako człowiek poradziłbym sobie z tym zadaniem, otrzymałem najlepsze pudełko, a następnie dopasowałem jeden po drugim największy przedmiot na najmniejszej dostępnej przestrzeni (i dodałem trochę podglądu).

Tak jak w moim algorytmie, ostatecznie prawdopodobnie nie będziesz miał najlepszego rozwiązania, ale zdecydowanie dobrą heurystykę, którą następnie możesz dopracować.

Czasami łatwiej jest zacząć od pierwszego kroku i usunąć problemy na swojej drodze, oczywiście oczywiście nie jest to krok ponad krawędź, ale trochę sprytny ... czasami możesz zostać zmuszony do poszukiwania alternatyw i wyboru najlepszy lub zaimplementuj „krok wstecz”.

Ale jak dowiedziałem się od mojego nauczyciela AI (Rolf Pfeifer, przepraszam, że zawracam sobie tym głowę): Czasami możesz stworzyć pozorne inteligentne zachowanie z kilkoma bardzo prostymi i kilkoma zestawami reguł> zachowaniem wschodzącym w podanym przykładzie, zaprogramowali małe odległe samochody, aby skręcały w lewo, jeśli wykrywają przeszkodę po prawej stronie, skręcają w prawo, jeśli jest przeszkoda po lewej stronie, i jeżdżą prosto, jeśli nie ma przeszkody lub przeszkoda jest z przodu. 3 lub 4 roboty umieszczone w kwadracie o wymiarach 3 x 3 m z dużą ilością piłek do ping-ponga prowadzą do niesamowitego faktu, że roboty sprzątają, pchając piłki do ping-ponga do rogów, nawet jeśli roboty są zaprogramowane tylko w celu uniknięcia przeszkód.

PD: Jedynym odchyleniem w świecie rzeczywistym, które znalazłem w tym podejściu, było to, że pracowałem w niepełnym wymiarze godzin jako pomocnik podczas dużych koncertów, takich jak Metallica, Iron Maiden, Britney Spears, Paul McCartney, U, to nazwa ... Kierowcy ciężarówek pracujący na międzynarodowe wycieczki mają dokładne listy pakowania pozycja po pozycji. Obliczenia są wykonywane raz (nie wiem przez ludzi lub maszyny), a następnie powielane. Czasami, gdy pakują się po raz pierwszy, robią nawet zdjęcia warstwa po warstwie i umieszczają je w ciężarówce, aby lokalne załogi dokładnie wiedziały, które pudełko należy naładować, kiedy i gdzie. Ale jest to również specyficzna potrzeba pakowania, ponieważ podczas jednej wycieczki zawsze pracują z tymi samymi skrzyniami i ciężarówkami.

Heurystyka, o której wspomniałeś w swoim poście, wydaje się interesująca.

Sugerowałbym kilka modyfikacji w celu ulepszenia ostatecznego rozwiązania.

Biorąc pod uwagę rozwiązanie, w którym wszystkie przedmioty są zapakowane w jednym pudełku, spróbuj połączyć zawartość dwóch małych pudełek w jednym większym pudełku (powinno to pomóc w poprawieniu kryteriów korzystania z jak najmniejszej liczby pudełek).

Alternatywnie, za każdym razem, gdy uruchamiasz nowe pudełko, zamiast używać najmniejszego pudełka, które może pomieścić bieżący element, możesz wybrać największe pudełko, które może go pomieścić, a po przypisaniu każdego elementu do pudełka spróbuj przypisać wszystkie elementy pudełko do mniejszego pudełka.

Ponadto, w funkcji dopasowania, zamiast uważać położenie innych skrzynek za ustalone, można wyobrazić sobie zmianę sekwencji ładowania. To powinno pozwolić Ci znaleźć lepsze rozwiązania kosztem dłuższego czasu pracy.