Algoritmo híbrido para resolver los problemas del Bin Packing Unidimensional más difíciles

Resumen En esta tesis se aborda el problema del Bin Packing Unidimensional fuera de línea, el cual pertenece a los problemas combinatorios del tipo NP-duro donde se solucionarán las instancias más difíciles mediante la creación de un algoritmo híbrido, se propone hibridar el algoritmo de Búsqueda Tabú y el algoritmo Genético con nuevas mejoras propuestas, con la finalidad de extraer información relevante que posibilite la generación de estrategias para mejorar los algoritmos existentes y/o generar nuevos. Los métodos de solución exacta propuestos para el BPP (del inglés, Bin Packing Problem) están limitados para resolver su intratabilidad. Una alternativa prometedora son los algoritmos metaheurísticos que obtienen soluciones que se aproximan a la solución óptima. Dado que no existe un algoritmo que sea la mejor opción para todas las situaciones posibles, tomar lo mejor de cada uno de ellos es un reto, por lo anterior, en este trabajo de tesis se propone hibridar dos Metaheurísticas para mejorar los resultados, además, añadir mejoras que ayuden a intensificar la búsqueda de nuevos resultados y esto hace un reto aún más complicado de realizar. Esta tesis parte del supuesto que la hibridación de algoritmos Metaheurísticos mediante técnicas especializadas, lo cual permitirá incrementar el alcance de solución. En la búsqueda de algoritmos Heurísticos eficientes para resolver problemas de optimización combinatoria, se han observado algunas de las características con las que las instancias son difíciles de resolver, tomando en cuenta estas dificultades encontradas se ha decidido utilizar una Heurística de intercambio y desplazamiento propuesto por Martello y Toth para obtener resultados aproximados y tomarlo como base para la hibridación. Los resultados obtenidos con el algoritmo Híbrido muestran que el algoritmo se comporta bastante bien con instancias chicas, medianas y algunas grandes, llegando a encontrar gran parte de las soluciones óptimas de las instancias utilizadas, a partir de esto, se implementaron nuevas técnicas que ayudan a buscar nuevos resultados (intensificar búsquedas), además de mejorar la eficiencia y eficacia de los resultados en instancias aún más grandes y que son difíciles de resolver para el algoritmo híbrido. El algoritmo híbrido puede resolver cualquier instancia para el problema del Bin Packing Unidimensional fuera de línea. El tiempo que requiere el algoritmo híbrido es otro punto para destacar, ya que, el algoritmo reduce significativamente el tiempo que se requiere para encontrar una solución óptima o aproximada de las instancias Hard28 en comparación con otros investigadores. De manera particular, el 50% de las instancias Hard28 requieren más del triple del tiempo en comparación con el algoritmo híbrido propuesto.

Abstract In this thesis the problem of one-dimensional Bin Packing offline is approached, which belongs to the combinatorial problems of the NP-hard type where the most difficult instances to solve will be solved by creating a hybrid algorithm, it is proposed to hybridize the algorithm of Tabu Search and the Genetic algorithm with new proposed improvements, in order to extract relevant information that enables the generation of strategies to improve existing algorithms and / or generate new ones. The exact solution methods proposed for the BPP (Bin Packing Problem) are limited to solving its intractability. A promising alternative is metaheuristic algorithms that obtain solutions that approximate the optimal solution. Since there is no algorithm that is the best option for all possible situations, taking the best of each of them is a challenge, therefore, in this thesis work, it is proposed to hybridize two Metaheuristics to improve the results, in addition, add improvements that help to intensify the search for new results, and this makes an even more complicated challenge to carry out. This thesis is based on the assumption that the hybridization of Metaheuristic algorithms through specialized techniques, which will allow increasing the scope of the solution. In the search for efficient Heuristic algorithms to solve combinatorial optimization problems, some of the characteristics with which the instances are difficult to solve have been observed, taking into account these difficulties encountered, it has been decided to use an exchange and displacement heuristic proposed by Martello and Toth to obtain approximate results and take it as the basis for hybridization. The results obtained with the Hybrid algorithm show that the algorithm behaves quite well with small, medium and some large instances, finding a large part of the optimal solutions of the instances used, from this, new techniques were implemented that help to search for new results (intensify searches), in addition to improving the efficiency and effectiveness of the results in even larger instances where the hybrid algorithm finds it difficult to solve them. Another point to highlight from the results obtained is that the algorithm can solve any instance for the offline One-dimensional Bin Packing problem. The time taken by the hybrid algorithm is another point to highlight, since the algorithm reduces the time, it takes to find an optimal solution or approximates the Hard28 instances compared to other researchers, where 50% of the Hard28 instances it takes more than triple time or more compared to the proposed hybrid algorithm.