Competitive Memetic Algorithms for Arc Routing Problems

Philippe Lacomme (), Christian Prins () and Wahiba Ramdane-Cherif ()

Annals of Operations Research, 2004, vol. 131, issue 1, 159-185

Abstract: 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. Copyright Kluwer Academic Publishers 2004

Keywords: Capacitated Arc Routing Problem; CARP; metaheuristic; memetic algorithm (search for similar items in EconPapers)
Date: 2004
References: Add references at CitEc
Citations: View citations in EconPapers (26)

Downloads: (external link)
http://hdl.handle.net/10.1023/B:ANOR.0000039517.35989.6d (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:131:y:2004:i:1:p:159-185:10.1023/b:anor.0000039517.35989.6d

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/B:ANOR.0000039517.35989.6d

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().