EXPERIMENTOS COMPUTACIONAIS COM HEURÍSTICAS DE MELHORIAS PARA O PROBLEMA DO CAIXEIRO VIAJANTE Claudio Barbieri da Cunha1
Departamento de Engenharia de Transportes Escola Politécnica da Universidade de São Paulo

Ulisses de Oliveira Bonasser2 Fernando Teixeira Mendes Abrahão3
Departamento de Engenharia de Transportes Escola Politécnica da Universidade de São Paulo ILA – Instituto de Logística da Aeronáutica RESUMO Neste artigo são analisadas estratégias alternativas de implementação computacional para heurísticas de melhorias aplicadas ao Problema do Caixeiro Viajante. As heurísticas são do tipo k-opt, na qual k arcos são removidos de um roteiro inicialmente definido e substituídos por outros k arcos, com a finalidade de diminuir a …exibir mais conteúdo…

Sob a ótica de otimização, o PCV pertence à categoria conhecida como NP-difícil (do inglês “NP-hard”), o que significa que possui ordem de complexidade exponencial. Em outras palavras, o esforço computacional para a sua resolução cresce exponencialmente com o tamanho do problema (dado pelo número de pontos a serem atendidos). Em termos práticos, isto significa que não é possível resolver até a otimalidade problemas reais pertencentes à classe NP-difícil. Consequentemente, os métodos de solução aplicados a instâncias reais são, em geral, heurísticos, isto é, não asseguram a obtenção da solução ótima do ponto de vista matemático. Nesse contexto, o presente trabalho objetiva analisar aspectos específicos da implementação computacional de heurísticas de melhorias, do tipo 2-opt e 3-opt para a solução do PCV. Mais especificamente, pretende-se verificar qual a influência, na qualidade dos resultados obtidos e nos tempos de processamento, da solução inicialmente submetida aos procedimentos de melhorias. Adicionalmente, pretende-se verificar também se há vantagens na utilização conjunta e sequencial das rotinas 2-opt e 3-opt, considerando diferentes critérios de parada. Todas as análises baseiam-se em vários experimentos computacionais, aplicados a diferentes problemas clássicos da literatura. Este artigo está organizado da seguinte forma: o próximo item aborda os principais aspectos do PCV e descreve os