Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-11-01T21:17:49Z No. of bitstreams: 1 EmersonBezerraDeCarvalho_DISSERT.pdf: 1150853 bytes, checksum: f0f5998d8f74eb082da1133fbcf4b27a (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-11-07T21:35:18Z (GMT) No. of bitstreams: 1 EmersonBezerraDeCarvalho_DISSERT.pdf: 1150853 bytes, checksum: f0f5998d8f74eb082da1133fbcf4b27a (MD5) / Made available in DSpace on 2017-11-07T21:35:18Z (GMT). No. of bitstreams: 1 EmersonBezerraDeCarvalho_DISSERT.pdf: 1150853 bytes, checksum: f0f5998d8f74eb082da1133fbcf4b27a (MD5) Previous issue date: 2017-07-24 / A heur?stica de Lin e Kernighan (LK) ? um dos m?todos mais eficientes para o Problema do Caixeiro Viajante (PCV). Devido a este fato, diferentes implementa??es para a LK foram propostas na literatura e esta heur?stica ? tamb?m usada como parte de diversos algoritmos meta-heur?sticos. A heur?stica LK tem sido utilizada no contexto do PCV multiobjetivo (PCVM) conforme proposta originalmente por seus autores, isto ?, com o foco mono-objetivo. Este trabalho investiga a extens?o da heur?stica LK no contexto multiobjetivo. ? investigado o potencial de extens?es da LK combinadas com outras t?cnicas meta-heur?sticas. Resultados de um experimento computacional para inst?ncias do PCVM com 2, 3 e 4 objetivos s?o reportados. / The Lin and Kernighan?s heuristic (LK) is one of the most effective methods for the Traveling Salesman Problem (TSP). Due to this fact, different implementations for the LK were proposed in literature and this heuristic is also used as part of various meta-heuristic algorithms. LK has been used in the context of the multi-objective TSP (MTSP) as originally proposed by its authors, i.e., with a single objective focus. This study investigates variants of the LK heuristic in the multi-objective context. We investigate the potential of LK extensions combined with other metaheuristic techniques. Results of a computational experimental are reported for MTSP instances with 2, 3 and 4 objectives.