Algoritmos para empaquetado 3D de contenedores: cuando el espacio importa

El problema

El empaquetado de contenedores 3D es uno de esos problemas que parecen simples hasta que intentas resolverlos: dada una colección de objetos con dimensiones variables y un contenedor con capacidad fija, ¿cómo los colocas para maximizar el volumen utilizado? La respuesta trivial, "ponerlos uno al lado del otro", esconde una complejidad computacional que lo cataloga como NP-hard.

No existe un algoritmo exacto que resuelva instancias reales en tiempo polinomial. Lo que sí existen son heurísticas y metaheurísticas que, en la práctica, producen soluciones razonablemente buenas en tiempos aceptables. Este artículo recorre las más relevantes.

Modelo del problema

Antes de entrar a los algoritmos, vale la pena definir formalmente el modelo. Cada objeto tiene:

• Dimensiones: largo, ancho y alto.
• Orientaciones permitidas: subconjunto de las 6 rotaciones ortogonales posibles. En algunos contextos, como productos con etiquetado direccional, no todas las rotaciones son válidas.
• Restricciones adicionales: peso máximo, fragilidad, compatibilidad entre productos y cualquier regla operativa propia del negocio.

El contenedor tiene a su vez:

• Dimensiones internas: largo, ancho y alto.
• Capacidad de peso.
• Reglas de estabilidad: evitar que piezas queden flotando o que la distribución de peso genere riesgos de volcado.

El objetivo típico es maximizar el volumen utilizado o, equivalentemente, minimizar el número de contenedores necesarios para un conjunto dado de objetos.

Arquitectura del pipeline de colocación

Una arquitectura estándar para cualquier algoritmo de packing 3D sigue este flujo:

1. Preprocesamiento y ordenamiento: los objetos se ordenan según un criterio como volumen descendente, lado más largo primero o prioridad por peso.
2. Generación de orientaciones: para cada objeto se generan todas las rotaciones ortogonales válidas y se descartan las que exceden las dimensiones del contenedor.
3. Heurística de colocación espacial: se mantiene una estructura de espacios libres dentro del contenedor. Para cada objeto se evalúa dónde y en qué orientación cabe mejor.
4. Actualización de espacios libres: al colocar un objeto, el espacio que ocupaba se particiona en subespacios libres alrededor del objeto.
5. Metaheurística global: opcionalmente, sobre la solución inicial greedy se aplican búsqueda local, algoritmos genéticos o simulated annealing para mejorar el resultado.

3D First-Fit Decreasing (3D-FFD)

La extensión natural del clásico First-Fit Decreasing al espacio tridimensional.

Mecanismo: los objetos se ordenan por volumen descendente. Para cada objeto, se generan todas sus orientaciones válidas y se prueba cada una contra la lista de espacios libres existentes. La primera orientación que quepa en el primer espacio donde quepa es la que se coloca. Si no cabe en ningún espacio del contenedor actual, se abre un nuevo contenedor.

Complejidad: O(n × o × f), donde n es el número de objetos, o el número promedio de orientaciones por objeto y f el número de espacios libres activos.

Limitación principal: al ser codicioso y tomar el primer espacio disponible, no necesariamente produce la mejor compactación. Que un objeto quepa no significa que quepa bien; puede dejar huecos grandes alrededor.

// Pseudocódigo 3D-FFD
objetos = ordenarPorVolumenDescendente(listaObjetos)
contenedores = [nuevoContenedor()]

para cada objeto en objetos:
  para cada orientacion en objeto.orientacionesValidas():
    para cada espacio en contenedor.espaciosLibres:
      si espacio.cabe(objeto, orientacion):
        espacio.colocar(objeto, orientacion)
        ir al siguiente objeto

  contenedor = nuevoContenedor()
  contenedor.espaciosLibres[0] = contenedor.espacioTotal
  contenedor.espaciosLibres[0].colocar(objeto, orientacion)

3D Best-Fit Decreasing (3D-BFD)

La variante que corrige la principal debilidad del 3D-FFD.

Mecanismo: es idéntico al 3D-FFD en preprocesamiento y ordenamiento, pero la heurística de selección cambia. En vez de tomar el primer espacio donde quepa, se evalúan todas las combinaciones objeto-orientación-espacio y se elige aquella que deje el menor volumen de espacio sobrante.

También existe la variante best-fit por altura: se elige la ubicación que coloque el objeto lo más abajo posible, priorizando estabilidad y dejando más espacio libre arriba para objetos más altos.

Trade-off: 3D-BFD es más costoso computacionalmente que 3D-FFD, pero típicamente logra mejor utilización de volumen, entre un 2% y un 8% más en benchmarks estándar.

Layer + huecos internos

Una estrategia que descompone el problema 3D en una serie de problemas 2D.

Mecanismo: el contenedor se llena por capas en el eje Z. Cada capa tiene una altura fija, determinada por el objeto más alto de esa capa o por un límite predefinido. Dentro de cada capa, el problema se convierte en un 2D bin packing, típicamente resuelto con heurísticas como First-Fit Decreasing 2D o Best-Fit Decreasing 2D.

La innovación clave está en el manejo de huecos internos: dentro de cada capa se mantiene un mapa de espacios libres resultantes, como maximal empty rectangles. Cuando llega un objeto más pequeño, en vez de colocarlo en la siguiente posición libre de la capa, se busca si cabe en alguno de los huecos irregulares generados por combinaciones previas. Esto permite un entrelazado donde piezas pequeñas se integran en los huecos que dejan piezas más grandes.

