Open AccessBRKGA Algorithm for the Capacitated Arc Routing Problem
Author(s) -
Cristian A. Martínez,
Irène Loiseau,
Maurício G. C. Resende,
Susana Alicia Constanza Rodríguez
Publication year - 2011
Publication title -
electronic notes in theoretical computer science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.242
H-Index - 60
ISSN - 1571-0661
DOI - 10.1016/j.entcs.2011.11.026
Subject(s) - arc routing , computer science , key (lock) , routing (electronic design automation) , mathematical optimization , metaheuristic , encoding (memory) , algorithm , arc (geometry) , mathematics , artificial intelligence , computer network , geometry , computer security
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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom