Resumen de Un algoritmo exacto de ramificación y corte para el problema del pallet

Ramón Álvarez Valdés , Francisco Parreño Torres , José Manuel Tamarit Goerlich

• En este trabajo desarrollamos un algoritmo exacto para el problema del "pallet loading", el problema del empaquetamiento en el que en una superficie rectangular, pallet, ha de colocarse el máximo número de cajas de un mismo tipo. Revisamos los métodos heurísticos y las cotas superiores propuestos para el problema a fin de incorporar a nuestro esquema procedimientos eficientes de obtención de cotas superiores e inferiores. El algoritmo exacto está basado en la técnica de ramificación y corte. Se estudian diversas desigualdades válidas que generan buenos cortes en los nodos del árbol de búsqueda. Los resultados computacionales muestran la eficiencia del algoritmo.