Caixeiro viajante

Disponível somente no TrabalhosFeitos
  • Páginas : 26 (6349 palavras )
  • Download(s) : 0
  • Publicado : 2 de dezembro de 2012
Ler documento completo
Amostra do texto
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ísticada 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, diferentesestraté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 improvementheuristics 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 ofinitial 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, umdos desafios da Pesquisa Operacional. Centenas de artigos já foram publicados sobre o PCV. Reinelt (1994) vai mais além, ao afirmar que o PCV é um dos mais proeminentes dentre um amplo conjunto de problemas de otimização combinatória. Segundo o autor, o estudo do PCV tem atraído pesquisadores de diferentes campos, entre os quais pesquisa operacional, matemática, física, biologia, inteligênciaartificial, entre outros. Isso se deve ao fato de que, apesar da simplicidade da sua formulação, no PCV é possível encontrar a maioria das questões que envolvem otimização combinatória; conseqüentemente, o mesmo tem sido usado como “benchmark” para avaliação de novos algoritmos e estratégias de solução que envolvem busca tabu, algoritmos genéticos, “simulated annealing”, redes neurais, entre outros.Não só a questão do desempenho computacional tem atraído o interesse pelo PCV. Inúmeros problemas reais são modelados como problemas do tipo caixeiro viajante ou suas variantes. Consequentemente, existe uma importante necessidade de novos algoritmos de solução. Entre esses problemas pode-se citar o problema de produção que corresponde ao sequenciamento de n tarefas em uma única máquina, de forma aminimizar o tempo total de

Trabalho apresentado no XVI Congresso da Anpet – Associação Nacional de Pesquisa e Ensino em Transportes. e publicado nos anais do evento. Natal, outubro de 2002.

execução das mesmas. Em linhas de montagem de componentes eletrônicos busca-se encontrar, por exemplo, o roteiro de mínima distância para um equipamento cuja tarefa é soldar todos os componentes de umaplaca eletrônica. O menor percurso total do equipamento para percorrer todos os pontos da placa está diretamente associado à produtividade da linha (Souza, 1993). Problemas de cristalografia e de controle de robôs também são citados (Helsgaun, 2000, Reinelt, 1994). Isso para não falar nos inúmeros problemas que envolvem a roteirização de veículos. Problemas de roteirização de veículos são muitas...
tracking img