带油耗率的车辆路径问题的改进量子遗传算法研究

汪婷 汤雅连

(1．广东技术师范学院 天河学院 ，广州 510540;2．广东工业大学 自动化学院，广州 510006)

车辆路径问题 (Vehicle Routing Problem，VRP)［1－2］自1959年Dantzig和Ramser首先提出以来就引起了人们的高度重视，它属于经典的组合优化问题。VRP的实用性强，且应用广泛。车辆路径问题一般定义为:对一系列送货点和收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件 (如货物需求量、发送量、送发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定的目标 (如路程最短、费用极小、时间尽量少、使用车辆数尽量少等)。

量子进化算法 (Quantum Evolutionary Algorithm，QEA)是20世纪90年代后期新兴的一种进化算法。由于其良好的性能，已广泛应用于诸多领域，如物流运输调度、智能交通领域、网格入侵检测、网格任务调度、非线性规划等［3－4］。Mohammed A.M.等人［3］提出了基于量子遗传的量子交叉算法 (Quantum Crossover－based Quantum Genetic Algorithm，QXQGA)对非线性规划问题求解;蔡延光等人［4］针对量子进化算法计算量大、收敛速度慢以及容易出现早熟等问题，提出混沌混合量子进化算法，并证明其可较好地应用在智能交通领域。研究车辆路径优化问题 (Vehicle Routing Problem，VRP)是研究IVRP的基础。目前，国内外采用QEA及其改进算法对VRP或其扩展问题的研究文献不少，有一定的借鉴意义。Cui L.等人［5］提出了一种带混合局部搜索的改进量子进化算法 (Improved Quantum Evolution Algorithm，IQEA)对带容量约束的VRP(Capacitated Vehicle Routing Problem，CVRP)求解;Wang L.等人［6］提出了一种改进量子进化算法 (Quantum－Inspired Evolutionary Algorithm，IQEA)对带时间窗的VRP(Vehicle Routing Problem with Time Windows，VRPTW)求解;葛显龙等人［7］根据随机需求信息把动态配送问题转换成一系列静态配送问题，设计基于并行节约算法动态插入随机需求信息的混合量子遗传算法，对动态模型实时再优化;之后，葛显龙等人［8］又采用量子比特位设计染色体结构，改进遗传算法中交叉与变异算子，避免优秀基因被破坏，设计快速寻优机制与最优保留机制，增强求解效率对以配送总费用最小为优化目标的数学模型求解;Zhang J.等人［9］提出了一种自适应网格多目标量子进化算法 (Multi－objective Quantum Evolutionary Agorithm，MOQEA)对带客户满意度的多目标VRP(Multiobjective Vehicle Routing Problem Considering Customer Satisfaction，MVRPCS)求解;Michallet J. 等人［10］研究了非常严格的带时间窗的周期性VRP，并提出了混合整数线性模型和多起点迭代局部搜索算法;Crispin A.等人［11］提出了一种量子模拟算法对带容量约束的VRP求解;Zheng T.等人［12］提出了量子差分进化算法对调度问题求解;Zhou L.等人［13］针对传统的遗传算法不能保证收敛到最优解的最大概率，提出了对小规模求解具有快速收敛和良好搜索能力的量子遗传算法，对VRP求解;Ning T.等人［14］结合量子粒子群优化算法和模拟退火算法，提出了混合量子粒子群优化算法对带时间窗的VRP求解;彭典军［15］在其硕士论文中，主要研究了一种量子进化算法在车辆路径问题中的应用，具体求解了有能力约束车辆路径问题、开放式车辆路径问题、动态网格车辆路径问题、动态需求车辆路径问题;刘勇等人［16］为求解给定期限条件的应急设施选址问题，将量子个体作为博弈者参与到竞争决策中，利用量子位、叠加态等理论提高竞争群体多样性，缩小群体规模，提出了一种量子竞争决策算法;宁涛［17］在其博士论文中，提出了混合量子粒子群优化算法对带时间窗车辆路径问题求解;提出模拟退火算法与量子算法对不确定需求车辆路径问题的数学规划模型求解;结合精英量子均值和混沌扰动理论的量子进化算法对带同时取送货需求的车辆路径问题求解;蔡蓓蓓等人［18］构造了一种混合量子遗传算法，即在传统量子遗传算法随机全局搜索的基础上引入一个免疫算子，通过该算子的局部搜索实现线路内次序的再优化;李川［19］在其硕士论文中，对随机需求的车辆路径问题进行研究，通过设计不同混合量子进化算法对建立的带时间窗和基于模糊预约时间的多目标问题模型求解;任伟［20］提出了一种混合量子免疫进化算法对带时间窗的车辆调度问题求解;吴斌等人［21］针对量子进化算法中旋转角取值的离散性使其解空间的搜索具有跳跃性，提出了基于混沌理论的精英均值计算旋转角算法，对具有同时集送货需求车辆路径问题求解;赵燕伟等人［22］针对带时间窗的随机需求车辆路径问题，建立了基于模糊满意度的多目标数学规划模型，提出了一种基于量子进化算法和粒子群算法分段优化的方法求解Pareto解;李熠等人［23］提出了一种新的混合量子优化算法，即量子蚁群算法对旅行商问题求解。以上学者或研究人员都取得了不错的成果。本文主要考虑车辆行驶过程中的油耗率、载重约束、多车场多车型等因素的VRP问题模型，并提出改进量子遗传算法 (Improved Quantum Genetic Algorithm，IQGA)对该问题求解。

1 问题描述及数学模型

1.1 计算油耗成本

假设某物流公司要给i(i=1，2，…，l)个客户送货，假设油耗率为γij，车辆空载重量为Q0，客户i到j路段车辆的载重为Qij，车辆载重为Qmax，最大载重时的油耗率为γmax，空载时的油耗率为γ0，(i，j)间的油耗成本为cij，单位油耗成本为c0，车辆从客户i到j之间的距离为dij，车辆总油耗成本为Cf。参照文献［24］，假定运载量时变线性函数如式 (1)，其中a和b为一元线性表达式的系数，空载时的油耗时变函数如 (2)，满载时的油耗时变函数如式 (3)，由式 (2)和式 (3)可推导出 (4)，即a的表达式，则 (1)可写成 (5)。(i，j)间的油耗成本如式 (6)所示。式 (7)为每辆车的油耗成本。

1.2 建立数学模型

假设第i个客户的需求量为gi(i=1，2，…，l)，1个车场，同种车型。i到j的行驶时间为tij，车辆启用成本为c，最大行驶里程为Dmax，司机薪酬单位付费为w，总运输时间为T，v＇为通过交通数据拟合的平均速度。不考虑装卸货时间。目标函数为考虑运载量变化影响油耗成本、路况约束、载重约束、单车场、同种车型等情况下，满足所有客户的需求，并使总运输成本最小。预先对需要车辆数进行估计。可以按照式 (8)确定车辆数。

式中，［］表示不大于括号内数字的最大整数;0＜α＜1，是对装车 (或卸车)的复杂程度及约束多少的估计。

假设客户编号为1，2，…，l，车场编号为0。决策变量如式 (9)和 (10)。

建立数学模型

目标函数式 (11)表示总运输成本最小，第一项为涉及运载量的油耗成本，第二项为车辆启用成本，第三项为司机薪酬成本;式 (12)和式 (13)表示每个客户仅由一辆车服务;式 (14)表示车辆的行驶里程约束;式 (15)表示车辆完成任务后，必须回到原车场;式 (16)表示每辆车所运输货物重量不超过车辆载重;式 (17)tij表示i到j的行驶时间;式 (18)为配送完所有任务所花费的时间;式 (19)消除了车辆不是从车场出发的现象。

2 算法设计

2.1 算法思想

量子遗传算法是将量子进化算法与遗传算法相结合，用量子比特、量子编码和量子叠加态的概念，把遗传算法的染色体编码操作替换为量子比特概率幅表示。即用［α，β］T表示一个量子位，α和β代表复数，对应和态的概率幅，并且满足 α2+β2=1，这样可以实现由n个量子位编码的染色体表示2n个状态。在一般的量子进化算法中用量子旋转门和灾变操作代替了遗传算法的交叉和变异操作。量子位作为量子进化计算的最小单位可能处于态、态或两种态的叠加态。在QEA中，长度为L的第K代种群Q(k)的量子个体如式 (20)所示。其中，k表示进化代数，N表示种群的大小，并且满足归一化条件量子个体通过量子门对信息进行操作，首先实施幺正变换对量子态的演化和传递进行控制，然后进化种群。一般使用量子旋转门，调整操作如式 (21)所示。其中[αi，βi]T表示染色体的第i个量子位，θi表示旋转角，旋转角的大小以及符号由调整策略确定。

2.2 IQGA求解问题模型

2.2.1 构造量子染色体

若VRP是由5个客户组成，则量子染色体可以表示成5×5×2的3维量子比特矩阵。使用“先线路后分组”的两步方法进行解码交换:先随机生成服务序列，用产生的随机数 (随机∈ ［0，1］)构造5×5的二维0－1矩阵，则服务顺序由矩阵的横坐标表示，客户编号由矩阵的纵坐标表示，如式 (22)所示;式 (22)矩阵中的客户顺序是4－5－3－1－2，形成车辆配送路线，按照客户顺序进行服务，如果路径中需要的车辆数目超过可提供的车辆数目，则路径有不可行解，需要重新生成量子染色体，逐渐把比特种群转化为整数种群。

2.2.2 更新量子门

QGA通过量子门旋转实现状态间的进化，量子门的设计包括Hadamard变换门、非门以及受控非门等。

2.2.3 通过交叉、变异改变行车路线染色体

交叉算子主要用于产生新个体，实现算法的全局搜索能力。考虑到整个种群的变化趋势及每个个体的变异机会，本节设计了与进化代数相关而与个体适应度无关的交叉概率计算公式，且与考虑油耗率的问题模型相结合，以满载油耗率和空载油耗率两者之和的一半的倒数作为最大交叉概率pcmax，如式(23)所示，以满载油耗率与空载油耗率之和的倒数作为最小交叉概率pcmin，如式 (24)所示。自适应交叉概率如式 (25)和 (26)所示，其中，t为当前进化代数，Gen为预设的最大进化代数。

变异算子主要作用是产生新个体和抑制早熟。设计变异概率的总趋势是逐渐减小而使群体迅速集中。以所有车辆的平均满载率的一半作为最大变异概率pmmax，如式 (27)所示。以pmmax的一半作为最小变异概率pmmin，如式 (28)所示。pm(t)是第t代个体进行变异的概率，如式 (29)和 (30)所示。

2.2.4 改进量子遗传算法执行步骤

QGA的种群更新采用量子旋转门实现，在QGA的基础上，提出通过更新旋转门达到更新种群的操作。方法中旋转角取值如式 (31)所示，其中Δθi表示旋转角的角步长，符号D(αi，βi)表示旋转角的旋转方向，旋转角角度根据表1来确定。表1中，xi表示二进制解x的第i个比特，bi表示最优解b的第i个比特，f(·)表示适应度函数，dta表示影响算法收敛速度的系数，如式 (32)所示，n表示当前进化代数，c'表示 ［0，1］间的常数，lg en为终止代数。

表1 旋转角角度查找表

2.3 改进量子遗传算法流程

改进量子遗传算法流程图如图1所示。

改进量子遗传算法具体步骤如下:

步骤1:初始化种群，确定种群大小、量子变异概率和量子位染色体位数的确定，并且保证所有态在算法搜索早期以相同的概率出现;

步骤2:根据种群中个体的概率幅来对量子叠加态的观测态B进行构造，B={b1，b2，…，bn}，bi(i=1，2，…，n)表示每个个体的观测状态;

步骤3:评价观测态的适应度;

步骤4:记录和保留最佳个体进行，同时判断是否满足终止条件 (多次得到相同解或达到最大迭代次数)，如果条件满足，算法就终止;否则，继续执行下一步;

步骤5:按照式 (12)对量子门旋转角进行动态调整并计算;

步骤6:引进交叉和变异操作，自适应改变交叉概率和变异概率;

步骤7:不断进化，转至步骤2，反复执行到算法终止。

IQGA在进行量子交叉操作和变异操作的基础上，对量子门的旋转角步长进行动态调整以提高算法收敛速度，结合量子态的干涉性和纠缠性同时有效避免了早熟收敛和改善了算法的寻优能力。

图1 改进量子遗传算法流程图

2.4 算法复杂度计算

求解VRP问题的参数表示:种群规模S，迭代次数N，车辆总数n，客户总数m，交叉概率为Sc，变异概率为Sm，则问题规模 (染色体编码长度)可表示为m·n。按照上述步骤执行:

1)把种群从量子比特群转换成二进制种群，则计算复杂度O(S·m·n);

