algorithm - tipos - Algoritmos de embalaje de contenedores de 3 dimensiones

siglas de contenedores por naviera

Question

Me enfrento a un problema de empaquetado de contenedores tridimensionales y actualmente estoy realizando una investigación preliminar sobre qué algoritmos / heurísticas están dando 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 límite? ¿Qué tamaño de instancia de problema puedo esperar resolver con recursos informáticos razonables?
2) ¿Cuáles son los mejores solucionadores heurísticos?
3) ¿Con qué soluciones estándar existen para realizar algunos experimentos?

Answer 1

De wikipedia :

Aunque estas estrategias simples a menudo son lo suficientemente buenas, se han demostrado algoritmos de aproximación eficientes que pueden resolver el problema de empaquetamiento de contenedores dentro de cualquier porcentaje fijo de la solución óptima para insumos suficientemente grandes

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

• Algoritmos de aproximación
• El empaque del contenedor se puede resolver dentro de 1 + ε en tiempo lineal

Answer 2

En cuanto a las soluciones disponibles, revise MAXLOADPRO para cargar camiones. Puede configurarse para cargar cualquier volumen rectangular, pero todavía no lo he intentado. En general, los problemas de empaquetado de contenedores 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, anchura y altura dadas, tiene que crear efectivamente tres variables que representan cada posición, pero solo usa una en la solución.

En general, las formulaciones MIP independientes (o ramificación y enlace) no funcionan bien para el problema 2d o 3d, pero la programación de restricciones ha tenido cierto éxito al producir soluciones exactas para el problema 2d. Echa un vistazo a este abstract . Sin mirar el papel, me gusta el enfoque de descomposición para el problema en el que intenta minimizar el número de contenedores del mismo tamaño. No he visto tantos resultados para el problema 3D, pero avísenos si encuentra alguno que sea implementable.

Buena suerte !

Answer 3

He escrito un program que prueba tres algoritmos diferentes. Además, esta es una buena fuente de información: mil maneras de empacar el contenedor: un enfoque práctico para el empaque de un contenedor rectangular de dos dimensiones . Es para un contenedor de rectángulo bidimensional, pero siempre puede transformarlo en 3D.

Answer 4

Usted pregunta es similar a: algoritmo de embalaje bin 3d

Aunque, debido a que no permite la rotación, puede obtener resultados bastante buenos. Sugiero mirar más hacia una solución que reduzca en primer lugar.

Answer 5

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

• Embalaje de un solo contenedor
• Embalaje de contenedores múltiples
• Encontrar tercera dimensión
• Encuentra las dimensiones de un contenedor

Answer 6

El mejor solucionador exacto: usar programación dinámica .

Variables de estado:

1. Elementos que hayas embalado y descartado.
2. Espacio rellenado en el contenedor.

Si el contenedor es una cuadrícula paralelepipédica y los elementos "encajan" en las 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 heurísticos

No lo sé. Tal vez la búsqueda de vecindario variable . Hay algunas similitudes entre su problema y el problema de la construcción del calendario (en el que estoy trabajando), por lo que la misma heurística podría ser buena para ambos.

Soluciones disponibles para llevar a cabo experimentos

Lo siento, ni siquiera tengo una pista.