Heurística inspirada en el análisis sistémico del “Vecino más cercano”, para solucionar instancias simétricas TSP, empleando una base comparativa multicriterio

dc.contributor.advisorJaramillo Álvarez, Gloria Patricia (Thesis advisor)spa
dc.contributor.authorPérez Rave, Jorge Ivánspa
dc.date.accessioned2019-06-24T17:36:14Zspa
dc.date.available2019-06-24T17:36:14Zspa
dc.date.issued2011spa
dc.description.abstractEsta tesis aporta evidencia que respalda al pensamiento sistémico como un pertinente campo de inspiración para el desarrollo de nuevos métodos de optimización heurística. Se delimita el alcance a la resolución del TSP simétrico como referente internacional de prueba que es. Se desarrollaron dos métodos: Sacrificio Cortoplacista Adaptativo 2-opt (SCA_2opt) y una versión mejorada (SCA_2_opt_r), los cuales son fruto del análisis sistémico de la regla vecino más cercano, encontrándole el arquetipo “Soluciones contraproducentes”. El SCA se basa en que el viajero renuncie en un momento dado a una ciudad inmediatamente cercana y se traslade hacia la segunda más cercana disponible, luego, el viajero continúa con la regla del vecino más cercano; cada que se realiza el SCA (búsqueda global) se efectúa una búsqueda local 2_opt. Las dos heurísticas resultan prometedoras en el balance entre eficacia y eficiencia en comparación con las heurísticas: vecino más cercano, Inserción más barata y 2-opt, y con 19 metaheurísticas en las categorías: Colonia de hormigas, Algoritmos genéticos, Enfriamiento simulado y Otras./Abstract. This thesis provides evidence that supports the relevant systems thinking as a field of inspiration for the development of new heuristic optimization methods. It delineates the scope of the resolution of the symmetric TSP as an international benchmark proves it. Two methods were developed: Adaptive short-term sacrifice 2-opt (SCA_2opt) and an enhanced version (SCA_2_opt_r), which are based on analysis systemic nearest neighbor rule, finding the archetypal "Solutions counterproductive ". The SCA is based on the traveler resign at any time a nearby town immediately and move to the second nearest available Of course, the traveler continues with the nearest neighbor rule, each SCA is performed (global search) is performed a local search 2_opt. The two heuristics are promising in the balance between effectiveness and efficiency compared to the heuristics: nearest neighbor, cheapest insertion and 2-opt, and with 19 metaheuristics in categories: ant colony, genetic algorithms, simulated annealing and Othe.spa
dc.description.degreelevelMaestríaspa
dc.format.mimetypeapplication/pdfspa
dc.identifier.eprintshttp://bdigital.unal.edu.co/5443/spa
dc.identifier.urihttps://repositorio.unal.edu.co/handle/unal/8756
dc.language.isospaspa
dc.relation.ispartofUniversidad Nacional de Colombia Sede Medellín Facultad de Minas Escuela de Sistemasspa
dc.relation.ispartofEscuela de Sistemasspa
dc.relation.referencesPérez Rave, Jorge Iván (2011) Heurística inspirada en el análisis sistémico del “Vecino más cercano”, para solucionar instancias simétricas TSP, empleando una base comparativa multicriterio. Maestría thesis, Universidad Nacional de Colombia, Sede Medellín.spa
dc.rightsDerechos reservados - Universidad Nacional de Colombiaspa
dc.rights.accessrightsinfo:eu-repo/semantics/openAccessspa
dc.rights.licenseAtribución-NoComercial 4.0 Internacionalspa
dc.rights.urihttp://creativecommons.org/licenses/by-nc/4.0/spa
dc.subject.ddc0 Generalidades / Computer science, information and general worksspa
dc.subject.proposalSacrificio cortoplacista adaptativospa
dc.subject.proposalOptimización Combinatoriaspa
dc.subject.proposalMetaheurísticasspa
dc.subject.proposalPensamiento sistémicospa
dc.subject.proposalHeurísticaspa
dc.subject.proposalInstancias simétricas TSP / Adaptive short-term sacrificespa
dc.subject.proposalOptimization combinatorics, Metaheuristics, Systems thinkingspa
dc.subject.proposalHeuristicsspa
dc.subject.proposalSymmetric TSP instancesspa
dc.titleHeurística inspirada en el análisis sistémico del “Vecino más cercano”, para solucionar instancias simétricas TSP, empleando una base comparativa multicriteriospa
dc.typeTrabajo de grado - Maestríaspa
dc.type.coarhttp://purl.org/coar/resource_type/c_bdccspa
dc.type.coarversionhttp://purl.org/coar/version/c_ab4af688f83e57aaspa
dc.type.contentTextspa
dc.type.driverinfo:eu-repo/semantics/masterThesisspa
dc.type.redcolhttp://purl.org/redcol/resource_type/TMspa
dc.type.versioninfo:eu-repo/semantics/acceptedVersionspa
oaire.accessrightshttp://purl.org/coar/access_right/c_abf2spa

Archivos

Bloque original

Mostrando 1 - 1 de 1
Cargando...
Miniatura
Nombre:
71225056.2011.pdf
Tamaño:
1.19 MB
Formato:
Adobe Portable Document Format
Descripción:
Tesis de Maestría en Ingeniería - Ingeniería de Sistemas