颜腾威，王丽侠，周 杰，王基一

(1.浙江师范大学数理与信息工程学院，浙江金华 321004; 2.浙江师范大学行知学院，浙江金华 321004)

求解CVRP问题的改进和声算法

颜腾威1，王丽侠2，周 杰1，王基一1

(1.浙江师范大学数理与信息工程学院，浙江金华 321004; 2.浙江师范大学行知学院，浙江金华 321004)

车辆路径问题是典型的NP难解问题，大多用启发式算法求解。和声搜索算法是一种新颖的启发式算法，最近几年得到了迅速发展，但是新提出的和声算法在求解车辆路径问题方面研究并不充分。针对现有的和声算法在求解车辆路径问题(CVRP)效率上的不足，提出了面向CVRP问题的改进的和声算法，对带有容量限制的CVRP，提出了一种改进的和声搜索算法。该算法采用自然数编码，在新和声的生成过程中，对和声音调的生成策略进行了改进，增加了和声约束，避免了不可行解的生成，并利用2-opt算子对新的和声进行了优化，从而压缩了搜索空间，提高了搜索效率。实验结果表明，算法的效率优于现有的CVRP求解算法。

车辆路径优化问题;容量约束的车辆路径问题;和声算法;组合优化

0 引言

车辆路径优化问题(Vehicle Routing Problem，VRP)是著名的组合优化问题，该问题的解决具有重要的理论和应用价值，广泛存在于交通运输、物流分发等领域。VRP问题可以描述为:一定数量的客户，各自有不同数量的物流需求，配送中心根据客户需求，规划车队行车路线，在满足一定约束的条件下，达到诸如路程最短、成本最低、耗费时间最少等目标。VRP问……