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.