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

摘要

车辆路径问题是典型的NP难解问题,大多用启发式算法求解。和声搜索算法是一种新颖的启发式算法,最近几年得到了迅速发展,但是新提出的和声算法在求解车辆路径问题方面研究并不充分。针对现有的和声算法在求解车辆路径问题( CVRP)效率上的不足,提出了面向CVRP问题的改进的和声算法,对带有容量限制的CVRP,提出了一种改进的和声搜索算法。该算法采用自然数编码,在新和声的生成过程中,对和声音调的生成策略进行了改进,增加了和声约束,避免了不可行解的生成,并利用2-opt算子对新的和声进行了优化,从而压缩了搜索空间,提高了搜索效率。实验结果表明,算法的效率优于现有的CVRP求解算法。%Vehicle routing problem is a typical NP-hard problem,mostly solved by a heuristic algorithm. Harmony search algorithm,as a novel heuristic algorithm,has been developing rapidly in recent years. However,the research on vehicle routing problem by the harmony search algorithm is not sufficient. The existing harmony search algorithms for CVRP have some defects on efficiency. To address the prob-lem,an improved harmony search algorithm is proposed,which uses natural number coding. It adds constraints to new harmonies to avoid generating invalid solutions,and optimizes new harmonies by 2-opt algorithm,so that it can compress the search solution space and im-prove the efficiency. Compared with several improved GA,PSO,experiments show that the proposed algorithm outperforms the existing algorithms on efficiency.