Competitive Memetic Algorithms for Arc Routing Problems

Philippe Lacomme Christian Prins 1 Wahiba Ramdane-Cherif 2
1 Tech-CICO - TECHnologies pour la Coopération, l’Interaction et les COnnaissances dans les collectifs
UTT - Université de Technologie de Troyes, CNRS - Centre National de la Recherche Scientifique : FRE2732
2 MACSI - Industrial system modeling, analysis and operation
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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 instances are broken by reaching a tight lower bound designed by Belenguer and Benavent, 26 solutions are improved, and all other best-known solutions are retrieved.
Type de document :
Article dans une revue
Annals of Operations Research, Springer Verlag, 2004, 131 (1-4), pp.159-185
Liste complète des métadonnées

https://hal.inria.fr/inria-00100062
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:13:49
Dernière modification le : mardi 27 février 2018 - 14:40:03

Identifiants

  • HAL Id : inria-00100062, version 1

Collections

Citation

Philippe Lacomme, Christian Prins, Wahiba Ramdane-Cherif. Competitive Memetic Algorithms for Arc Routing Problems. Annals of Operations Research, Springer Verlag, 2004, 131 (1-4), pp.159-185. 〈inria-00100062〉

Partager

Métriques

Consultations de la notice

128