El objetivo de los problemas de packing es encontrar la mejor manera de empaquetar un conjunto de elementos de tamaños determinados en contenedores con packing fijas. Una aplicación típica es cargar cajas en camiones de reparto de manera eficiente. A menudo, no es posible empaquetar todos los elementos debido a las restricciones de capacidad. En ese caso, el problema es encontrar un subconjunto de los elementos con el tamaño total máximo que quepa en los contenedores.
Hay muchos tipos de problemas de empaquetado. Dos de los más importantes son los problemas de mochilas y el empaquetado de contenedores.
Problemas de mochila
En el problema simple de la mochila, hay un solo contenedor (una mochila). Los elementos tienen valores y tamaños, y el objetivo es empaquetar un subconjunto de los elementos que tenga un valor total máximo.
Para el caso especial en el que el valor es igual al tamaño, el objetivo es maximizar el tamaño total de los elementos empaquetados.
Las herramientas OR proporcionan varios solucionadores de problemas de mochilas en su biblioteca de algoritmos.
También hay versiones más generales del problema de la mochila. A continuación, se incluyen algunos ejemplos:
Problemas de mochila multidimensionales: Los elementos tienen más de una cantidad física, como el peso y el volumen, y la mochila tiene una capacidad para cada cantidad. Aquí, el término dimensión no necesariamente se refiere a las dimensiones espaciales habituales de altura, longitud y ancho. Sin embargo, algunos problemas pueden estar relacionados con las dimensiones espaciales, por ejemplo, encontrar la forma óptima de empaquetar cajas rectangulares en un contenedor de almacenamiento rectangular.
Varios problemas de mochila, en los que hay varias mochilas y el objetivo es maximizar el valor total de los artículos empaquetados en todas las mochilas.
Ten en cuenta que puedes tener un problema multidimensional con una sola mochila o uno múltiple con una sola dimensión.
El problema del empaquetado en contenedores
Uno de los problemas de empaquetado más conocidos es el bin-packing, en el que existen varios contenedores (llamados bin-packing) con la misma capacidad. A diferencia del problema de varias mochilas, la cantidad de discretizaciones no es fija. En cambio, el objetivo es encontrar la menor cantidad de discretizaciones que contengan todos los elementos.
A continuación, se muestra un ejemplo simple para ilustrar la diferencia entre el problema de la mochila múltiple y el de empaquetado en contenedores. Supongamos que una empresa tiene camiones de reparto, cada uno de los cuales tiene una capacidad de peso de 18,000 libras y 130,000 libras de artículos para entregar.
Varias mochilas: Tienes cinco camiones y deseas cargar un subconjunto de los elementos que tenga el peso máximo en ellos.
Empaquetado en contenedores: tiene 20 camiones (más que suficientes para llevar todos los artículos) y desea usar la menor cantidad de camiones posible.
En las siguientes secciones, se muestra cómo resolver varios tipos de problemas de empaquetado con las herramientas OR, comenzando con el problema de mochila.