Research On Improved Ant Colony Optimization Algorithm Based On Spark For Vehicle Routing Problem With Time Windows

As a sought-after combinatorial optimization and integer programming problem in many research directions,vehicle routing problem has in-depth and extensive application and practice in graph theory,operations research,applied mathematics,computer application in recent decades.In nearly a decade,with the explosive growth of electronic commerce in our country,the applications of VRP problem in logistics,express transport and its economic value make it importance in the field of scientific research.Vehicle routing problem with time windows constraint is a branch of VRP problem,has higher application value,but the related research is less.With the development of big data and cloud computing,Spark and Hadoop as famous big data parallel computing framework have achieved good results in industry,but there is few attempt in the field of scientific research.In this paper,the main work includes:first of all,three areas of VRPTW problem,ant colony algorithm,ant colony algorithm to solve VRPTW problem are reviewed respectively.Secondly,an improved optimization strategy for the ant colony algorithm is put forward,the improved algorithm combines the ideas of the"Ant-Cycle Model" and the Max-Min Ant System,pheromone is updated by using global information,the pheromone concentration is controlled within a certain range that makes the algorithm avoid getting stuck prematurely into local optimum;time window span,waiting time and saved values are introduced into the transition rules of ant as impact factors;two pheromone evaporation strategy is proposed;a dynamic adjustment strategy of pheromone's volatilization rate is added;finally local search optimization strategy is added to improve the quality of the solution significantly.The experiments of classical VRP data show that the improved algorithm is effective.Thirdly,the standalone version,Spark version and Hadoop version are compared and analyzed in the experiment and the convergence and extensibility of the Spark version is verified.In this paper,the improved ant colony algorithm to solve the vehicle routing problem with time window constraints has certain feasibility and the distributed implementation greatly reduces the time of the algorithm,and has certain practical value.