An improved genetic algorithm for the extended Capacitated Arc Routing Problem

The capacitated arc routing problem (CARP) arises in applications like waste collection or winter gritting. Exact algorithms are still limited to small problems and metaheuristics are required for large scale instances. The paper presents an improved genetic algorithm (GA) for solving an extended version of the CARP (ECARP) like prohibited turns or slop problem. This new algorithm improves the population structure and chromosome organization mode of the traditional genetic algorithm (TGA), and devises several simple and high-effective evolutionary operators, avoiding the premature convergence phenomenon in the TGA. According to our experiment analysis, the improved GA proposed in our paper can solve the ECARP effectively, meanwhile, the comparison experiment between the improved GA and classical MA (memetic algorithms) for the basic CARP shows that our new algorithm is more effective and can get the better results than MA when solving the large-scale basic CARP.