Abstract: The Capacitated Arc Routing Problem (CARP) is a difficult vehicle routing problem, where given an undirected graph, the objective is to minimize the total cost of all vehicle tours that serve all required edges under vehicle capacity constraints. In this study, a Hybrid Genetic Algorithm with Perturbation (HGAP) is proposed to solve the multi-depot CARP (MDCARP) which generalizes the CARP by extending the single-depot to the multi-depot. The proposed HGAP incorporates a Genetic Algorithm (GA), a local search, a new replacement method and a perturbation mechanism. The proposed HGAP is evaluated on the MDCARP benchmark instances and computational results show that the HGAP is very competitive.