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

来源：计算机技术与发展杂志2016年第09期北京时间：

作者：颜腾威;王丽侠;周杰;王基一

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

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