1964, Clark and Wright[4] An effective heuristic algorithm for improving Dantzig-Ramse method Clark-Wright saving algorithm.
It is precisely because of the publication of the above two groundbreaking papers that VRP has become the frontier and hot spot in the field of operational research and combinatorial optimization.
In 1969, Christofides and Ai Long apply 2-opt[5] and 3-opt[6] to solve the vehicle routing problem.
In 1970, a two-stage method is proposed to solve the vehicle routing problem, including two heuristic strategies: cluster first-path second and path first-cluster second.
In 198 1, Fisher and Jaikumar put forward an optimization method based on mathematical programming to deal with the problem involving about 50 customer points, and its operation efficiency is also an urgent problem. In the same year, Gulen, Jarvis and Ratliff established a heuristic method of human-computer interaction.
In 198 1 year, Bodin and Golden summarized many VRP solutions. It can be divided into the following seven categories: exact procedures; Interactive optimization); Methods; Cluster first-route second; Route first-cluster second; Save or insert; Improve or communicate; Mathematical programming (mathematical programming).
Since 1990, artificial intelligence methods have shown powerful functions in solving combinatorial optimization problems and have been fully applied in various fields. Many scholars have also introduced artificial intelligence to solve the vehicle routing problem and constructed a large number of heuristic algorithms based on artificial intelligence. Tabu search (TS) is basically a local search method of artificial intelligence (AI). Willard first used this algorithm to solve VRP. Yuan Qingda [7] and others designed a tabu algorithm considering time window and different car types. The algorithm mainly uses genetic algorithm to generate the initial solution, and then uses tabu algorithm to optimize the initial solution. Simulated annealing method has the characteristics of fast convergence and global search. Osman[8] studied the simulated annealing algorithm of VRP. Genetic algorithm has good characteristics in solving combinatorial optimization problems. Holland first used genetic algorithm (GA) to solve the VRPTW problem. At present, most scholars adopt mixed strategy and two artificial intelligence methods for route grouping and route optimization. Ombuki[9] proposed a hybrid algorithm of route grouping with GA and route optimization with TS. Bent and Van Hentenryck[ 10] firstly use simulated annealing algorithm to minimize the number of vehicle routes, and then use largneighborhood search to minimize the transportation cost.
Based on the previous methods to solve VRP, it can be divided into exact algorithm and heuristic algorithm, in which the exact algorithm includes branch and bound method, branch cutting method, set covering method and so on. Heuristic algorithms include saving method, simulated annealing method, deterministic annealing method, tabu search method, genetic algorithm, neural network, ant colony algorithm and so on.