求解CVRP的改进量子遗传算法研究

Study of Modified Quantum Genetic Algorithm for CVRP

车辆路径问题属于离散NP-hard组合优化问题,传统的量子遗传算法存在储存量大和易陷入局部最优解等问题。提出一种新的量子遗传算法用于最小化运输成本。设计一种将量子比特编码转换为实数的编码方法,每条染色体代表一种行车路线方案,利用改进的旋转门对种群进行更新操作,采用动态调整旋转角机制对量子步长实现自适应搜索,扩大全局搜索范围;引入一种变异操作,用于保持算法的种群多样性,从而提高算法的全局搜索宽度;采用客户节点重置和2-opt法对线路进行再优化,增强算法的局部搜索能力。仿真实验和算法比较,验证了该算法的优越性和有效性。

The vehicle routing problem is the NP-Hard combinatorial optimization discrete problem,The traditional quantum genetic algorithm has many problems such as large storage capacity and easy to fall into local optimal solution,so in this paper,a new quantum genetic algorithm is proposed to minimize transportation cost.This paper designs a coding method to transform the common coding into quantum bits,each chromosome represents a routing scheme,the update operation by using the improved rotating door population,adaptive search of quantum step size by dynamic adjustment of rotation angle mechanism,improve global search local.A mutation operation is introduced to maintain the population diversity of the algorithm,so as to improve the global search width of the algorithm.Finally,the customer node reset and the 2-opt method are used to optimize the circuit to enhance the local search capability of the algorithm.The advantages and effectiveness of the algorithm are verified by experimental simulation and algorithm comparison.