摘要：The Capacitated Arc Routing Problem (CARP) consists of visiting a subset of edges of the graph that describes the problem. CARP applications include urban waste collection and inspection of power lines. The CARP is NP-hard, even in the single-vehicle case (called Rural Postman Problem). In this case, the use of metaheuristics is an efficient solution strategy. This paper proposes a hybrid genetic algorithm for the CARP, which is tested on available instances of the literature. The results obtained until now show the effectiveness of the proposed algorithm when it is compared with lower bounds described in the literature.↓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.
其他摘要：The Capacitated Arc Routing Problem (CARP) consists of visiting a subset of edges of the graph that describes the problem. CARP applications include urban waste collection and inspection of power lines. The CARP is NP-hard, even in the single-vehicle case (called Rural Postman Problem). In this case, the use of metaheuristics is an efficient solution strategy. This paper proposes a hybrid genetic algorithm for the CARP, which is tested on available instances of the literature. The results obtained until now show the effectiveness of the proposed algorithm when it is compared with lower bounds described in the literature.
Loading...
