Research On Improved Ant Colony Optimization Algorithm Based On Spark For Capacity Vehicle Routing Problem

The Capacitated Vehicle Routing Problem(CVRP)is a well-known combinatorial optimization problem.In reality,many problems such as robot path planning,logistics and distribution,urban waste disposal,etc.can be abstracted as CVRP problems.There are many ways to solve the CVRP problem,including exact algorithms,such as branch bounding and branch cutting;metaheuristic algorithms,such as ant colony algorithm,simulated annealing algorithm,genetic algorithm,etc.;reinforcement learning methods,etc.However,most of these methods have problems of long solution time and low accuracy.Since its introduction,the ant colony algorithm has been effectively applied in many fields.Due to the natural parallelism of ant colony algorithm,it can be effectively combined with Spark,a computing framework for big data computing,to effectively reduce the running time while ensuring the accuracy of the algorithm.To address the CVRP problem,this thesis designs an improved adaptive ant colony algorithm AMACO and proposes three improvement strategies: 1.Improve the transfer probability so that the pheromone accumulation and heuristic factor weight ratio change continuously as the number of iterations increases to achieve adaptive changes and mitigate the drawbacks of fixed parameters.2.Improve the pheromone strength so that it changes dynamically with the number of iterations so that it can jump out of the local optimum.3.add a local search strategy using the 2-opt operator,which will,optimize the path generated by each vehicle to speed up the convergence and improve the accuracy.In order to improve the algorithm execution speed and better compute large-scale arithmetic cases,the Sparkbased distributed parallel computing method is used to design the ant colony algorithm SPAMACO based on Spark framework.This method encapsulates the ants into Resilient Distributed Datasets(RDD)for distributed computing.Through numerical experiments of different scales,2 aspects of solution accuracy and running time are tested,and the experimental results show that the solution accuracy and algorithm execution time of the algorithm are effectively improved.Finally,the planning system of vehicle path is designed to give realistic application scenarios for the CVRP problem and to provide help for existing path planning methods.