Un algoritmo basado en backtracking para un problema de packing en tres dimensiones

Abstract

En este trabajo consideramos el siguiente problema de packing en tres dimensiones, que surge en el contexto del transporte de productos medicinales refrigerados. Los datos de entrada están dados por un conjunto de productos y un conjunto de tipos de contenedores. Cada producto consiste de una cierta cantidad de cajas, especificadas por su ancho, altura y profundidad. Cada contenedor está especificado por su ancho, altura y profundidad internos, y además tiene asociados un costo y un porcentaje máximo de volumen que se puede ocupar. El problema consiste en ubicar los productos en contenedores minimizando el costo total de los contenedores utilizados, de modo tal que (a) cada producto se ubique en forma vertical en cada contenedor, (b) no haya superposiciones entre los productos, (c) cada producto o bien se ubique sobre el piso del contenedor o bien al menos el 70% de su base esté apoyada sobre otros productos, (d) no se supere el porcentaje máximo de volumen ocupado en ningún contenedor y (e) cada producto aparezca con productos distintos en a lo sumo un contenedor. No hay límite a la cantidad de contenedores que se pueden usar. Presentamos un algoritmo heurístico para este problema. Se utiliza como sub-rutina un algoritmo de programación dinámica para la resolución del problema mono-contenedor y mono-producto (sobre la base de algoritmos similares para el pallet loading problem'). A partir de la generación de todas las combinaciones posibles de contenedores mono-producto, se utiliza un algoritmo basado en backtracking para completar la asignación de las cantidades restantes de cada producto. Presentamos experimentos computacionales intensivos, que muestran que los tiempos de resolución sobre instancias prácticas son aceptables y que las soluciones generadas por el algoritmo son adecuadas.