Research On Improved Artificial Bee Colony Algorithm Based On Vehicle Routing Problems With Time Windows

Vehicle Routing Problems(VRP) is a combination optimization problem derived from the addition of time window constraints based on the Basic Routing Problems(VRP).Since VRPTW has been proved to be an NP-hard problem,how to effectively solve VRPTW is also a research difficulty.The Artificial Bee Colony Algorithm(ABC algorithm) is an emerging group intelligent algorithm that mimics the behavior of bees collecting honey and foraging,It has a very good effect in solving NP-hard problems.This thesis focuses on the two targets of vehicle number and vehicle travel distance based on VRPTW to improve and research the artificial bee colony algorithm.The main work is as follows:This thesis first discusses the theoretical basis of the ABC algorithm,and discretizes the standard ABC algorithm according to the characteristics of VRPTW.This thesis designs a new data structure,using a single-linked list in two directions,using two-dimensional coding to represent each solution,and redefining the code update formula for the bee colony in the neighborhood transformation of the food source.A method for establishing an initial population and generating a detection bee is given.Because the standard discrete ABC algorithm has poor accuracy,this thesis improves the standard discrete ABC algorithm and proposes an improved discrete ABC algorithm.Combined with the structure of two-dimensional coding,the algorithm uses two search directions between paths and paths in the neighborhood search,and proposes an optimal insertion strategy to improve the success rate of the insertion operation.In the scouting stage,this thesis introduces the limit variable,designs a new elimination mechanism,and increases the number of iterations to generate new solutions to improve the competitiveness of the new solution.This thesis sets up a bulletin board to record the global optimal solution by updating the bulletin board to prevent the optimal solution from being abandoned during the iteration process.By comparing with the standard discrete ABC algorithm,other heuristic algorithms,and the optimal solution in the database,the improved discrete ABC algorithm maintains high accuracy when the optimal number of vehicles can be found.In order to further explore the improved population convergence ability of discrete ABC algorithm,this thesis studies the population diversity of the algorithm in solving VRPTW from the aspects of variance and entropy.The experimental data prove that the improved discrete ABC algorithm has a wide population distribution and a strong spatial search ability throughout the iterative process,and maintains a relatively high population diversity.