Variantes comunes:

• Maximal rectangles: se mantiene la lista de rectángulos libres maximales y se recortan al colocar cada objeto.
• Guillotine cuts: se impone la restricción de que los cortes al partir espacios deben ser completos, lo que simplifica la estructura de datos pero puede producir soluciones menos óptimas.
• Extreme points: en vez de mantener rectángulos libres completos, se trabaja con puntos extremos, las esquinas inferiores izquierdas de cada espacio libre potencial.

Algoritmo codicioso con restricciones de compatibilidad

En contextos logísticos reales, el packing no es solo geométrico. Hay restricciones adicionales que muchas veces se ignoran en la literatura académica, pero son críticas en la práctica:

• Límites de peso por contenedor y distribución del centro de masa.
• Compatibilidad entre productos, evitando contaminación cruzada o combinaciones riesgosas.
• Prioridad de acceso, por ejemplo, objetos de alta rotación cerca de la puerta del contenedor.
• Fragilidad, evitando que objetos frágiles tengan carga pesada encima.

Un algoritmo greedy con restricciones extendidas funciona igual que 3D-BFD, pero añade filtros de factibilidad antes de evaluar cada posición: ¿el objeto cabe geométricamente?, ¿no excede el límite de peso?, ¿es compatible con los productos ya colocados?, ¿respeta las reglas de fragilidad?

La función de score se expande para incluir no solo volumen desperdiciado, sino también variación del centro de masa, penalización por colocar un objeto frágil debajo de uno pesado y penalización por violar zonas de compatibilidad.

Algoritmos genéticos para packing 3D

Cuando las heurísticas greedy no son suficientes, se recurre a metaheurísticas. Los algoritmos genéticos son de los más estudiados para bin packing 3D.

Representación del cromosoma: típicamente se codifica como una secuencia de objetos con su orientación asignada. El orden en el cromosoma determina el orden de inserción. Cada gen puede ser un par (objeto_id, orientacion_id).

Función de fitness: puede incluir múltiples objetivos, como maximización de volumen utilizado, minimización del número de contenedores, maximización de la estabilidad y minimización del número de rotaciones usadas.

Operadores:

• Crossover: combinaciones de padres producen hijos que heredan fragmentos del orden de colocación. Un crossover ingenuo puede producir objetos duplicados o faltantes, por lo que suele requerirse una variante basada en posición.
• Mutación: cambiar la orientación de un objeto, intercambiar la posición entre dos objetos o mover un objeto a otra parte del orden.

Pipeline típico: se usa una solución greedy, como 3D-FFD o 3D-BFD, para generar la población inicial. Eso le da al algoritmo genético un punto de partida razonablemente bueno en vez de partir de soluciones completamente aleatorias.

Limitaciones: los algoritmos genéticos son costosos computacionalmente y requieren ajustar múltiples hiperparámetros, como tamaño de población, tasa de mutación y número de generaciones. Para aplicaciones en tiempo real o con miles de objetos, pueden ser imprácticos sin paralelización.

Estructura de datos: espacios libres

El corazón de cualquier algoritmo de packing 3D serio es cómo representas y actualizas los espacios libres. La opción más común es mantener una lista de cajas libres: cada espacio libre se representa como (x, y, z, ancho, profundidad, alto). Inicialmente hay una sola caja, el contenedor completo. Al colocar un objeto, la caja ocupada se particiona en tres nuevas cajas en la versión simplificada alineada a ejes:

• La caja a la derecha del objeto.
• La caja al frente del objeto.
• La caja encima del objeto.

Versiones más sofisticadas usan axis-aligned bounding boxes con merge de cajas adyacentes cuando comparten un plano completo. Eso reduce la explosión de espacios libres que, de otro modo, degrada el rendimiento cuando hay muchos objetos.

Trade-offs entre algoritmos

Algoritmo	Velocidad	Calidad	Complejidad impl.	Notas
3D-FFD	Muy rápida	Buena	Baja	Baseline rápido, no busca el mejor ajuste.
3D-BFD	Rápida	Muy buena	Baja	Mejor compactación, aunque cuesta más que FFD.
Layer + huecos	Rápida	Buena	Media	Reduce el problema a 2D por capa.
Greedy + restricciones	Media	Variable	Media	Es la opción más flexible para operación logística real.
Algoritmos genéticos	Lenta	Excelente	Alta	Requiere tuning y más costo computacional.

Conclusión

No existe el algoritmo perfecto para bin packing 3D; existe el algoritmo adecuado para tu contexto. Si necesitas velocidad y una solución razonablemente buena para cientos de objetos en tiempo real, 3D-BFD con una estructura de espacios libres bien implementada es probablemente tu mejor opción. Si tienes tiempo de cómputo y necesitas la mejor solución posible, un algoritmo genético con una buena población inicial greedy puede mejorar significativamente los resultados.

Lo que sí es cierto es que la diferencia entre usar cualquier heurística y no usar ninguna es enorme. Estudios de caso en logística muestran que pasar de carga "a ojo" a 3D-FFD puede mejorar la utilización de volumen en un 15% a 25%. De 3D-FFD a 3D-BFD, otro 3% a 8%. De un greedy a un algoritmo genético bien afinado, hasta un 5% adicional.

Si quieres ver cómo funciona esto en la práctica y probarlo con tus propios proyectos, tenemos una implementación funcional en acomodamela.dbug.mx, donde puedes cargar objetos, definir tu contenedor y observar cómo diferentes algoritmos toman decisiones de placement en tiempo real.