Memetic Approach To Capacitated Arc Routing Problem

The Capacitated Arc Routing Problem (CARP) is a challenging combinatorial and constrained optimization problem with wide real world applications, such as salting route optimization or winter gritting, garbage collection, postal delivery, inspection of gas pipeline lines and electric power lines, etc. Since CARP is NP-hard, it is difficult for the exact methods to solve the problem in reasonable time, and the computational cost is extraordinary large. Therefore, this paper aims to apply meta-heuristic approach to solve CARP, and provide more efficient and applicable solutions.First, a novel extension memetic approach, named MAENS-C, is proposed to improve the state-of-the-art algorithm-Memetic Algorithm with Extended Neighbourhood Search (MAENS) for CARP, in which three techniques are introduced: applying tournament selection for parents by integrating fitness information, using an adaptive probability to optimize the frequency and depth of local search, and incorporating adaptive probability in stochastic ranking to balance the fitness and feasibility for ranking. C language is applied to simulate the algorithm, and the wide-used data set is used to test the algorithm, the result confirms the validity of the algorithm.Based on the parameters in the considered algorithms, statistical racing algorithm and non-parameter test methods are used to perform parameter optimization on all the 8 instances, which saves computational cost significantly, and ultimately get the optimal parameters combinations. All of the work has laid the foundation for the algorithm evaluation and application.After parameter optimization, experimental studies are performed on the considered algorithms with regard to the five metrics:average total cost, convergence reliability, the ability of global optimization, the robust stability, and the time complexity. This paper mainly compare and analysis the results from two aspects:under the circumstance of same time complexity and the same number of generations. Finally, it shows that the proposed algorithm can significantly improve the performance of MAENS. Furthermore,13 new best known solutions are found by our algorithm, which further verify the proposed algorithm can optimize the frequency and depth of the local search, and bring the outperformance of the algorithm.Lastly, the theoretical results of this study are applied to path planning instance of the Lancashire in the UK. Combining the requirements of the roads and geographic information, the algorithm proved the allocate solution to the vehicles and plan the route for the vehicles. Besides, the solution visualization are given, which help to provide efficient solutions for the route planning.