Improved Hybrid Ant Colony Algorithm And Its Application In Vehicle Routing

Ant colony algorithm is a swarm intelligence algorithm,which is used to simulate the foraging behavior of ants.Ant colony algorithm has the characteristics of self-organization and positive feedback,so it has highly adaptability.It is widely used in path planning,graph coloring problem,integrated circuit design,data clustering analysis and so on.However,ant colony algorithm also has the disadvantages of convergence slowly and easily falling into local optimum.Therefore,it is of great theoretical significance to study the improvement of ant colony algorithm.With the development of economic globalization and informatization,the logistics industry has rapidly become a new service industry with great potential and development space.The logistics industry is also the tenth industry in China's Ten Industrial Promotion Plan.Vehicle routing problem is a theoretical model of logistics distribution problem.Therefore,it is of great practical value to study the vehicle routing problem.The main work of this paper are as follows:1.This thesis discusses the basic principle and development process of ant colony algorithm,and describes in detail the ant system,elitist ant system,rank-based ant system and max-min ant system algorithm.The thesis discusses the effects of parameter settings on the performance of the algorithm,and the characteristics of ant colony algorithm.2.This thesis proposes an ant colony optimization algorithm for vehicle routing problem with time windows.This method improves the state transition probability and increases the influence factor of time window,and the pheromone evaporation rate is adjusted incrementally.At the same time,a method to construct the initial solution is proposed.The effectiveness of the algorithm is proved by the comparison with the best known solution.3.This thesis discusses the application of ant colony algorithm in the vehicle routing problem with simultaneous pick-up and delivery and time windows,and presents a hybrid ant colony optimization algorithm.This algorithm increases a candidate set to eliminate non-eligible customers in advance.Based on the ant colony optimization algorithm,the state transfer probability is improved,and the influence factor of the demand is added.This algorithm combines ant colony algorithm with frog leaping algorithm,firstly,the ant colonies are sorted and then grouped.Then evolve the ants selected in each group using the triangle probability distribution,the evolutionary step using local search algorithms,finally reorder and regroup,and then it cycles a certain number of times.Experiments show that the combination of these two swarm intelligence algorithms reduces the amount of computation while improving the quality of solution.4.This thesis discusses the dynamic vehicle routing problem and proposes the parallel ant colony optimization algorithm.This algorithm divides the process of solving dynamic problem into two stages.The first stage is to plan the initial path through the hybrid ant colony optimization algorithm.The second stage divides the workday into equal time periods,each time period checks whether there is a new customer and if so,replanning the path.Every time the planning is completed,the pheromones are retained and they will continue to participate in the next plan.Therefore,positive feedback is formed between the time periods,and the final solution is continuously improved.At the same time,the parallelism of the ant colony algorithm is used,parallel computation is introduced,and each ant constructs path in parallel.Experiments show that the parallel ant colony optimization algorithm not only improves the quality of the solution,but also reduces the computation time.