Algoritmos de aproximação para o problema do caixeiro viajante

• Processo: 18/13448-3
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de setembro de 2018
• Data de Término da vigência: 31 de agosto de 2019
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Mário César San Felice
• Beneficiário: Rodrigo Prata Salmen
• Instituição Sede: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brasil
• Assunto(s): Problema do caixeiro viajante (PCV) Otimização combinatória Algoritmos de aproximação Programação linear inteira Métrica
• Palavra(s)-Chave do Pesquisador: Algoritmos de Aproximação | Problema do Caixeiro-Viajante | programação linear inteira | Otimização combinatória

Resumo

O problema do caixeiro viajante (TSP), em que temos um conjunto de cidades e queremos saber qual é o circuito de comprimento mínimo que passa por todas elas exatamente uma vez, é central na área de otimização combinatória e possui diversas aplicações práticas em áreas como planejamento, logística e manufatura de microchips. Neste projeto estamos interessados tanto na sua versão mais famosa, o TSP métrico, quanto em casos particulares e generalizações deste. Este projeto tem por objetivo a introdução do candidato à pesquisa científica, bem como a complementação de sua formação em Ciência da Computação, aprofundando seu conhecimento na área de otimização combinatória. Além disso, pretendemos que esta Iniciação Científica gere um relatório técnico que seja útil para outros estudantes iniciando na área.