Um algoritmo evolutivo para o problema de roteamento em arcos capacitados

Dalessandro Soares Vianna, Roberta Claudino Barreto Pessanha Gomes

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.

Palavras-chave


Roteamento de veículos; Arcos capacitados; Algoritmos genéticos

Texto completo:

PDF


DOI: https://doi.org/10.7177/sg.2006.SGV1N2A2

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

 

ISSN: 1980-5160

Rua Passo da Pátria 156, bloco E, sala Sistemas & Gestão, Escola de Engenharia, São Domingos, Niterói, RJ, CEP: 24210-240

Tel.: (21) 2629-5616

Correspondência: Caixa Postal LATEC: 100175, CEP 24.020-971, Niterói, RJ