Here, the most commonly used techniques for solving Vehicle Routing Problems are listed. Near all of them are heuristics and metaheuristics because no exact algorithm can be guaranteed to find optimal tours within reasonable computing time when the number of cities is large. This is due to the NP-Hardness of the problem. Next we can find a classification of the solution techniques we have considered:
Exact Approaches（精确求解）
As the name suggests, this approach proposes to compute every possible solution until one of the bests is reached.
-
Branch and bound（分支定界法）
-
Branch and cut（分支剪切法）
Heuristics（启发式）
启发式算法中文介绍：https://leovan.me/cn/2019/04/heuristic-algorithms/
Heuristic methods perform a relatively limited exploration of the search space and typically produce good quality solutions within modest computing times.
Constructive Methods（构造法）
Gradually build a feasible solution while keeping an eye on solution cost, but do not contain an improvement phase per se.
-
Multi-route Improvement Heuristics（多路径改进算法）
2-Phase Algorithm（两阶段算法）
The problem is decomposed into its two natural components: (1) clustering of vertices into feasible routes and (2) actual route construction, with possible feedback loops between the two stages.
Metaheuristics（元启发式）
-
Ant Algorithms（蚁群算法）
-
Constraint Programming（约束编程）
-
Deterministic Annealing（确定性退火）
-
Genetic Algorithms（遗传算法）
-
Simulated Annealing（模拟退火）
-
Tabu Search（禁忌搜索）