Métodos heurísticos para resolução do problema do caixeiro viajante simétrico

• Processo: 05/56313-0
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de novembro de 2005
• Data de Término da vigência: 31 de outubro de 2006
• Área de conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Maristela Oliveira dos Santos
• Beneficiário: Larissa Alves Petri
• Instituição Sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
• Assunto(s): Algoritmos genéticos Heurística Problema do caixeiro viajante (PCV) Otimização combinatória
• Palavra(s)-Chave do Pesquisador: Algoritmo Genetico | Caixeiro Viajante | Heuristicas | Otimizacao

Resumo

Neste trabalho de iniciação científica implementaremos várias heurísticas para resolução do problema do caixeiro viajante. Dentre as heurísticas, trabalharemos com uma baseada no algoritmo genético e outra nas heurísticas de melhoria. A heurística de melhoria é do tipo k-opt, na qual k arcos são removidos de um roteiro inicial e substituídos por outros k-arcos com o objetivo de diminuir a distância total percorrida neste roteiro. Os roteiros iniciais serão obtidos utilizando uma heurística de inserção, tanto para o algoritmo genético quanto para as heurísticas de melhorias. Nas heurísticas de melhorias, implementaremos diferentes estratégias baseadas no trabalho de Cunha et al. (2002). Para o algoritmo genético, estudaremos como representar as soluções do problema, e utilizaremos operações de cruzamento e mutação para gerar novos indivíduos que serão incorporados à população inicial. Após a implementação dos métodos heurísticos resolveremos alguns exemplos do TSPLIB e os resultados serão comparados considerando o tempo computacional e a qualidade das soluções obtidas após um certo critério de parada. Consideramos também uma modificação do algoritmo genético, ou seja, após um certo número de iterações, faremos uma busca local considerando as heurísticas de melhorias implementadas. Além da abordagem baseada em heurísticas, pretendemos estudar algumas formulações matemáticas para esse problema e resolver uma delas utilizando o CPLEX 7.0. (AU)