Abstract: This paper produces a new algorithm called HEGA for solving the CARP（Capacitated Arc Routing Problem）.The new algorithm improves the method of coding chromosomes and structure of population in traditional genetic algorithm，and some of its ideas derive from Partheno-Genetic Algorithm（PGA） and memetic algorithm.HEGA can solve the multi-vehicle CARP which is hardly to be solved by existing algorithms，in solving general CARP，its efficiency and accuracy are more excellent as well.Related with a typical case of optimizing the routings of sprinkler cars，the new method is evaluated with a real set of data.