BRKGA algorithm for the capacitated arc routing problem

C. Martinez, I. Loiseau, M.G.C. Resende, and S. Rodriguez

Electronic Notes in Theoretical Computer Science, vol. 281, pp. 69-83, 2011


We propose a new algorithm for the Capacitated Arc Routing Problem (CARP). Our motivation to deal with this problem is related to its application in several real world scenarios such as street sweeping, urban waste collection and electric meter reading just to mention a few.

Based on BRKGA metaheuristic, our algorithm introduces a new random key encoding for CARP, mutation to random keys strings, a restart phase to avoid stagnation and local search.

The algorithm was tested with several well-known instances from the literature. The results obtained were competitive in terms of objective function value and required computational time.

[ DOI ]

Go back

Mauricio G.C. Resende's Home Page

Last modified: 15 July 2013

Copyright Notice