Algorytmy pakowania trójwymiarowego

Question

Mam do czynienia z problemem 3-wymiarowego pakowania bin i obecnie prowadzę pewne wstępne badania, które algorytmy/heurystyki są obecnie przynoszące najlepsze wyniki. Ponieważ problem jest NP trudny, nie oczekuję optymalnego rozwiązania w każdym przypadku, ale zastanawiałem się:

1) jakie są najlepsze dokładne rozwiązania? Branch and Bound? Jakie problemy z rozmiarami wystąpień mogę rozwiązać przy użyciu rozsądnych zasobów obliczeniowych?
2) jakie są najlepsze rozwiązania heurystyczne?
3) Jakie istnieją gotowe rozwiązania do przeprowadzenia eksperymentów?

Answer 1

Od wikipedia:

Chociaż these simple strategies często są wystarczająco dobre, wydajne algorytmy aproksymacji wykazano, że może rozwiązać problem pakowania bin w dowolnej ustalonej procentowo w stosunku do optymalnego rozwiązania dla dostatecznie dużych nakładów

Oto dwa źródła, które dają:

• Approximation Algorithms
• Bin packing can be solved within 1 + ε in linear time

Answer 2

miarę gotowych rozwiązań, sprawdź MAXLOADPRO do załadunku samochodów ciężarowych. Może on być skonfigurowany do ładowania dowolnej prostokątnej objętości, ale jeszcze tego nie próbowałem. Zasadniczo problemy z pakowaniem w 3d mają dodatkowe komplikacje, że obiekty można obracać w różnych pozycjach, więc dla każdego obiektu o zadanej długości, szerokości i wysokości trzeba efektywnie utworzyć trzy zmienne reprezentujące każdą pozycję, ale używa się tylko jednego. rozwiązanie.

Generalnie, samodzielne formuły MIP (lub branch and bound) nie działają dobrze w przypadku problemu 2d lub 3d, ale programowanie z ograniczeniami napotkało na pewien sukces, tworząc dokładne rozwiązania problemu 2d. Sprawdź to abstract. Nie patrząc na papier, podoba mi się podejście do rozkładu problemu, w którym próbujesz zminimalizować liczbę pojemników o tym samym rozmiarze. Nie widziałem tylu rezultatów dla problemu 3d, ale daj nam znać, jeśli znajdziesz coś, co można zrealizować.

Powodzenia!

Answer 3

ty pytanie jest podobny do: 3d bin packing algorithm

Mimo, bo dis-umożliwić obrót, można uzyskać bardzo dobre wyniki. Sugeruję, aby bardziej skupić się na rozwiązaniu FIRST-FIT-DECREASING.

Answer 4

Najlepsze rozwiązanie: użyj dynamic programming.

Zmienne stanu

:

1. Pracuj zostały zapakowane i odrzucono.
2. Miejsce wypełnione w pojemniku.

Jeśli pojemnik jest równoległościenną siatką, a elementy "pasują" do dokładnych komórek siatki, można użyć trójwymiarowej tablicy do przedstawienia zmiennej stanu 2.W przeciwnym razie będziesz musiał użyć bardziej złożonych struktur danych.

Najlepsze heurystyczne rozwiązują

ja nie wiem. Być może Variable Neighborhood Search. Istnieje kilka podobieństw między twoim problemem a problemem budowy rozkładu jazdy (nad którym pracuję), więc ta sama heurystyka może być korzystna dla obu.

off-the-shelf rozwiązań do przeprowadzania eksperymentów

Przepraszam, ja nawet nie mają pojęcia.

Answer 5

Napisałem program, który testuje trzy różne algorytmy. Jest to również dobre źródło informacji: A Thousand Ways to Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing. Jest on przeznaczony do dwuwymiarowego pojemnika prostokątnego, ale zawsze można go przekształcić na 3D.

Answer 6

3dbinpacking jest komercyjnym rozwiązaniem (nie jest algorytmem) narażającym API na konsumpcję z ładną wizualizacją. Oferuje on:

• bin Pojedyncze pakowanie
• Wielu bin pakowania
• Znajdź trzeci wymiar
• Znajdź A Wymiary bin