Solving Capacity Arc Routing Problems With Order Reduction And Directed Evolution

Capacitated Arc Routing Problem(CARP) is one of the classic combinatorial optimization problems and it is applied in a very wide range in our daily life, such as waste cleaning up, salting and snow removing in winter, school buses scheduling and mail delivery and so on. Therefore, researchers concentrate more on the practical problems. At present, scholars have put forward some algorithms to solve small-scale and medium-scale CARP effectively. With the continuous expansion of the information and networks in 21 st century, studying small-scale and medium-scale CARP can't meet our actual needs. So, researchers gradually pay attention to the study of the large-scale CARP. However, large-scale CARP has a higher complexity and it's difficult for the existing algorithms to get the global optima. Based on the situation, we consider the order reduction as the core idea to reduce the complexity of the problem, and immune clonal algorithm is a highly-evolved parallel algorithm. Therefore, we will use the order reduction and immune algorithm to slove large-scale CARP. The main works are as follows:1) Recently, Yi Mei proposed a cooperative co-evolution with route distance grouping(RDG-MAENS) for large-scale CARP and it has achieved good results. But RDG-MAENS is still insufficient in mutation mechanism when generating new individuals and update of the offspring. First, the RDG-MAENS algorithm adopts mutation operation with small probability 0.2 to change the search area and jumps out of the local optimal. While, for LSCARP, mutation with small probability is easy to make problems fall into local optimum. As a result, the improved algorithm called IRDG-MAENS makes full use of complete mutation to facilitate problems jump out of the local optimum. Next, RDG-MAENS starts to choose parents from the initial population and then gets new individuals by crossover and mutation of the selected parents, which can't guarantee the diversity of population, so it's also easy to fall into local optima. The improved algorithm(IRDG-MEANS) improves RDG-MAENS in above aspects and the experimental results show that IRDG-MAENS has better results than RDG-MAENS.2) We propose an immune clonal algorithm based on directed evolution(DE-ICA) for large-scale multi-objective CARP. Firstly, DE-ICA uses the framework of the immune clonal algorithm and enlarges the size of the initial population, increasing the diversity of the population and improving the quality of solutions. Secondly, DE-ICA combines the immune gene manipulation with the decomposition strategy. The decomposition strategy of population is conducive to share the information between the adjacent populations and converge to the ideal solutions fast. Finally, DE-ICA applies a novel comparison operation to select the best individuals according to a certain principle and the selected individuals are candidates to join the next evolutionary iteration. Experimental results show that the solutions got by DE-ICA on all instances in EGL-G can totally dominate the solutions obtained by the other algorithms.3) We propose a genetic algorithm based on order reduction and decomposition(RDGA) for large-scale multi-objective CARP. Firstly, RDGA algorithm adopts the order reduction algorithm as its framework. It decomposes large-scale problems into many relatively small-scale problems to reduce the size of the operation process. Secondly, RDGA applies decomposition strategy for every small-scale problem. RDGA decomposes the multi-objective small-scale problem into a series of single-objective problems, then it uses genetic algorithm for the single-objective problems to get solutions. Finally, in order to prevent the miss of the efficient solutions, RDGA adopts a more reserved strategy to save the individuals during the process of evolution. Experimental results show that RDGA has a strong competitiveness when solving large-scale multi-objective CARP.