2)把二进制种群转换为十进制种群，则计算复杂度是O(S·m·n);

3)适应度函数计算过程的时间复杂度是O(S·m·n);

4)选择操作对应的时间复杂度是O(S2);

5)交叉操作对应的时间复杂度是O(Sc·S·m2·n2);

6)变异操作对应的时间复杂度是O(Sm·S·m·n);

7)下一代进化对应的时间复杂度是O(S+s);

8)动态调整量子门旋转角的复杂度是O(S·m2·n2)。

综合以上，得出IQGA的时间复杂度如式 (33)所示。

通过计算可知IQGA的时间复杂度和问题规模m2·n2成正比，与已知时间复杂度的量级相同，即IQGA的复杂度并未增加。

3 仿真实验

3.1 实例

广州市某物流公司有1个车场，车场位置为 (50，50)，需给40个客户送货，可用车辆数若干，每辆车的最大配送距离为180 km，客户信息如表2所示。且Qmax=30，c0=0.1，c=10，w=10。

表2 客户信息

3.2 参数设置及结果分析

在Intel(R)CoreTMi5 CPU 3.0 GHz、内存为8.0 G、安装系统为Windows7的PC机上采用Matlab R2010b编程实现。IQEA不同参数取值求解带油耗率VRP的结果如表3所示，可见当γmax=2，γ0=1时，IQEA的寻优效果较好，也说明了满载油耗率越高，系数a越大，油耗成本越高。

