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

摘要：

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

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

所属期刊栏目：26

分类号：TP31(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61170108,61402418;教育部人文社科研究项目12YJCZH142;浙江省自然科学基金LQ13F020007

在线出版日期：2016-10-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：187-191