trabalho

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

AUTOR:
Paulo Henrique Asconavieta da Silva
FONTE
IBICT
DATA DE PUBLICAÇÃO
19/12/2011
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

Plasticidade sináptica e o problema do caixeiro viajante

AUTOR:
Ricardo Fábio Sato
DATA DE PUBLICAÇÃO
2010
FONTE
IBICT
Propõem-se algoritmos para