Portal de Periódicos da CAPES

Um Algoritmo Evolutivo para o Problema de Roteamento em Arcos Capacitados

2009; Volume: 1; Issue: 2 Linguagem: Português

10.7177/sg.2006.sgv1n2a2

1980-5160

Dalessandro Soares Vianna, Roberta Claudino Barreto Pessanha Gomes,

Business and Management Studies

O problema de roteamento em arcos capacitados (Capacitated Arc Routing Problem - CARP) consiste em visitar um subconjunto de arestas do grafo que descreve o problema, atendendo as suas demandas. Aplicacoes possiveis para o CARP sao a coleta de lixo urbano e a inspecao de linhas de forca. O CARP e um problema NP-dificil, mesmo no caso onde existe apenas um veiculo (chamado de Problema do Carteiro Rural). Neste caso, o uso de metaheuristicas surge como uma estrategia de solucao eficiente.Este trabalho apresenta um algoritmo genetico hibrido para o CARP, que e testado em instâncias disponiveis na literatura. Os resultados obtidos ate o momento demonstram a eficiencia do algoritmo proposto quando comparado com limites inferiores descritos na literatura.