Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00100227
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 10:15:45 AM
Last modification on : Sunday, March 28, 2021 - 11:18:03 PM

Identifiers

  • HAL Id : inria-00100227, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

190