表3 自适应遗传算法不同参数取值求解带油耗率VRP的结果

遗传算法的参数设计:最大进化代数G=1 000;编码长度f=20;种群规模N=30;交叉概率和因子突变概率分别为0.95和0.05，采用轮盘赌策略选择算子，多点交叉，均匀变异。

自适应遗传算法参数设定:pcmax=0.667，pcmin=0.333，pmmax=0.095和pmmax=0.047 5，初始化种群m=20，最大迭代次数Gen=800，采用轮盘赌策略选择算子，多点交叉，均匀变异。

改进量子遗传算法参数设计:种群规模N=100，最大进化代数G=1 000，编码长度f=20，c'=0.82，多点交叉，均匀变异。运用三种算法求解问题各10次。

表4 不同算法求解总成本的比较 元

表5 不同算法迭代次数比较 元

由表4、表5可知:IQGA不但能够在较短时间内收敛到最优解和避免早熟，而且无论从配送距离最优解的获取还是从迭代次数的大小方面，IQGA的值优于AGA，明显好于一般GA，也验证了IQGA在求解VRP问题的优越性。

表6 最优路径的具体配送信息

4 结语

交叉概率越大，新个体产生的速度就越快，然而，交叉概率过大时遗传模式被破坏的可能性也越大，使得具有高适应度的个体结构很快就会被破坏;但是交叉概率过小，会使搜索过程缓慢，以至于停滞不前。而变异算子主要是产生新个体和抑制早熟，设计变异概率的总趋势是使它逐渐减小，从而使群体迅速集中。本文提出了引入了交叉操作和变异操作的改进量子遗传算法，提出了带油耗率的VRP，应用设计的算法对问题模型求解，通过与AGA和GA求解的结果相比较，从多个角度证明所设计算法的优越性，研究更大规模问题模型及包含多种扩展特性 (次序关联、不对称、随机需求、需求关联、多周期性、需求可拆分、同时取送货、开放式、服务优先级等)的VRP及其求解算法将是下一步研究方向。

