A Genetic Algorithm for the Capacitated Arc Routing Problem

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.