Verschachteln der maximalen Anzahl von Formen auf einer Oberfläche

Question

In der Industrie gibt es oft ein Problem, wo Sie den effizientesten Materialverbrauch berechnen müssen, sei es Stoff, Holz, Metall usw. Der Ausgangspunkt ist X Anzahl der Formen von gegebene Dimensionen, die aus Polygonen und/oder gekrümmten Linien bestehen, und Ziel ist ein anderes Polygon mit gegebenen Dimensionen.

Ich nehme an, viele der aktuellen CAM-Suiten implementieren dies, aber keine Erfahrung mit ihnen oder ihrer Interna, welche Art von Computeralgorithmus wird verwendet, um die effizienteste Nutzung von Raum zu finden? Kann mich jemand auf ein Buch oder eine andere Referenz verweisen, die dieses Thema behandelt?

Answer 1

Nachdem Andrew in seiner Antwort mich in der richtigen Richtung und das Problem für mich genannt, habe ich beschlossen, meine Forschungsergebnisse hier in einer separaten Antwort auszugeben.

Dies ist in der Tat ein Verpackungsproblem, und um genau zu sein, ist es ein Verschachtelungsproblem. Das Problem ist mathematisch NP-schwer und daher sind die derzeit verwendeten Algorithmen heuristische Ansätze. Es scheint keine Lösungen zu geben, die das Problem in linearer Zeit lösen würden, außer für triviale Problemmengen. Die Lösung komplexer Probleme dauert mit der aktuellen Hardware Minuten bis Stunden, wenn Sie eine Lösung mit guter Materialausnutzung erreichen möchten. Es gibt Dutzende kommerzieller Softwarelösungen, die das Verschachteln von Formen anbieten, aber ich konnte keine Open-Source-Lösungen finden, daher gibt es keine realen Beispiele, bei denen man die tatsächlich implementierten Algorithmen sehen könnte.

Eine ausgezeichnete Beschreibung des Nesting- und Strip-Nesting-Problems mit historischen Lösungen findet sich in einem Papier von Benny Kjær Nielsen von der Universität Kopenhagen (Nielsen).

Allgemeiner Ansatz scheint zu sein, mehrere bekannte Algorithmen zu mischen und zu verwenden, um die beste Verschachtelungslösung zu finden. Diese Algorithmen sind (Guided/Iterated) Lokale Suche, Schnell Neighborhood Search, die auf No-Fit Polygon und Drängeln Heuristiken basiert. Ich fand eine großartige Arbeit zu diesem Thema mit Bildern, wie die Algorithmen funktionieren. Es hatte auch Benchmarks der verschiedenen Software-Implementierungen bisher. Dieses Papier wurde auf dem International Symposium on Scheduling 2006 von S. Umetani et al. (Umetani) vorgestellt.

Eine relativ neue und möglicherweise der beste Ansatz bisher basiert auf Hybrid genetischen Algorithmus (HGA), ein Hybrid aus Simulated Annealing bestehend und genetischen Algorithmus, die von beschrieben wurde Wu Qingming und Mitarbeiter der Universität Wuhan (Quanming). Sie haben dies implementiert, indem sie Visual Studio, SQL-Datenbank und Genetic Algorithm Optimization Toolbox (GAOT) in MatLab verwenden.

Answer 2

Sie beziehen sich auf eine wohlbekannte Informatikdomäne der Packung, für die eine Vielzahl von Problemen definiert und erforscht wurde, sowohl für den 2-dimensionalen Raum als auch für den 3-dimensionalen Raum.

Es gibt beträchtliches Material im Netz, das für die definierten Probleme zur Verfügung steht, aber um es zu finden, müssen Sie den Namen des zu suchenden Problems kennen.

Einige Pakete könnten eine heuristische Appraoch (die ich vermute, dass sie es wird) übernehmen und einige könnten die Möglichkeiten der Berechnung aller Möglichkeiten, um die absolut richtige Antwort zu erhalten, übernehmen.

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