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

曹云+向凤红+毛剑琳

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

关键词：车辆路径问题；量子遗传算法；量子旋转门；量子变异

DOIDOI：10.11907/rjdk.171907

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2017）012-0060-04

Abstract：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.

Key Words：vehicle routing problem； quantum genetic algorithm； quantum rotating gate； quantum mutation

0 引言

車辆路径问题（Vehicle Routing Problem， VRP）是典型的NP-hard问题，由Dantzing和Ramser [1]于1959年提出，广泛应用于物流配送、交通线路规划和快递收发系统。传统精确算法仅适用于小规模问题，而启发式算法难以获得精确解，因此，智能算法受到人们青睐。赵燕伟等[2]提出了一种双种群遗传算法用来求解CVRP，根据两个种群各自特点进行不同进化，同时交换种群间的优质个体信息，使算法避免陷入局部最优；Wang等[3]提出了一种混合遗传算法来求解CVRP，利用响应面法对变异、交叉概率进行优化操作，同时将改进的扫描法插入到遗传算法以增加种群的多样性，使算法的搜索能力得以提高；Dorronsoro等[4]提出了一种元胞遗传混合算法，全局搜索用遗传算法，局部捜索采用交换操作结合2-opt法提高算法搜索性能；蔡蓓蓓等[5]提出一种混合量子遗传算法求解CVRP，在传统的量子遗传算法基础上加入免疫算子，算法的局部捜索能力明显改善；WANG等[6]提出一种元胞蚁群算法，实验证明该算法具有较好的捜索能力。

量子遗传算法（QGA）是由A Narayannan和Kuk-Hylun Han[7]等首先提出的，是一种受到量子计算启发，并成功借鉴量子计算中的部分概念和理论形成的概率遗传算法。它的优点是丰富的种群多样性以及全局寻优能力，为求解车辆调度问题提供了新的思路。QGA的染色体用量子位表示，通过量子门更新完成进化搜索。

作为VRP最基本的约束模型，CVRP在求解方面效果不是很理想。本文将量子和遗传算法结合，针对问题本身特点对算法作了进一步改进。采用客户与虚拟配送中心共同排列的编码方式表示客户位置，并利用改进的旋转门对种群进行更新操作，采用动态的调整旋转角机制对量子步长实现自适应搜索，引入量子变异从而防止算法的早熟问题。仿真结果表明，改进的QEA算法比文献[8]中的混合遗传算法寻优能力更强。

1 CVRP及数学模型

1.1 带容量的车辆路径问题描述

带容量约束的车辆路径问题描述为：有一个车场，共有K辆车，每辆车的最大载重为Q，这些车辆为L个客户服务，客户i的需求为qi，每个客户可由任一辆车进行服务，但只能被一辆车服务一次，每辆车服务完后必须返回原车场。其目标是找到一个合适的车辆调度方案，在满足客户需求的同时使车辆的运输成本最低。

1.2 带容量的车辆路径问题模型

2.2.5 客户节点重置和2-opt法

为增强算法的局部开发能力，改进的QGA引入客户点重置结合2-opt法局部搜索。

客户节点重置是将一个客户节点从一条线路移到另一条线路。如图2所示，节点i距离节点j是最短的，则将节点i重置到一个线路，与j相邻。重置时需考虑以下情况：i重置到线路r1，i在j之前或之后；j重置到线路ri，i在j之前或之后。选择满足车辆的容量限制且路程最短的一种重置。

2-opt法是针对一条线路的两个客户进行交换，如图3所示。将（i，j），（i+1，j+1）替换原来的（i，i+1），（j，j+1）。若交換后的路线长度变短则采用此算法，并将采用此算法形成的新路线作为最优解，否则将原来的解定位为最优解。

3 算法性能测试

在CPU为E5800 3.20GHz，内存为2.96GB，操作系统为Windows 10的计算机上，采用文献[8]中的算例与之对比，对算法进行验证。配送中心共有5辆货车，货车的最大载重量均为8t，最大行驶距离均为50km，要求向20个客户送货，车场（即配送中心）坐标为（14.5km，13.0km），客户的位置坐标和需求量如表1所示。

本文将改进的量子遗传算法（KQGA）与GA算法和HGA算法进行比较，所得结果如表2所示。从表2可以看出，对于同样的数据，3种算法在同样运行10次时改进量子遗传算法要优于其它两种算法。图4为3种算法的适应度曲线。因为目标函数是求运输成本，所以适应度越小越好。从图中可以看出，本文提出的算法适应度最小。

4 结语

本文针对传统的量子遗传算法存储量大且易陷入局部最优等问题，提出了一种改进的量子遗传算法。采用动态调整旋转角机制对量子步长实现自适应搜索，从而加快了算法收敛速度，提高了搜索深度。引入量子自适应变异操作防止了早熟问题。局部搜索采用客户节点重置和2-opt法结合对线路进行优化，使解的质量明显提高。通过与传统的GA和HGA对比，证明了该算法具有较强的寻优能力。目前，KQGA只是针对静态的带容量车辆调度问题进行研究，今后将对动态车辆调度进行研究，并验证其有效性。

参考文献：

[1] DANTZIGC RAMSERJ.The truck dispatching problem[J].Management，Science，1959（6）：80-91.

[2] 赵燕伟，吴斌，蒋丽，等.车辆路径问题的双种群遗传算法求解方法[J].计算机集成制造，2004，10（3）：303-306.

[3] WANG C H， LU J Z. A hybrid genetic algorithm that optimizes capacitated vehicle routing problems[J].Expert Systems with Applications，2009，36（2）：2921-2936.

[4] DORRONSORO B，ARIAS D，LUNA F.A grid-based hybrid cellular genetic algorithm for very largr scale instances of the CVRP[C].High Performance Computing & Simulation Conference，2007：759-765.

[5] 蔡蓓蓓，张兴华.混合量子遗传算法及其在VRP中的应用[J].计算化仿真，2010，27（7）：267-270.

[6] WANG Y.Solving the capacitated vehicle routing problem by cellular ant algortithm[EB/OL].http：//comnection.ebscohost.com/c/articles/74249351.

[7] HARYNANAN A，MOORE M.Quantum-inspired genetic algorithms[C].Proceeding of IEEE International ConferenceonEvolutionary Computation，Nagoya，Japan，1996：61-66.

[8] 郎茂祥，胡思继.用混合遗传算法求解物流配送路径优化问题的研究[J].中国管理科学，2002，10（5）：51-56.

（责任编辑：杜能钢）