Anidamiento de la cantidad máxima de formas en una superficie

Question

En la industria, a menudo hay un problema donde se necesita calcular el uso más eficiente del material, ya sea de tela, madera, metal, etc. El punto de partida es X cantidad de formas de dimensiones dadas, hechas de polígonos y/o líneas curvas, y el objetivo es otro polígono de dimensiones determinadas.

Supongo que muchas de las suites CAM actuales implementan esto, pero al no tener experiencia en el uso de ellas o de sus partes internas, ¿qué tipo de algoritmo computacional se usa para encontrar el uso más eficiente del espacio? ¿Puede alguien señalarme un libro u otra referencia que discuta este tema?

Answer 1

Después de Andrew en su respuesta me señaló la dirección correcta y nombró el problema para mí, decidí volcar los resultados de mi investigación aquí en una respuesta por separado.

Esto es realmente un problema de embalaje, y para ser más precisos, es un problema de anidamiento. El problema matemáticamente es NP-hard, y por lo tanto los algoritmos que se usan actualmente son enfoques heurísticos. No parece haber soluciones que resuelvan el problema en tiempo lineal, excepto por conjuntos de problemas triviales. La solución de problemas complejos lleva de minutos a horas con el hardware actual, si desea lograr una solución con una buena utilización del material. Existen decenas de soluciones de software comerciales que ofrecen formas anidadas, pero no pude encontrar ninguna solución de código abierto, por lo que no hay ejemplos reales en los que se puedan ver los algoritmos realmente implementados.

Puede encontrar una excelente descripción del problema de anidamiento y anidamiento de tiras con soluciones históricas en un documento escrito por Benny Kjær Nielsen de la Universidad de Copenhague (Nielsen).

El enfoque general parece ser mezclar y usar múltiples algoritmos conocidos para encontrar la mejor solución de anidamiento. Estos algoritmos incluyen (Guided/Iterado) Búsqueda local, rápida Barrio búsqueda que se basa en n-Fit Polígono, y empujones Heurística. Encontré un excelente artículo sobre este tema con imágenes de cómo funcionan los algoritmos. También tenía puntos de referencia de las diferentes implementaciones de software hasta ahora. Este documento fue presentado en el Simposio Internacional de Programación 2006 por S. Umetani et al (Umetani).

A relativamente nuevo y, posiblemente, el mejor enfoque hasta la fecha se basa en híbrido Algoritmo Genético (HGA), un híbrido que consiste en recocido simulado y algoritmo genético que ha sido descrito por Wu Qingming y col. De la Universidad de Wuhan (Quanming). Lo han implementado utilizando Visual Studio, base de datos SQL y la herramienta de optimización de algoritmos genéticos (GAOT) en MatLab.

Answer 2

Usted se está refiriendo a un conocido dominio informático de embalaje, para el cual hay una variedad de problemas definidos e investigaciones realizadas, tanto para el espacio bidimensional como para el espacio tridimensional.

Hay un considerable material en la red disponible para los problemas definidos, pero para encontrarlo debe saber el nombre del problema que debe buscar.

Algunos paquetes pueden adoptar un enfoque heurístico (que sospecho que lo harán) y algunos pueden llegar al extremo de calcular todas las posibilidades para obtener la respuesta correcta.

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