Please use this identifier to cite or link to this item:
https://rinacional.tecnm.mx/jspui/handle/TecNM/3000| Title: | UN ESTUDIO FORMAL DE HEURÍSTICAS PARA EL PROBLEMA DE EMPACADO DE OBJETOS DE UNA DIMENSIÓN |
| Authors: | Gonzalez San Martin, Jessica Elena |
| Issue Date: | 2021-05-01 |
| Publisher: | Tecnológico Nacional de México |
| metadata.dc.publisher.tecnm: | Instituto Tecnológico de Ciudad Madero |
| Description: | El problema de Bin Packing de una dimensión (1D-BPP) es un problema clásico de optimización que es conocido por su aplicabilidad y complejidad, el cual pertenece a una clase especial de problemas denominada NP-duro. A través de los años el esfuerzo de muchos investigadores ha concretado en una variedad de algoritmos que han mostrado un desempeño satisfactorio, sin embargo, en la actualidad no existe un algoritmo heurístico capaz de encontrar la solución óptima para todas las posibles instancias de un problema de este tipo a pesar de los esfuerzos de la comunidad científica. En este trabajo se presenta un estudio de los algoritmos más relevantes y un análisis comparativo de los principales trabajos relacionados con 1D-BPP con el fin de identificar componentes y/o estrategias que muestran un impacto positivo en el desempeño de estos. Se propone una nueva versión de la metahuerística Grouping Genetic Algorithm with Controlled Gene-Transmission (GGA-CGT) la cuál denominamos GGA CGT/D. Para este algoritmo se diseñaron tres estrategias: un método de selección del límite inferior más adecuado al problema que se resuelve, un método de reducción del problema y un método de diversificación de soluciones los cuales ayudaron a mejorar el desempeño del algoritmo original. Los resultados obtenidos de un extenso estudio computacional confirman que GGA-CGT/D logra superar el desempeño de los mejores algoritmos del estado del arte. Como caso de estudio se seleccionó el conjunto de instancias más aceptado para comparar algoritmos competitivos. Este conjunto es parte de BPPLIB e incluye a la clase Hard28, que parece tener el mayor grado de dificultad para los algoritmos BPP. También se aborda un nuevo conjunto de instancias retadoras de grandes dimensiones llamado BPP𝑣𝑢_𝑐. El algoritmo propuesto puede resolver óptimamente todas las instancias seleccionadas de BBPLIB, y un gran número de BPP𝑣𝑢_𝑐, resolviendo en total 2309 instancias difíciles, abiertas hasta el momento, de las cuales 49 no habían sido resueltas por ninguno de los algoritmos seleccionados como caso de estudio. |
| metadata.dc.type: | info:eu-repo/semantics/masterThesis |
| Appears in Collections: | Maestría en Ciencias de la Computación |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| G13070673_donacion_tesis_bib.pdf | 1.9 MB | Adobe PDF | View/Open | |
| G13070673_donacion_tesis_licencia.pdf Until 2050-01-01 | 119.09 kB | Adobe PDF | View/Open Request a copy |
This item is protected by original copyright |
This item is licensed under a Creative Commons License
