Algoritmos tridimensionales de empaquetadura de contenedores

Question

Tengo un problema con el empaquetamiento tridimensional y actualmente estoy realizando algunas investigaciones preliminares sobre qué algoritmos/heurísticas están produciendo los mejores resultados. Dado que el problema es NP difícil, no espero encontrar la solución óptima en todos los casos, pero me preguntaba:

1) ¿Cuáles son los mejores solucionadores exactos? Rama y Bound? ¿Qué tamaños de instancia de problema puedo esperar resolver con recursos informáticos razonables?
2) ¿Cuáles son los mejores solucionadores heurísticos?
3) ¿Qué soluciones listas para usar existen para realizar algunos experimentos?

Answer 1

De wikipedia:

Aunque these simple strategies son a menudo lo suficientemente bueno, algoritmos de aproximación eficientes han demostrado que puede resolver el problema de embalaje bin dentro de cualquier porcentaje fijo de la solución óptima para suficientemente grandes entradas

Aquí están las dos fuentes que dan para esto:

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

Answer 2

En cuanto a soluciones ya, echa un vistazo a MAXLOADPRO para la carga de camiones. Puede configurarse para cargar cualquier volumen rectangular, pero aún no lo he intentado. En general, los problemas de empaquetamiento en 3d tienen la complicación adicional de que los objetos pueden rotarse en diferentes posiciones, por lo que para cualquier objeto con una longitud, ancho y altura dados, efectivamente debe crear tres variables que representen cada posición, pero solo use una en la solución.

En general, las formulaciones MIP independientes (o bifurcadas y encuadernadas) no funcionan bien para el problema 2d o 3d, pero la programación de restricciones ha tenido cierto éxito produciendo soluciones exactas para el problema 2d. Mira esto abstract. Sin mirar el documento, me gusta el enfoque de descomposición para el problema en el que intentas minimizar el número de contenedores del mismo tamaño. No he visto tantos resultados para el problema 3d, pero háganos saber si encuentra alguno que pueda implementarse.

¡Buena suerte!

Answer 3

Usted pregunta es similar a: 3d bin packing algorithm

Aunque, debido a que dis-permitir la rotación, usted puede obtener muy buenos resultados. Sugiero mirar más hacia una solución FIRST-FIT-DECREASING.

Answer 4

Mejor solucionador exacto: Utilice dynamic programming.

las variables

Estado:

1. elementos que tiene envasados ​​y se desecha.
2. Espacio lleno en el contenedor.

Si el contenedor es una cuadrícula paralelepípeda, y los elementos "encajan" en celdas exactas de la cuadrícula, puede usar una matriz tridimensional para representar la variable de estado 2.De lo contrario, tendrá que usar estructuras de datos más complejas.

mejores solucionadores de heurísticas

que no conozco. Tal vez Variable Neighborhood Search. Hay algunas similitudes entre su problema y el problema de construcción del horario (en el que estoy trabajando), por lo que la misma heurística podría ser buena para ambos.

Off-the-shelf soluciones para llevar a cabo experimentos

Lo siento, no tienen ni siquiera una pista.

Answer 5

He escrito un program que prueba tres algoritmos diferentes. También esta es una buena fuente de información: A Thousand Ways to Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing. Es para bin rectangular bidimensional, pero siempre puedes transformarlo a 3D.

Answer 6

3dbinpacking es una solución comercial (no es un algoritmo) que expone una API para consumir con una buena visualización. Ofrece:

• bin solo embalaje
• bin Multi embalaje
• Encuentra tercera dimensión
• encontrar un bin dimensiones