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

Question

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

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

Answer 1

Esto es un problema Bin Packing, y es NP-difícil. 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 'apilar' elementos) y calcular un límite superior razonable en el envío usando eso, entonces, si sus empacadores humanos pueden hacerlo mejor, usted hace un pequeño beneficio. O descuenta los precios calculados ligeramente suponiendo que tu embalaje no es ideal.

Answer 2

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

Parece que estás intentando solucionar el Knapsack Problem. Es posible que pueda encontrar algunos algoritmos para eso que podrían adaptarse a sus requisitos específicos. Simplemente tenga en cuenta 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 lo haga). importar).

Answer 3

Quizás esto parezca obvio, pero podría valer la pena memorizar el problema, y ​​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 en cosas en términos de embalaje jerárquico.

Answer 4

Si las cajas van a empacarse a mano, entonces podría considerar escribir un algoritmo que haría lo que haría un humano razonable humano. 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 elementos en m cajas. :-P (También pueden solicitarle para hacerlo, pedirle instrucciones, etc.).

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

Answer 5

tal vez esta cosa que hackeado las últimas horas pueden ayudar: http://github.com/yetzt/boxing

Answer 6

La literatura sobre la "Papelera de embalaje 3D" es largo y ancho. Puede obtener una buena visión general siguiendo las publicaciones de Professor 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 Bin Packing 3D para aplicaciones de almacenamiento. Básicamente está implementando 4D Bin Packing (tamaño 3D & 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.

Answer 7

Las metaheurísticas son buenas para hacer frente a los problemas de embalaje de contenedores del mundo real cuando hay muchos paquetes y/o muchas limitaciones. Una implementación Java de código abierto es Drools Planner.

Answer 8

Pisinger es uno de los pocos académicos que publica working code. En uno de sus documentos, menciona el problema de "profundidad mínima".

Aquí está una práctica y efficient algorithm para el Embalaje de Caja Rectangular 3D que ajusta la altura de la caja envolvente.

Y aquí hay una implementación en php.

Answer 9

Después de mucha búsqueda encontré un repositorio GitHub que podría ayudar a alguien. Función PackingService.Pack() lista de Container y la lista de Item (s) a ser envasados ​​como parámetro y el retorno de resultados que contiene gran cantidad de información, incluyendo

"recipiente (s) envasado en porcentaje y la lista de los artículos envasados ​​y no envasados"