计算机工程与应用 ›› 2019, Vol. 55 ›› Issue (9): 230-236.DOI: 10.3778/j.issn.1002-8331.1801-0054

• 工程与应用 • 上一篇    下一篇

变邻域量子烟花算法求解CVRP

蔡延光,陈厚仁,戚远航   

  1. 广东工业大学 自动化学院,广州 510006
  • 出版日期:2019-05-01 发布日期:2019-04-28

Variable Neighborhood Quantum Fireworks Algorithm for Solving CVRP

CAI Yanguang, CHEN Houren, QI Yuanhang   

  1. School of Automation, Guangdong University of Technology, Guangzhou 510006, China
  • Online:2019-05-01 Published:2019-04-28

摘要: 针对带容量约束的车辆路径问题,提出一种融合量子进化算法和变邻域优化策略的变邻域量子烟花算法。该算法采用等分随机键与最大位置法结合的实数编码方式,通过量子旋转门和非门变异提高算法全局搜索能力,同时运用结合2-Opt的变邻域优化策略加强局部搜索能力。选取17个基准算例进行参数实验和对比实验,实验结果表明,相对于对比算法,所提出的算法具有较好的寻优能力和收敛速度。

关键词: 烟花算法, 量子进化算法, 变邻域搜索, 容量约束车辆路径问题(CVRP), 最大位置法

Abstract: For the capacitated vehicle routing problem, this paper proposes a variable neighborhood quantum firework algorithm which integrates the quantum evolutionary algorithm and variable neighborhood optimization strategy. The proposed algorithm adopts a real number encoding method which combines uniform random keys and largest order value strategy. In addition, the proposed algorithm applies the quantum revolving door and gate mutation to improve the global search ability. Moreover, the proposed algorithm uses the variable neighborhood optimization strategy with 2-Opt to enhance the local search performance. 17 benchmark instances are applied to the parameter experiment and the comparison experiment. The experimental results show that, compared with the alternative algorithms, the proposed algorithm has a better optimal ability and a convergence speed.

Key words: fireworks algorithm, quantum evolutionary algorithm, variable neighborhood search, Capacitated Vehicle Routing Porblem(CVRP), largest order value