Caixeiro viajante

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 distância total percorrida. Neste caso, diferentes estratégias envolvendo heurísticas do tipo 2-opt e 3-opt foram testadas, de forma a avaliar vários aspectos, entre os quais a influência da solução inicialmente submetida aos procedimentos de melhorias e o uso conjunto das heurísticas 2-opt e 3-opt, considerando diferentes critérios de parada. ABSTRACT In this paper, alternative strategies for the computational implementation of improvement heuristics for the Traveling Salesman Problem are analyzed. The heuristics are based on the k-opt algorithm in which k arcs are removed from a tour initially obtained and replaced by k other arcs, aiming to reduce the total distance traveled. In the present study, different solution strategies were analyzed and tested, involving 2-opt and 3-opt heuristics. The major concern is to identify the influence of initial solution tour which is submitted to the improvement procedures, as well as the joint use of 2-opt and 3-opt procedures with different stop criteria.

1. INTRODUÇÃO O Problema do Caixeiro Viajante – PCV (do inglês Traveling Salesman Problem - TSP) é um dos problemas mais estudados em otimização combinatória (Laporte, 1992). Apesar da sua definição singela, o PCV representa, até hoje, um