［1］Azi N，Gendreau M，Potvin J Y．An adaptive large neighborhood search for a vehicle routing problem with multiple routes［J］．Computers＆Operations Research，2014，41:167 －173．

［2］Michallet J，Prins C，Amodeo L，et al．Multi－start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services［J］．Computers ＆ Operations Research，2014，41:196 －207．

［3］Mohammed A M，Elhefhawy N A，El－Sherbiny M M，et al．Quantum crossover based quantum genetic algorithm for solving non－linear programming［C］//Informatics and Systems(INFOS)，2012 8th International Conference on．IEEE，2012:BIO －145－BIO－153．

［4］蔡延光，张敏捷，蔡颢，等．混合混沌量子进化算法［J］．系统工程理论与实践，2012，32(10):2207－2214．

［5］Cui L，Wang L，Deng J，et al．A new improved quantum evolution algorithm with local search procedure for capacitated vehicle routing problem［J］．Mathematical Problems in Engineering，2013:17．

［6］Wang L，Kowk S K，Ip W H．Design of an improved quantum－inspired evolutionary algorithm for a transportation problem in logistics systems［J］．Journal of Intelligent Manufacturing，2012，23(6):2227 －2236．

［7］葛显龙，王旭，代应．基于混合量子遗传算法的随机需求车辆调度问题［J］．系统工程，2011，29(3):53－59．

