Optimización de problemas multi-objetivo de empaquetado de palets mediante algoritmos evolutivos

Abstract

En este trabajo se ha implementado un algoritmo evolutivo multi-objetivo paralelo, para resolver el problema de empaquetamiento en dos dimensiones con restricciones, para una aplicación de transporte de palets en camiones. El transporte de palets en camiones tiene una gran importancia en Andalucía y especialmente en el campo almeriense donde a diario salen hacia Europa cientos de camiones cargados de productos del campo. El problema de empaquetamiento en dos dimensiones (2DPP) consiste en insertar un conjunto de objetos caracterizados por tener un alto y ancho específico, en el menor número de camiones posibles donde el alto y ancho es igual para todos. A partir de esta definición existen multitud de variantes al problema. En la variante multi-objetivo del problema, además de minimizar el número de camiones, se intenta minimizar el balanceo de carga de los mismos intentando colocar la carga de las piezas de la mejor forma posible para que el centro de gravedad del camión quede lo más cercano posible al centro deseado. El algoritmo se ha aplicado a una variante del problema donde se trata de insertar un conjunto de palets con su alto, ancho y peso específico, en el menor número de camiones posible y con el mejor balanceo de carga, evitando una serie de restricciones añadidas al problema. Cada palet corresponde a un cliente, con lo cual todos los palets de un mismo cliente deben de ir en el mismo camión, cada camión no puede ir cargado con más de 25000 kilos y el centro de gravedad debe de ir lo más próximo al eje del camión. Para la optimización de este problema hemos implementado un algoritmo evolutivo TPMOEA, este tipo de algoritmos están inspirados en la teoría de la evolución de Darwin y en el desarrollo de la informática evolutiva. Los algoritmos evolutivos son técnicas de optimización y búsqueda de soluciones basadas en la selección natural y genética que permiten resolver problemas no lineales en los que interviene un alto número de variables en problemas complejos. El algoritmo ha sido implementado con un conjunto de operadores evolutivos diseñados para obtener soluciones de gran calidad para un conjunto de instancias establecidas.