Hybrid ant colony algorithm for VRP problem and implementation system thereof

Abstract

The invention discloses a hybrid ant colony algorithm for a VRP problem and an implementation system thereof. The algorithm comprises the steps of (S1) allowing all ants in an ant colony to independently construct a solution of the VRP problem and optimizing the solution by using a local search operation, (S2) performing a pheromone perturbation strategy to adjust a pheromone matrix if an iterative optimal solution remains unchanged in successive iterations, wherein the iterative optimal solution is an optimal solution in solutions constructed by all ants in a single time of iteration, (S3) starting a simulated annealing algorithm to search for a better solution if the optimal solution remains unchanged in the successive iterations so far and taking an optimal solution so far of the ant colony algorithm as an initial solution, (S4) updating the pheromone matrix according to the quality of an ant solution and updating the optimal solution so far, (S5) repeating the steps (S1), (S2), (S3) and (S4) until an obtained optimal solution satisfies a termination condition. According to the hybrid ant colony algorithm for a VRP problem and the implementation system thereof, the purposes of high-quality solution and strong robustness for the VRP problem can be achieved.

Description

technical field [0001] The invention relates to the technical field of VRP (Vehicle Routing Problem, vehicle routing problem) of logistics, in particular to a mixed ant colony algorithm for the VRP problem and an implementation system thereof. Background technique [0002] With the development of the Internet economy and trade, the scale of the logistics industry is increasing day by day, and the impact of logistics distribution on economic activities is becoming more and more significant. VRP (Vehicle Routing Problem, Vehicle Routing Problem) is a key issue in distribution optimization. Optimizing distribution vehicle routes can effectively reduce distribution costs, reduce delivery time, and improve user satisfaction. Therefore, it is of great practical significance to study this problem. [0003] The VRP problem is a kind of NP (Non-deterministic Polynomial, non-deterministic problem with polynomial complexity) complete problem. It is difficult to solve it in a reasonabl...

AI Technical Summary

Problems solved by technology

Ant colony algorithm is a heuristic algorithm proposed by simulating the foraging behavior of ant colonies in nature. This algorithm has better performance in solving combinatorial optimization problems such as VRP problems. However, the swarm algorithm has defects such as easy to fall into local optimum.

[0004] At present, most of the optimization methods for the ant colony algorithm focus on the pheromone update process. These optimization methods generally still use a single ant colony algorithm, and the optimization space is very limited.

Images