Journal
ANNALS OF OPERATIONS RESEARCH
Volume 131, Issue 1-4, Pages 159-185Publisher
SPRINGER
DOI: 10.1023/B:ANOR.0000039517.35989.6d
Keywords
Capacitated Arc Routing Problem; CARP; metaheuristic; memetic algorithm
Categories
Ask authors/readers for more resources
The Capacitated Arc Routing Problem or CARP arises in applications like waste collection or winter gritting. Metaheuristics are tools of choice for solving large instances of this NP-hard problem. The paper presents basic components that can be combined into powerful memetic algorithms (MAs) for solving an extended version of the CARP (ECARP). The best resulting MA outperforms all known heuristics on three sets of benchmark files containing in total 81 instances with up to 140 nodes and 190 edges. In particular, one open instance is broken by reaching a tight lower bound designed by Belenguer and Benavent, 26 best-known solutions are improved, and all other best-known solutions are retrieved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available