Publicación:
Diseño de una metaheurístico para la solución del problema de la mochila múltiple con configuraciones

Vista sencilla de ítem
dc.contributor.advisorLópez Pereira, Jorge Mariospa
dc.contributor.authorSarmiento, Andrés Felipe
dc.date.accessioned2021-11-25T22:22:49Z
dc.date.available2021-11-25T22:22:49Z
dc.date.issued2021-11-25
dc.description.abstractThe present project seeks to develop a metaheuristic for solving a variant of the Multiple Knapsack Problem, based on a recently developed metaheuristic for solving continuous domain optimization problems. To achieve this, an algorithm that has the logic behind the initial model was developed and new functions were added to make it work properly with the binary encoding of the decision variables of the problem. In order to make comparison, a couple of variants of the main model were designed and an experiment was built in which several runs were performed, with predefined and tested with other algorithms instances, in a random order for each variant, and finally get some descriptive data, GAP’s and average execution times. Results indicate a competent performance of the metaheuristics compared to exact algorithms like CPLEX, while it’s less competent compared to other metaheuristics developed previously for this type of optimization problems, in terms of both target value and execution time.spa
dc.description.degreelevelPregradospa
dc.description.degreenameIngeniero(a) Industrialspa
dc.description.modalityTrabajos de Investigación y/o Extensiónspa
dc.description.resumenEn el presente proyecto se busca desarrollar una metaheurística para resolver una variante del problema de la mochila múltiple, basada en una metaheurística recientemente desarrollada para resolver problemas de dominio continuo. Para lograrlo, se desarrolló un algoritmo que mantiene la lógica del modelo inicial y se agregaron nuevas funciones para que funcionase adecuadamente con la codificación binaria de las variables de decisión del problema. Con el fin de realizar comparaciones, se diseñaron variantes del algoritmo principal y se construyó un experimento en el que se realizaron varias corridas, con instancias predefinidas y probadas con otros algoritmos, en un orden aleatorio para cada variante, para al final obtener algunos datos descriptivos, los GAP’s y los tiempos de ejecución medios. Los resultados indican un desempeño competente con respecto a algoritmos exactos como CPLEX, mientras que es inferior a otras metaheurísticas desarrolladas con anterioridad para este tipo problemas de optimización, en términos tanto de valor objetivo como de tiempo de ejecución en el presente proyecto se busca desarrollar una metaheurística para resolver una variante del problema de la mochila múltiple, basada en una metaheurística recientemente desarrollada para resolver problemas de dominio continuo. Para lograrlo, se desarrolló un algoritmo que mantiene la lógica del modelo inicial y se agregaron nuevas funciones para que funcionase adecuadamente con la codificación binaria de las variables de decisión del problema. Con el fin de realizar comparaciones, se diseñaron variantes del algoritmo principal y se construyó un experimento en el que se realizaron varias corridas, con instancias predefinidas y probadas con otros algoritmos, en un orden aleatorio para cada variante, para al final obtener algunos datos descriptivos, los GAP’s y los tiempos de ejecución medios. Los resultados indican un desempeño competente con respecto a algoritmos exactos como CPLEX, mientras que es inferior a otras metaheurísticas desarrolladas con anterioridad para este tipo problemas de optimización, en términos tanto de valor objetivo como de tiempo de ejecución.
dc.description.tableofcontentsResumen .................................................................................................................... viiispa
dc.description.tableofcontentsAbstract.....................................................................................................................ixspa
dc.description.tableofcontentsIntroducción ....................................................................................................1spa
dc.description.tableofcontentsObjetivos..............................................................................................................3spa
dc.description.tableofcontentsObjetivo General....................................................................................3spa
dc.description.tableofcontentsObjetivos específicos..........................................................................3spa
dc.description.tableofcontentsRevisión bibliográfica...............................................................................4spa
dc.description.tableofcontentsMarco conceptual.................................................................................4spa
dc.description.tableofcontentsAlgoritmo...................................................................................................4spa
dc.description.tableofcontentsAlgoritmo de aproximaciónn.......................................................................4spa
dc.description.tableofcontentsAlgoritmos exactos.....................................................................................4spa
dc.description.tableofcontentsHeurística..................................................................................................5spa
dc.description.tableofcontentsMetaheurística...........................................................................................5spa
dc.description.tableofcontentsProblema de la mochila.............................................................................5spa
dc.description.tableofcontentsProblemas NP.............................................................................................6spa
dc.description.tableofcontentsProblemas NP-Completo...........................................................................6spa
dc.description.tableofcontentsProblemas P o tiempo polinómico............................................................6spa
dc.description.tableofcontentsValor k.....................................................................................................6spa
dc.description.tableofcontentsEstado del arte ..............................................................................................7spa
dc.description.tableofcontentsProblema de la mochila múltiple con configuración y metaheurística usadas ............................................................................7spa
dc.description.tableofcontentsMetaheurística de fertilidad de suelos ...............................9spa
dc.description.tableofcontentsMateriales y métodos ..............................................................................11spa
dc.description.tableofcontentsCondiciones del trabajo ...............................................................11spa
dc.description.tableofcontentsDesarrollo de la metaheurística ............................................11spa
dc.description.tableofcontentsLógica del algoritmo final .......................................................................12spa
dc.description.tableofcontentsPrueba de parámetros......................................................................28spa
dc.description.tableofcontentsDiseño experimentalL..........................................................................29spa
dc.description.tableofcontentsDiseño de nuevas versiones ......................................................................29spa
dc.description.tableofcontentsSelección de instancias s.............................................................................30spa
dc.description.tableofcontentsDetalles adicionales del experimento ....................................................30spa
dc.description.tableofcontentsResultados y discusionesspa
dc.description.tableofcontentsConclusiones.......................................................................32spa
dc.description.tableofcontentsRecomendaciones.......................................................................................39spa
dc.description.tableofcontentsBibliografía ...................................................................................................41spa
dc.description.tableofcontentsAnexos .........................................................................................................................44spa
dc.description.tableofcontentsAnexo 1 Instancias utilizadas en formato Excel L.....................44spa
dc.description.tableofcontentsAnexo 2 Scripts de las diferentes versiones de la metaheurística ..................44spa
dc.description.tableofcontentsAnexo 3 Archivo con resultados del experimento ................45spa
dc.description.tableofcontentsAnexo 4 Ejemplo numérico del algoritmo .................................45spa
dc.format.mimetypeapplication/pdfspa
dc.identifier.urihttps://repositorio.unicordoba.edu.co/handle/ucordoba/4718
dc.language.isospaspa
dc.publisher.facultyFacultad de Ingenieríaspa
dc.publisher.placeMontería, Córdoba, Colombiaspa
dc.publisher.programIngeniería Industrialspa
dc.rightsCopyright Universidad de Córdoba, 2021spa
dc.rights.accessrightsinfo:eu-repo/semantics/openAccessspa
dc.rights.creativecommonsAtribución-NoComercial-SinDerivadas 4.0 Internacional (CC BY-NC-ND 4.0)spa
dc.rights.urihttps://creativecommons.org/licenses/by-nc-nd/4.0/spa
dc.subject.keywordsMetaheuristicsspa
dc.subject.keywordsFarmland Fertilityspa
dc.subject.keywordsCorrective Heuristicsspa
dc.subject.keywordsMultiple Knapsack Problemspa
dc.subject.proposalMetaheurísticaspa
dc.subject.proposalFertilidad de Suelosspa
dc.subject.proposalHeurística Correctivaspa
dc.subject.proposalProblema de la Mochilaspa
dc.titleDiseño de una metaheurístico para la solución del problema de la mochila múltiple con configuracionesspa
dc.typeTrabajo de grado - Pregradospa
dc.type.coarhttp://purl.org/coar/resource_type/c_7a1fspa
dc.type.contentTextspa
dc.type.driverinfo:eu-repo/semantics/bachelorThesisspa
dc.type.redcolhttps://purl.org/redcol/resource_type/TPspa
dc.type.versioninfo:eu-repo/semantics/submittedVersionspa
dcterms.referencesAbdel-Basset, M., El-Shahat, D., Faris, H., & Mirjalili, S. (2019). A binary multi-verse optimizer for 0-1 multidimensional knapsack problems with application in interactive multimedia systems. Computers and Industrial Engineering, 132(March), 187–206. https://doi.org/10.1016/j.cie.2019.04.025spa
dcterms.referencesAdouani, Y., Jarboui, B., & Masmoudi, M. (2020). Efficient matheuristic for the generalised multiple knapsack problem with setup. European Journal of Industrial Engineering, 14(5), 715–741. https://doi.org/10.1504/EJIE.2020.109906spa
dcterms.referencesAl-Herz, A., & Pothen, A. (2019). A 2/3-approximation algorithm for vertex-weighted matching. Discrete Applied Mathematics, xxxx. https://doi.org/10.1016/j.dam.2019.09.013spa
dcterms.referencesAmiri, A. (2020). A Lagrangean based solution algorithm for the knapsack problem with setups. Expert Systems with Applications, 143, 113077. https://doi.org/10.1016/j.eswa.2019.113077spa
dcterms.referencesChebil, K., & Khemakhem, M. (2015). A dynamic programming algorithm for the Knapsack Problem with Setup. Computers and Operations Research, 64, 40–50. https://doi.org/10.1016/j.cor.2015.05.005spa
dcterms.referencesDantas, S., De Figueiredo, C. M. H., Petito, P., & Teixeira, R. B. (2019). A General Method for Forbidden Induced Subgraph Sandwich Problem NP-completeness. Electronic Notes in Theoretical Computer Science, 346, 393–400. https://doi.org/10.1016/j.entcs.2019.08.035spa
dcterms.referencesDella Croce, F., Salassa, F., & Scatamacchia, R. (2017). An exact approach for the 0–1 knapsack problem with setups. Computers and Operations Research, 80, 61–67. https://doi.org/10.1016/j.cor.2016.11.015spa
dcterms.referencesDokeroglu, T., Sevinc, E., Kucukyilmaz, T., & Cosar, A. (2019). A survey on new generation metaheuristic algorithms. Computers and Industrial Engineering, 137(August), 106040. https://doi.org/10.1016/j.cie.2019.106040spa
dcterms.referencesFigueroa, I., Jiménez, C., Allende-Cid, H., & Leger, P. (2019). Developing usability heuristics with PROMETHEUS: A case study in virtual learning environments. Computer Standards and Interfaces, 65(March), 132–142. https://doi.org/10.1016/j.csi.2019.03.003spa
dcterms.referencesGoderbauer, S., Comis, M., & Willamowski, F. J. L. (2019). The synthesis problem of decentralized energy systems is strongly NP-hard. Computers and Chemical Engineering, 124, 343–349. https://doi.org/10.1016/j.compchemeng.2019.02.002spa
dcterms.referencesGurski, F., Rehs, C., & Rethmann, J. (2019). Knapsack problems: A parameterized point of view. Theoretical Computer Science, 775, 93–108. https://doi.org/10.1016/j.tcs.2018.12.019spa
dcterms.referencesHassan, A., & Pillay, N. (2019). Hybrid metaheuristics: An automated approach. Expert Systems with Applications, 130, 132–144. https://doi.org/10.1016/j.eswa.2019.04.027spa
dcterms.referencesJing, R. J., Yuan, C. M., & Gao, X. S. (2019). A polynomial-time algorithm to compute generalized Hermite normal forms of matrices over Z[x]. Theoretical Computer Science, 755(11688101), 89–109. https://doi.org/10.1016/j.tcs.2018.07.003spa
dcterms.referencesKhemakhem, M., & Chebil, K. (2016). A tree search based combination heuristic for the knapsack problem with setup. Computers and Industrial Engineering, 99, 280–286. https://doi.org/10.1016/j.cie.2016.07.021spa
dcterms.referencesKorte, B., & Vygen, J. (2018). Bin-Packing. In Springer Link (Vol. 21, pp. 489–507). https://doi.org/10.1007/978-3-662-56039-6_18spa
dcterms.referencesLahyani, R., Chebil, K., Khemakhem, M., & Coelho, L. C. (2019). Matheuristics for solving the Multiple Knapsack Problem with Setup. Computers and Industrial Engineering, 129(December 2018), 76–89. https://doi.org/10.1016/j.cie.2019.01.010spa
dcterms.referencesPferschy, U., & Scatamacchia, R. (2018). Improved dynamic programming and approximation results for the knapsack problem with setups. International Transactions in Operational Research, 25(2), 667–682. https://doi.org/10.1111/itor.12381spa
dcterms.referencesRossi, F. L., & Nagano, M. S. (2019). Heuristics for the mixed no-idle flowshop with sequence-dependent setup times and total flowtime criterion. Expert Systems with Applications, 125, 40–54. https://doi.org/10.1016/j.eswa.2019.01.057spa
dcterms.referencesRycroft, R. W., & Kash, D. E. (2004). Self-organizing innovation networks: Implications for globalization. Technovation, 24(3), 187–197. https://doi.org/10.1016/S0166-4972(03)00092-0spa
dcterms.referencesShayanfar, H., & Gharehchopogh, F. S. (2018). Farmland fertility: A new metaheuristic algorithm for solving continuous optimization problems. Applied Soft Computing Journal, 71, 728–746. https://doi.org/10.1016/j.asoc.2018.07.033spa
dcterms.referencesVidal Esmoris, A. (2013). Algoritmos heurísticos en optimización [Universidad de Santagio de Compostela]. evolucionspa
dcterms.referencesZhong, T., & Young, R. (2010). Multiple Choice Knapsack Problem: Example of planning choice in transportation. Evaluation and Program Planning, 33(2), 128–137. https://doi.org/10.1016/j.evalprogplan.2009.06.007spa
dspace.entity.typePublication
oaire.accessrightshttp://purl.org/coar/access_right/c_abf2spa
oaire.versionhttp://purl.org/coar/version/c_ab4af688f83e57aaspa
Archivos
Bloque original
Mostrando 1 - 2 de 2
Miniatura
Nombre:
Sarmiento, Andrés Felipe.pdf
Tamaño:
1.17 MB
Formato:
Adobe Portable Document Format
Descripción:
Informe Final
Descargar
No hay miniatura disponible
Nombre:
AutorizaciónPublicación.pdf
Tamaño:
259.21 KB
Formato:
Adobe Portable Document Format
Descripción:
Autorización Publicación
Descargar
Bloque de licencias
Mostrando 1 - 1 de 1
No hay miniatura disponible
Nombre:
license.txt
Tamaño:
14.48 KB
Formato:
Item-specific license agreed upon to submission
Descripción:
Descargar
Colecciones
F.C.A. Trabajos de Investigación y/o Extensión