Problema de optimización para la anidación de tuberías

Question

Trabajo en una empresa en la que se supone que producimos y enviamos tubos con camiones a los compradores. Los tubos de menor diámetro pueden anidarse dentro de los de mayor diámetro durante el envío para minimizar el número de camiones.

Los camiones que transportan estos tubos suelen tener una longitud de 40 pies / 12,192 metros, mientras que los tubos miden 12 metros. Por lo tanto, se colocan a lo largo del remolque.

Los camiones suelen tener 2,438 metros de altura y anchura, es decir, 8x8.

Los diámetros exteriores de los tubos que fabricamos son 90, 110, 125, 140, 160, 180, 200, 250 y 315 (todos los tamaños en mm).

Una limitación es que, al anidar, los tubos de un tamaño sólo pueden anidarse dentro de tubos de un tamaño superior al siguiente. Por ejemplo, un tubo de 90 puede ir dentro de un tubo de 125 o más, y un tubo de 140 puede ir dentro de un tubo de 160 o más.

Deseo derivar matemáticamente un sistema para la carga óptima de los camiones con el fin de minimizar el número de camiones para entregar la cantidad pedida de varios tamaños utilizando la anidación porque a menudo nos equivocamos con la anidación, lo que resulta en enormes implicaciones de costes. ¿Puede alguien ayudarnos?

(Además, soy un usuario ingenuo. También sería útil que me sugirieras las etiquetas apropiadas que debería poner a lo largo de la pregunta para ayudar a la gente a notar la pregunta).

Answer 1

Dudo que haya una estrategia analítica óptima para resolver el problema. Será necesario utilizar un enfoque de optimización.

Una estrategia ingenua y codiciosa, que probablemente sea decente, pero casi seguro que no es óptima:

1. Empaque en todas las tuberías más grandes. Para cualquier camión dado, esto equivale a un problema de empaquetar tantos círculos como sea posible en un cuadrado; como Malcolm mencionó en un comentario, este problema se ha resuelto explícitamente en algunos casos y probablemente también existen cálculos numéricos; véase https://en.wikipedia.org/wiki/Circle_packing_in_a_square . Utilizar el menor número de camiones posible.

2. Considere el tipo de tubería más grande que aún no se ha embalado. Primero anídelos dentro de los tubos más grandes. Si aún quedan tubos, intente encajarlos en los huecos entre los tubos más grandes; empaquételos con el mayor cuidado posible. Se trata de empaquetar círculos en un área delimitada arbitrariamente y puede que exista literatura de optimización, pero es casi seguro que no habrá soluciones explícitas. Puedes hacer esto de un camión a la vez. Si aún quedan tubos del mismo tamaño, añade nuevos camiones; esto se reduce al paso 1., anterior.

3. Repita el paso 2 para todos los tamaños de tubería.

Un método de optimización ingenuo, y no eficiente, sería eliminar una tubería (y todas las tuberías anidadas) de un tamaño determinado y luego tratar de encajar dos o más tuberías más pequeñas en el hueco. Debería llenar primero todos los camiones con el método ingenuo y luego comprobar qué tamaño de tuberías hay en el final; éstas son las que querrá empaquetar de forma más eficaz.

Supongamos que hay al menos dos camiones llenos de tubos del tamaño crítico. Intenta retirar las tuberías más grandes de otros camiones y sustituirlas por tuberías del tamaño crítico. Toma el camión más vacío con tuberías críticas como el que intentas vaciar. En el otro(s) intentarás insertar las tuberías que has retirado de otro lugar.

Esto sería engorroso, por lo que probablemente sólo se mantenga el algoritmo ingenuo.