¿Cómo puedo determinar mediante progtwigción cómo colocar cajas más pequeñas en un paquete más grande?

¿Alguien sabe de software o algoritmos existentes para calcular el tamaño de un paquete para el envío de múltiples artículos?

Tengo un montón de artículos en nuestra base de datos de inventario con dimesiones de longitud, ancho y alto definidos. Dadas estas dimensiones, necesito calcular cuántos de los artículos comprados se adaptarán a los tamaños de caja predefinidos.

Este es un problema de Bin Packing , y es NP-hard. Para una pequeña cantidad de objetos y paquetes, puede simplemente usar el método de fuerza bruta para probar todas las posibilidades. Más allá de eso, necesitarás usar una heurística de algún tipo. El artículo de Wikipedia tiene algunos detalles, junto con referencias a documentos que probablemente quiera consultar.

La alternativa, por supuesto, es comenzar con un algoritmo realmente simple (como simplemente ‘astackr’ elementos) y calcular un límite superior razonable en el envío utilizando eso, entonces, si sus empacadores humanos pueden hacerlo mejor, obtendrá un beneficio leve. O descuenta los precios calculados ligeramente suponiendo que tu embalaje no es ideal.

La literatura sobre “Empaquetado de cubos 3D” es extensa. Puede obtener una buena visión general siguiendo las publicaciones del Profesor David Pisinger . También publicó una de las pocas implementaciones de alta calidad de bin packing con código fuente: 3dbpp.c

Mi propio kit de herramientas de logística pyShipping viene con una implementación de 3D Bin Packing para aplicaciones de Warehousing. Básicamente está implementando 4D Bin Packing (tamaño 3D y peso) y obtiene una solución aceptable para tamaños de pedidos típicos (algunas docenas de paquetes) en un segundo tiempo de ejecución. Se usa en producción (es decir, un almacén) durante algunos meses para determinar el límite superior de las cajas de envío que se utilizarán. Los trabajadores del almacén a menudo pueden empacar de manera más eficiente, pero eso está bien conmigo.

Pisinger es uno de los pocos académicos que publica código de trabajo . En uno de sus documentos menciona el problema de “profundidad mínima”.

Aquí hay un algoritmo práctico y eficiente para el Embalaje de Caja Rectangular 3D que ajusta la altura de la caja envolvente.

Y aquí hay una implementación en php .

¿Estás tratando de ver cuántos de un solo tipo cabe en un paquete de tamaño particular, o también estás tratando de mezclar tipos?

Parece que estás tratando de resolver el problema de la mochila . Es posible que pueda encontrar algunos algoritmos para eso que podrían adaptarse a sus requisitos específicos. Simplemente entienda que será difícil encontrar un algoritmo eficiente , ya que el problema es NP completo (aunque dependiendo de sus requisitos específicos, puede encontrar una aproximación eficiente o sus entradas pueden ser lo suficientemente pequeñas como para que no importe) .

Si las cajas van a ser empacadas a mano, entonces podría considerar escribir un algoritmo que haría lo que haría un humano razonable . La razón por la que sugiero esto es porque, a menos que desee imprimir las instrucciones de embalaje para cada pedido, quien realice el embalaje tendrá que entrenar cómo van a encajar los artículos pedidos en la cantidad de cajas asignadas para el pedido. orden.

Esto podría llevar a que sus empacadores humanos lleguen a SO, preguntándose cómo entrenar programáticamente cómo empacar n artículos en m boxes. 😛 (También pueden pedirle que lo haga, pedirle instrucciones, etc.).

Mientras su algoritmo haga lo que haría un ser humano razonable, yo personalmente aceptaría su estimación de envío.

Las metaheurísticas son buenas para lidiar con problemas de empaquetamiento de basura en el mundo real cuando hay muchos paquetes y / o muchas restricciones. Una implementación Java de código abierto es Drools Planner .

Tal vez esto parezca obvio, pero podría valer la pena memorizar el problema, luego hacer algunos de ellos a mano. Encontrar la solución más eficaz para entradas y cuadros arbitrarios en NP-hard, pero al restringir el espacio problemático y aceptar alguna ineficiencia, que el tamaño de NP sea algo razonable, y al memorizar, es posible que pueda presentar el “caso común” “Tiempo de inactividad sustancialmente.

También podría ayudar pensar sobre las cosas en términos de empaquetamiento jerárquico.

Después de muchas búsquedas, encontré un repository de GitHub que podría ayudar a alguien. Función PackingService.Pack() toma la lista del Container y la lista de Item que se empaquetarán como parámetro y devolverá el resultado que contiene gran cantidad de información, incluida

“contenedor (es) empaquetados en porcentaje y lista de artículos empacados y desempacados”