Abstract: For solving the Capacitated Vehicle Routing Problem (CVRP),an Effective Hybrid Quantum Evolutionary Algorithm (EHQEA) was presented.The solution generation method based on two-dimensional Qubit Measurement Model (QMM) and visibility was designed to realize the global search guided by QMM,which was used to find the promising regions over the solution space.An interchange operation based on the distance similar degree between customers was constructed to improve the quality of the solution.The Interchange and Inverse operations based on the problem's property were proposed to construct a two-phase hybrid variable neighborhood local search,which was utilized to execute the fast and meticulous search in the promising regions and helped the algorithm to achieve a balance between the global and local search.Simulation results and comparisons on classic benchmarks with different scales demonstrated the effectiveness and robustness of the presented EHQEA.

Key words: quantum computing, capacitated vehicle routing problem, hybrid quantum evolutionary algorithm, qubit measurement model, two-phase hybrid variable neighborhood local search

摘要： 针对带容量约束的车辆路径优化问题,提出一种有效混合量子进化算法。设计了基于二维量子位观测模型和可见度的解生成方式,实现了由该模型引导的全局搜索,将其用于发现解空间中的优质解区域|构造了一种基于客户间距离相近度的交换操作来提高解的质量;提出基于问题性质的交换和逆转操作来构造两阶段混合变邻域局部搜索,可对优质解区域进行快速细致的搜索,使算法的全局和局部搜索能力得到平衡。通过不同规模经典测试问题上的仿真实验和算法比较,验证了所提算法的有效性和鲁棒性。

关键词: 量子计算, 车辆路径优化问题, 混合量子进化算法, 量子位观测模型, 两阶段混合变邻域局部搜索