Research On Closed Multi-depot Capacitated Arc Routing Problem Based On Memetic Algorithm

As a kind of arc routing problem,Capacitated Arc Routing Problem adds a capacity constraint to the service vehicle so as to make the problem closer to the actual situation.Closed Multi-depot Capacitated Arc Routing Problem is widely used in real life,such as winter salting work route planning and garbage truck operation route planning.The promotion of the research results of the problem issues in multiple areas can effectively improve social efficiency and reduce energy consumption.Therefore the study of the problem has a certain value.In this paper,we will construct the model of the Closed Multi-depot Capacitated Arc Routing Problem,and make research of using the Memetic algorithm to solve the problem.Then the validity of the improved algorithm is attempted to be proved by the solution of the example.The contents of this article are made up of following sections:At firstly,introduction.In this part we briefly describe the research background,research status at home and abroad,and the structure of the paper.Secondly,the origin,definition,complexity of Capacitated Arc Routing Problem,the classifications of Closed Multi-depot Capacitated Arc Routing Problem and the processing of complex constraints in the problem are introduced.Then we modeled Capacitated Arc Routing Problem,closed Multi-depot Capacitated Arc Routing Problem.The meanings of various symbols and formulas in the problems are introduced.Thirdly,we briefly introduce the Genetic Algorithm(GA)and the Memetic Algorithm(MA),and the key steps in the algorithms are discussed.Based on the traditional Memetic algorithm,we introduce the algorithm we use in this paper.The algorithm adopts integer coding,uses the Extended Random Ulusoy's Heuristic method for initialization,the tournament method to perform the selection operation,the Linear Order Crossover to perform the crossover operation.The traditional genetic operator is adopted.The operators obtained after the compound operation are used to perform the mutation operation.Then,firstly we describe the method of converting the Closed Multi-depot Capacitated Arc Routing Problem into multiple standard problems.Then the improved algorithm is used to solve the example and we can draw a conclusion.At last,we summarize the previously completed content,explain its significance and deficiencies and look forward to future research.