A Hybrid Genetic Algorithm for the Multiple Depot Capacitated Arc Routing Problem

This paper presents a new hybrid genetic algorithm (HGA) for the multiple depot capacitated arc routing problem (MDCARP) with homogeneous vehicles. This algorithm improves the traditional-genetic algorithm (TGA) on the basis of the partheno-genetic algorithm (PGA), which can avoid the premature convergence effectively and overcome the inefficient problem of existing heuristic algorithms. The background of our study is assigning the routes of sprinklers, so computational experiments are done with the real-life data provided by the Sanitation Department of Chongqing city in china, and the computational results reveal that the proposed HGA can solve MDCARP effectively. Furthermore, two comparison experiments for the single depot capacitated arc routing problem (1-CARP) show that this algorithm can also solve the 1-CARP with better result and much higher efficiency than the best metaheuristic published.