Memetic Algorithm With Backtracking And Decomposition Strategy For Capacited Arc Routing Problems

Capacitated Arc Routing Problem(CARP)is a classic NP hard problem in combinatorial optimization.Due to its wide applications,it has received more and more attention from many researchers in recent years.In our daily life,collection of the trash,transport route planning,energy line inspection,replacement of oil path,all of these are to find the path with minimum total consumption under capacity constraint and belong to CARP.In recent years,many research methods have been proposed to solve this combinatorial optimization problem.But with the advent of the era of big data,the scale of the problem becomes large,many algorithms aimed at small and medium-sized are no longer fit.As a result,the strategy of problem decomposition was adopted in this paper.After that,the large scale problem is decomposed into many small scale problems,the multi-objective problem is decomposed into a series of single objective problem.In addition,the existing algorithms have higher requirements on the initial solution,which affects the stability of the algorithm.Ant colony algorithm has strong robustness,the low requirement on initial solution and strong global search ability,making it more suitable for the graph search optimization problem.Besides,the loop adjustment operator,extended search operator and elite reserve strategy are also designed to improve the search ability.The main work of this paper is as follows:(1)For single CARP,some scholars proposed a cooperative co-evolution with route distance grouping(RDG-MAENS)and it has been proved to be competitive.However,the algorithm is not reasonable in the problem decomposition,which makes the search resources distributed unevenly,and is easy to fall into the local optimal solution.At the same time,in the process of solving sub problem,RDG-MAENS uses random selection operator to select individuals in a population as a parent to produce new offspring,while maintaining diversity of solution to a certain extent,but the convergence speed is very slow.For this reason,a Decomposition Strategy Based On Route Distance Grouping and Backtracking for LSCARP(RBD-MAENS)was introduced,and the experimental results show that compared with RDG-MANES,the RBD-MAENS algorithm is competitive.(2)Due to the high requirement of the initial solution of RDG-MAENS,the stability of the algorithm is not good enough and the poor ability in searching optimal solution,a Decomposition Strategy Based on Rank Ant Colony Algorithm for LSCARP(RDAC)was proposed.In this paper,a ranked ant colony algorithm was used to solve CARP to produce initial solutions with high quality.In addition,the way of updating the pheromone is improved,so it can produce high quality solutions,reduce the dependence of RDAC on the initial solution,and enhance the stability of the algorithm.Secondly,the decomposition strategy was introduced,the problem is decomposed into several smaller sub problems and achieve pheromone communication between sub problem,thereby achieving more effective search in huge space,improving the search efficiency of the algorithm and make it suitable for solving LSCARP.Finally,a loop adjustment operator was used to the local search to further improve the quality of the solution,so as to improve the searching ability of the algorithm.(3)For large-scale Multi-objective CARP(MO-CARP),this paper put forward to a Memetic Algorithm Based on Decomposition and Extended Search(ED-MAENS).Firstly,the multi-objective problem is decomposed into several single objective problems by weighted vector.Then,the representative solution for each single objective subproblem is assigned.In order to ensure that each sub problem can be assigned a more appropriate representative solution,this paper introduces the concept of hierarchy,and rank all candidate solutions according to the two objective function values.After that,for each sub problem,the MAENS algorithm is used for further search combined with the information of its neighborhood subproblem.Finally,an extended search operator was designed to expand the search for the solution space to improve the quality of the solution.Experiments show that,compared with the contrast algorithm,ED-MAENS is very suitable for solving MO-CARP.