1. Repositorio Institucional del Tecnológico Nacional de México (RI - TecNM)
2. Tesis de Posgrado
3. Tamaulipas
4. Instituto Tecnológico de Ciudad Madero
5. Tesis
6. Tesis de Maestría
7. Maestría en Ciencias de la Computación

Title:	HIBRIDACIÓN DE ALGORITMOS METAHEURÍSTICOS PARA PROBLEMAS DE BIN PACKING
Authors:	Nieto Yañez, Diana Maritza.
Issue Date:	2007-12-01
Publisher:	Tecnológico Nacional de México
metadata.dc.publisher.tecnm:	Instituto Tecnológico de Ciudad Madero
Description:	La rentabilidad y productividad de las empresas demanda una buena organización de sus procesos logísticos. Para posibilitar ahorros económicos importantes, el presente proyecto aborda el diseño de planes de distribución de objetos en contenedores. Este problema es conocido en las ciencias computacionales como BPP (acrónimo de Bin Packing Problem), y pertenece a una clase de problemas difíciles que demandan una alta cantidad de recursos computacionales. A pesar de su dificultad, la formulación de problemas mediante BPP permite resolver una gran cantidad de situaciones de las empresas, entre las cuales destaca el ahorro de espacios en planta y el acomodo de productos en vehículos y líneas de producción. Los métodos tradicionales propuestos para la solución de BPP 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. Esta tesis parte del supuesto que la hibridación de algoritmos metaheurísticos, mediante técnicas especializadas, permitiría incrementar su alcance de solución. Por lo anterior, se propone un algoritmo genético híbrido. El metaheurístico controla el proceso de búsqueda de la solución, e interactúa con un conjunto de estrategias heurísticas. Para la representación de soluciones se utiliza un esquema basado en bloques. Esto incrementa el desempeño pero genera soluciones inviables. Para manejar la inviabilidad e incrementar la capacidad de exploración se adaptaron cuatro algoritmos deterministas. Además, se incorporaron métodos para estimar valores cercanos al óptimo. Estos límites se utilizan para delimitar el espacio de la búsqueda y como criterio de paro del algoritmo. Los resultados de los experimentos muestran que el algoritmo híbrido tiende a converger rápidamente hacía el óptimo. La hibridación permitió resolver un mayor número de instancias tomadas de un banco de pruebas estándar con un menor error, pasando de un 5.1% a un 0.17%. Experimentos adicionales muestran su alto nivel de competencia con respecto a los de la literatura.
metadata.dc.type:	info:eu-repo/semantics/masterThesis
Appears in Collections:	Maestría en Ciencias de la Computación

This item is protected by original copyright View License

This item is licensed under a Creative Commons License