蒋海青，赵燕伟，冷龙龙

(1.浙江工业大学 特种装备制造与先进加工技术教育部重点实验室，浙江 杭州 310014; 2.中国计量大学 现代科技学院，浙江 杭州 310014)

0 引言

半个多世纪的研究使车辆路径问题(Vehicle Routing Problem, VRP)从问题描述到求解方法都取得了丰硕的成果，但如何获得满意的求解方法依然是VRP中具有挑战性的研究领域[1]。VRP的求解方法大体分为精确式、启发式和智能优化3种，精确求解方法如动态规划、分支定界等[2]，启发式算法如节约法[3]、扫描法[4]及文献[5-6]对这两种算法的改进。由于启发式算法一般求到的是局部最优解，VRP目前的求解方法主要以智能优化算法为主，如遗传算法(Genetic Algorithm, GA)[7-8]、禁忌搜索(Tabu Search, TS)算法[9-10]、模拟退火(Simulated Annealing, SA)算法[11-13]、蚁群优化(Ant Colony Optimization, ACO)算法[14-17]。

石兆[18]总结智能优化算法在VRP的应用认为，禁忌TS算法搜索时间短，但禁忌规则难以确定;SA算法在不考虑计算时间时求得的解最好;ACO算法的搜索速度较慢，且较易出现早熟问题。鉴于智能优化算法的不足，近年来人们尝试从以下两方面进行算法改进：

(1)将多种算法进行集成 如Boon等[19]提出的集成差分算法，通过扩展TS算法求解车辆路径问题；Teymourian等[20]将改进智能水流算法(Enhanced Intelligent Water Drops, EIWD)和布谷鸟搜索(Cuckoo Search, CS)算法结合，并应用局部搜索混合算法(Local Search Hybrid Algorithm, LSHA)和后优化混合算法(Post-Optimization Hybrid Algorithm, POHA)局部搜索解决带有容量约束的车辆路径问题(Capacity Vehicle Routing Problem, CVRP)；Akpinar[21]将大规模邻域搜索(Large Neighbourhood Search, LNS)与蚁群算法ACO结合组成LNS-ACO算法求解CVRP问题，该算法应用ACO构造新的解，应用LNS进行解的改进，结合基于插入的局部优化方法在大量CVRP案例中获得了满意的结果；张景玲等[22]将量子进化算法与免疫算法结合，提出自适应免疫量子进化算法求取动态VRP；……