Research On The Large Scale Capacitated Arc Routing Problem Based On Divide And Conquer Strategy

The capacitated arc routing problem(CARP)is a classic combinatorial optimization problem,which has a wide range of applications,such as urban garbage cleaning,winter road salt spraying planning,etc.Regarding the solution of this problem,relevant scholars have currently proposed some algorithms to effectively solve it.However,in the current social production,research on small scale CARP problems is no longer able to keep up with the needs of practical applications.The optimization of large scale capacitated arc routing problem(LSCARP)has increasingly highlighted its importance.However,as the scale increases,the difficulty of solving CARP problems will further increase,making it difficult for small scale CARP solving methods to solve such problems.Therefore,this article mainly studies the structural characteristics of the LSCARP problem itself,and adopts a divide and conquer strategy to solve and optimize the LSCARP problem.The main work of this article is as follows:(1)An improved route cutting off composition operator(IRCO)is proposed to solve LSCARP.In response to the incomplete decomposition results obtained by the current algorithm using the divide and conquer strategy to solve LSCARP,IRCO can identify the difference shaped paths in the path set and segment them accordingly.By recombining the segmented paths,better decomposition can be achieved,which is beneficial for the algorithm to jump out of local optima and achieve better results.IRCO also introduced the concepts of long and short paths,and defined high cost and small total distance paths as differential paths based on their morphology.Based on this,IRCO can perform heuristic optimization on the target path.In experiments,this paper validated IRCO using EGL-G,Hefei,and Beijing test sets,and the results showed its effectiveness.(2)An adaptive dataset detection operator(ADDO)is proposed to address the impact of the structure of LSCARP on algorithm performance and optimize the stability of its divide and conquer strategy.This operator can detect the structure of the CARP test set and allocate key parameters based on the relationship between task edges and non task edges to improve decomposition quality.ADDO defines the concept of task sparsity based on the density of edges that need to be served in CARP application scenarios.Based on SAHID,it adaptively controls the rate of virtual path merging and the probability of path basic segmentation,supplementing its shortcomings in different scale and structure application scenarios.Finally,the experimental results verified the effectiveness of ADDO in improving SAHi D performance.(3)An improved Path Construction Rules(IPCR)based on the algorithm Merge Split is proposed.In the local search stage of solving LSCARP based on the divide and conquer strategy,the shortcomings of insufficient consideration of CARP domain information by the rules during path insertion were supplemented in Merge Split.The rules of the Merge Split algorithm during path insertion were improved,which fully combined CARP domain information and reduced unnecessary costs incurred by vehicles returning to warehouse points.This can increase the efficiency of local search and avoid some ineffective searches.Finally,the improved path construction rules were applied to the SAHi D algorithm,and sufficient comparative experiments were conducted with current mainstream algorithms in the EGL-G,Hefei,and Beijing test sets.The experimental results show that IPCR has good performance and can effectively improve the efficiency of the algorithm.