Zagnieżdżanie maksymalnej liczby kształtów na powierzchni

Question

W przemyśle często występuje problem polegający na konieczności obliczenia najbardziej efektywnego wykorzystania materiału, np. Tkaniny, drewna, metalu itd. Punktem wyjścia jest X ilość kształtów podane wymiary, wykonane z wielokątów i/lub zakrzywionych linii, a celem jest inny wielokąt o podanych wymiarach.

Zakładam, że wiele z obecnych zestawów CAM to implementuje, ale nie mając doświadczenia z ich używaniem lub ich wbudowanymi, jaki algorytm obliczeniowy jest wykorzystywany do znalezienia najbardziej efektywnego wykorzystania przestrzeni? Czy ktoś może wskazać mi książkę lub inne odniesienie, które omawia ten temat?

Answer 1

Po Andrew w jego odpowiedzi wskazał mnie we właściwym kierunku i nazwał problem dla mnie, postanowiłem zrzucić moje wyniki badań tutaj w oddzielnym odpowiedź.

To rzeczywiście jest problem z pakowaniem, a mówiąc dokładniej, jest to problem z zagnieżdżaniem. Problem jest matematycznie NP-trudny, a zatem obecnie używane algorytmy są podejściami heurystycznymi. Wydaje się, że nie istnieją rozwiązania, które rozwiązałyby problem w czasie liniowym, z wyjątkiem prostych zestawów problemów. Rozwiązywanie złożonych problemów trwa od kilku minut do kilku godzin przy użyciu aktualnego sprzętu, jeśli chcesz uzyskać rozwiązanie z dobrym wykorzystaniem materiałów. Istnieje kilkadziesiąt komercyjnych rozwiązań programowych, które oferują zagnieżdżanie kształtów, ale nie byłem w stanie zlokalizować żadnych rozwiązań open source, więc nie ma prawdziwych przykładów, w których można zobaczyć algorytmy faktycznie zaimplementowane.

Doskonały opis problemu zagnieżdżania i rozplątywania pasków za pomocą rozwiązań historycznych można znaleźć w artykule Benny'ego Kjæra Nielsena z Uniwersytetu w Kopenhadze (Nielsen).

Ogólne podejście polega na łączeniu i użyciu wielu znanych algorytmów w celu znalezienia najlepszego rozwiązania do zagnieżdżania. Algorytmy te obejmują (Guided/powtórzyć) Lokalne wyszukiwanie, Szybkie wyszukiwanie sąsiedztwa, która jest oparta na No-Fit wielokąt i przepychanki analizy heurystycznej. Znalazłem świetny artykuł na ten temat ze zdjęciami na temat działania algorytmów. Miał także benchmarki różnych wdrożeń oprogramowania do tej pory. Artykuł ten został zaprezentowany na Międzynarodowym Sympozjum poświęconym planowaniu 2006 roku przez S. Umetaniego i innych (Umetani).

stosunkowo nowe i możliwie najlepsze podejście do tej pory jest na podstawie hybrydowego algorytmu genetycznego (HGA) hybrydowe składające się z symulowaną denaturację i algorytmu genetycznego który opisali Wu Qingming i wsp. Z Wuhan University (Quanming). Zaimplementowali to za pomocą Visual Studio, bazy danych SQL i zestawu narzędzi do optymalizacji algorytmów genetycznych (GAOT) w MatLab.

Answer 2

Masz na myśli dobrze znaną dziedzinę informatyki pakowania, dla której zdefiniowano wiele różnych problemów i badań, zarówno dla przestrzeni 2-wymiarowej, jak i przestrzeni trójwymiarowej.

W sieci dostępnych jest wiele materiałów, które mogą pomóc w rozwiązaniu zdefiniowanych problemów, ale aby znaleźć to urządzenie, trzeba znać nazwę problemu, który należy wyszukać.

Niektóre pakiety mogą przyjąć heurystyczną aplikację (co podejrzewam, że będą), a niektóre z nich mogą przejść do długości obliczania wszystkich możliwości uzyskania absolutnej właściwej odpowiedzi.

http://en.wikipedia.org/wiki/Packing_problem