HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

New Algorithms for the General Arc Routing Problems

Philippe Lacomme Christian Prins 1 Wahiba Ramdane-Cherif 2
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.
Document type :
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 10:15:45 AM
Last modification on : Friday, February 4, 2022 - 3:21:02 AM


  • 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, LORIA - Université de Lorraine. 2004, 15 p. ⟨inria-00100227⟩



Record views