Um algoritmo evolutivo para o problema de roteamento em arcos capacitados

Resumo

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 às suas demandas. Aplicações possíveis para o CARP são a coleta de lixo urbano e a inspeção de linhas de força. O CARP é um problema NP-difícil, mesmo no caso onde existe apenas um veículo (chamado de Problema do Carteiro Rural). Neste caso, o uso de metaheurísticas surge como uma estratégia de solução eficiente.Este trabalho apresenta um algoritmo genético híbrido para o CARP, que é testado em instâncias disponíveis na literatura. Os resultados obtidos até o momento demonstram a eficiência do algoritmo proposto quando comparado com limites inferiores descritos na literatura.