［8］葛显龙，许茂增，王伟鑫．多车型车辆路径问题的量子遗传算法研究［J］．中国管理科学，2013，21(1):125－133．

［9］Zhang J，Wang W，Zhao Y，et al．Multiobjective quantum evolutionary algorithm for the vehicle routing problem with customer satisfaction［J］．Mathematical Problems in Engineering，2012:19．

［10］Michallet J，Prins C，Amodeo L，et al．Multi－ start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services［J］．Computers＆ operations research，2014(41):196 －207．

［11］Crispin A，Syrichas A．Quantum Annealing Algorithm for Vehicle Scheduling［C］//Systems，Man，and Cybernetics(SMC)，2013 IEEE International Conference on．IEEE，2013:3523－3528．

［12］Zheng T，Yamashiro M．Quantum－inspired differential evolutionary algorithm for permutative scheduling problems［M］．Rijeka，Croatia:In-Tech．Evolutionary Algorithms，2011，109 －132．

［13］Zhou L，Li R，Li Q．Research on Vehicle Routing Problem Based on Quantum Genetic Algorithm［C］//ICLEM 2010:Logistics For Sustained Economic Development:Infrastructure，Information，Integration．ASCE，2010:2965－2971．

［14］Ning T，Guo C．Using hybrid quantum algorithm to solve VRPTW［C］//Intelligent Control and Information Processing(ICICIP)，2012 Third International Conference on．IEEE，2012:59－62．

［15］彭典军．车辆路径问题的量子进化算法研究［D］．杭州:浙江工业大学，2009．

［16］刘勇，马良，宁爱兵．给定限期条件下应急选址问题的量子竞争决策算法［J］．运筹与管理，2011，20(3):66－71．

［17］宁涛．混合量子算法在车辆路径问题中应用的研究［D］．大连:大连海事大学，2013．

［18］蔡蓓蓓，张兴华．混合量子遗传算法及其在VRP中的应用［J］．计算机仿真，2010，27(7):267－334．

［19］李川．基于混合量子进化算法的随机车辆路径问题的研究［D］．杭州:浙江工业大学，2011．

［20］任伟．基于量子免疫算法的车辆调度问题的优化［J］．计算机科学，2013，40(5):233－236．

［21］吴斌，钱存华，董敏，等．具有同时集送货需求车辆路径问题的混沌量子进化算法研究［J］．2010，25(3):383－387．

［22］赵燕伟，李川，张景玲，等．一种新的求解多目标随机需求车辆路径问题的算法［J］．计算机集成制造系统，2012，18(3):523－530．

［23］李熠，马良．用量子蚁群算法求解大规模旅行商问题［J］．上海理工大学学报，2012，34(4):355－358．

［24］Xiao Y，Zhao Q，Kaku I，et al．Development of a fuel consumption optimization model for the capacitated vehicle routing problem［J］．Computers＆ Operations Research，2012，39(7):1419－1431．