New Algorithms for the General 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 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 : This paper considers an Extended version of the Capacitated Arc Routing Problem (E-CARP), obtained by adding several realistic constraints (including for example prohibited turns) to the basic CARP. We propose a resolution method to a mono objective and a hierarchical bi-objective optimization of the CARP. Our approach is based on: 1) a cutting plane algorithm to compute optimal solutions for medium-scale instances 2) a Genetic Algorithm for medium and large-scale instances. Dedicated crossover, mutations and construction heuristics for the initial population are presented for the E-CARP. The well-known construction heuristics have been adjusted taking into account the realistic constrains added to the basic CARP. A set of 11 benchmark problems with up to 16 nodes and 52 arcs is proposed to evaluate performances of the two approaches. The Xpress library is used to provide optimal solutions for small and medium size problems using the cutting plane algorithm. Using this approach about 50% E-CARP library problems have been optimally solved. The experiments prove that the GA is nearly optimal and remains still adequate for the bi-objective optimisation problem.
Type de document :
[Intern report] A04-R-340 || lacomme04c, 2004, 15 p
Liste complète des métadonnées
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:15:45
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48


  • HAL Id : inria-00100227, version 1



Philippe Lacomme, Christian Prins, Wahiba Ramdane-Cherif. New Algorithms for the General Arc Routing Problems. [Intern report] A04-R-340 || lacomme04c, 2004, 15 p. 〈inria-00100227〉



Consultations de la notice