O problema do caixeiro viajante alugador : um estudo algorítmico

AUTOR(ES)

Paulo Henrique Asconavieta da Silva

FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

19/12/2011

RESUMO

O Problema do Caixeiro Alugador (CaRS) é uma variante ainda não descrita na literatura do clássico Problema do Caixeiro Viajante onde o tradicional tour de visitas do caixeiro pode ser decomposto em caminhos contíguos e que podem ser realizados em diferentes carros alugados. O problema consiste em determinar o ciclo hamiltoniano que resulte em um custo final mínimo, considerando o custo da rota adicionado ao custo de uma provável penalização paga em cada troca de veículos na rota, penalização devida ao retorno do carro descartado até a sua cidade base. Sem perda para a generalidade do caso, os custos do aluguel do carro podem ser considerados embutidos nos custos da rota do carro. O presente trabalho introduz o problema geral e o exemplifica, caracterizando igualmente algumas variantes associadas. Uma análise geral da complexidade desse problema combinatório é descrita, visando justificar sua classificação na classe NP-difícil. Um banco de instâncias para o problema é apresentado, descrevendo-se a metodologia de sua constituição. O problema proposto também é objeto de um estudo algorítmico experimental baseado na aplicação de seis metaheurísticas de solução, representando adaptações do melhor do estado da arte em programação heurística. Novas vizinhanças, procedimentos construtivos, operadores de busca, agentes evolucionários, cooperação por multiferomônios, são criados para o caso. Experimentos computacionais comparativos e testes de desempenho são realizados sobre uma amostra de 60 instâncias, visando oferecer um algoritmo de solução competitivo para o problema. Conclui-se pela vantagem do algoritmo transgenético em todos os conjuntos de instâncias

ASSUNTO(S)

memetic algorithm ant colony computational transgenic evolutionary computation o problema do caixeiro alugador metaheurísticas grasp/vnd colônia de formigas computação evolucionária algoritmo memético transgenética computacional sistemas de computacao the car rental salesman problem metaheuristics grasp/vnd

Documentos Relacionados

• Plasticidade sináptica e o problema do caixeiro viajante
• Algoritmo treansgenético na solução do problema do Caixeiro Viajante
• Metodologia estatística na solução do problema do caixeiro viajante e na avaliação de algoritmos : um estudo aplicado à transgenética computacional
• Algoritmos Evolucionários Aplicados ao Problema do Caixeiro Viajante Multiobjetivo.
• Algoritmo memetico para o problema do caixeiro viajante assimetrico como parte de um framework para algoritmos evolutivos