Search

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.

In this paper, the Genetic Algorithm(GA) is used to resolve the Capacitated Arc Routing Problem(CARP), the case of which stems from assigning the routing of sprinkler cars in real life. And the paper presents basic components of GA combined with the crossover, mutation and loach search operation. These new methods are helpful for the global search of CARP problem. The test data is coming from real world, offered by the Sanitation Department-the owner of the sprinkler cars. Furthermore, the contrastive experiment which has been done in this paper illustrates that this GA method is more excellent than other existing algorithms in resolving this kind of CARP. As for the pratical meaning of this research, the routing plan proposed may provide high efficiency for the department and will bring about significant economic benefits.

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.