Solucionador de problemas de empaquetado de contenedores en 2D

Esta calculadora en línea trata de resolver un problema de empaquetado bidimensional (2D) fuera de línea, utilizando el algoritmo heurístico de Rectángulos Máximos

Esta calculadora en línea le ayudará a responder a preguntas como cuántas losas se necesitan si encaja una serie de rectángulos más pequeños de varias dimensiones de longitud y anchura (LxW) en rectángulos más grandes con dimensiones fijas de longitud y anchura (LxW).

Por ejemplo, usted es un fabricante de encimeras y necesita calcular cuántas tablas de un tamaño determinado necesita pedir para un trabajo. Por lo tanto, la cantidad de material que se necesita debe desglosarse en una serie de pequeños rectángulos (vea esta solicitud).

A continuación debe introducir las dimensiones de la losa maestra en formato Largo x Ancho, y luego las dimensiones de las piezas rectangulares y su cantidad, en formato Largo x Ancho x Cantidad, un tipo de rectángulos por línea.

De hecho, se trata de un problema de empaquetado de piezas rectangulares en dos dimensiones. La calculadora intentará encontrar la mejor distribución que pueda, pero no garantiza la solución óptima. Para más detalles, consulte la sección de teoría debajo de la calculadora.

PLANETCALC, Solucionador de problemas de empaquetado de contenedores en 2D

Solucionador de problemas de empaquetado de contenedores en 2D

Dimensiones del contenedor

Rectángulos para empaquetar

Contenedores requeridos
 
El archivo es muy grande; La ralentización del navegador puede ocurrir durante la carga y creación.
El archivo es muy grande; La ralentización del navegador puede ocurrir durante la carga y creación.

Empaquetado de contenedores rectangulares bidimensionales

Bien, aquí tratamos el problema del empaquetado de contenedores rectangulares bidimensionales. En cualquier problema de empaquetado de contenedores, se dan algunos contenedores (en nuestro caso, el contenedor es una región rectangular 2D). Un conjunto de objetos (de nuevo, en nuestro caso, se trata de rectángulos más pequeños) debe ser empaquetado en uno o más contenedores. El objetivo suele ser empaquetar todos los objetos utilizando el menor número posible de contenedores.

Si el conjunto de objetos que hay que empaquetar se conoce de antemano, el problema se denomina "fuera de línea", a diferencia del problema "en línea", en el que los objetos aparecen uno a uno. Por lo tanto, aquí tenemos que tratar el problema fuera de línea de empaquetado de contenedores rectangulares en 2D.

Este es uno de los problemas clásicos de la optimización combinatoria y se ha demostrado que es difícil de resolver. Por lo tanto, solo podemos aproximarnos a la solución óptima con algoritmos heurísticos.

Esta implementación particular del solucionador del problema de empaquetado de contenedores en 2D se basa en los Algoritmos de Rectángulos Máximos. Esta heurística es una extensión de la heurística de corte por guillotina y muestra excelentes resultados para el empaquetado fuera de línea.1

La idea de la heurística de los rectángulos máximos es llevar la cuenta de todos los espacios rectangulares libres máximos, que todavía están disponibles después de colocar un objeto en el contenedor (vea la imagen siguiente).

Controlar los rectángulos superpuestos
Controlar los rectángulos superpuestos

También hay diferentes reglas para elegir qué rectángulo colocar en cada contenedor. Aquí utilizamos el enfoque global, lo que significa que en cada paso calculamos la 'puntuación' para cada rectángulo restante y cada espacio libre restante y elegimos la combinación que nos da la mejor puntuación. En cuanto a la regla de colocación particular, esta implementación en realidad comprueba cuatro de ellas y luego elige la regla que produce el mejor resultado (es decir, utiliza una cantidad mínima de contenedores).

Las reglas de colocación son

  1. Parte inferior izquierda: la coordenada y de la parte superior del rectángulo debe ser la más pequeña. En caso de empate, se utilizará el que tenga el valor más pequeño de la coordenada x.
  2. Mejor ajuste del lado corto - el área de espacio libre debe tener la longitud mínima del lado sobrante más corto.
  3. Mejor ajuste del lado largo: el área de espacio libre debe tener la longitud mínima del lado sobrante más largo.
  4. Mejor ajuste del área - el área de espacio libre debe ser la más pequeña del área para colocar el siguiente rectángulo. En caso de empate, se utiliza la regla del mejor ajuste del lado corto.

  1. A Thousand Ways to Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing by Jukka Jylänki 

URL copiada al portapapeles
PLANETCALC, Solucionador de problemas de empaquetado de contenedores en 2D

Comentarios