求解动态需求车辆调度问题的自适应量子遗传算法*

郑丹阳， 毛剑琳， 郭 宁, 曲蔚贤， 王昌征

(昆明理工大学 信息工程与自动化学院，云南 昆明 650500)



求解动态需求车辆调度问题的自适应量子遗传算法*

郑丹阳， 毛剑琳， 郭 宁, 曲蔚贤， 王昌征

(昆明理工大学 信息工程与自动化学院，云南 昆明 650500)

针对物流配送过程中存在的动态车辆调度问题，即带载车量约束的实时优化车辆路径问题，提出一种自适应量子遗传算法，用于最小化配送成本。根据搜索点目标函数的变化率，提出一种自适应量子旋转门更新方式，并通过子种群适应度值的变化确定量子旋转角的方向和大小，进而引导种群进化方向，提高算法的全局搜索广泛性；设计了一种变异操作，用于保持自适应量子遗传算法的种群多样性，进而提高算法全局搜索的宽泛性；引入基于两元素搜索原则的局部搜索方法来增强算法的局部优化能力。仿真实验和算法比较验证了所提算法的有效性和优越性。

物流配送; 自适应量子遗传算法； 动态车辆路径问题； 全局搜索； 局部优化

0 引 言

带约束能力的动态车辆调度(capacitated dynamic vehicle routing problem,DVRP)是通过对实时出现的客户新需求的配送顺序进行优化调度，使某种指标达到最优。

在求解DVRP方面主流的智能优化算法主要包括遗传算法(GA)[1]、蚁群算法(ACA)[2]、粒子群优化(PSO)算法[3]、模拟退火算法(SA)等。使用智能算法求解组合优化问题，已经成为智能计算领域研究的热点[4]。例如，文献[5]提出利用贪婪算法和GA求解仓储车辆调度问题。文献[6]提出了利用混合PSO算法对初始阶段进行优化，再利用贪婪插入算法实现再优化，实现对动态车辆调度问题的求解。文献[7]利用改进的ACA对飞机冲突解脱的路径进行规划，并验证了改进的算法在求解的优越性。

在混合量子研究方面，文献[8]提出量子进化算法，同时采用邻近插入法结合两元素法再优化线路内次序的方式增强局部开发能力。文献[9]提出将量子计算与ACA相结合的量子蚁群算法。文献[10]提出量子遗传算法用于求解车辆路径问题，用于最小化配送路程，得到的解均优于现存方法。文献[11]提出将量子算法与PSO算法相结合，并与其他算法比较，验证了其有效性。

本文提出一种自适应量子旋转门更新方式，自适应量子遗传算法(SAQGA)用于求解最小配送成本指标下的DVRP问题。通过搜索点目标函数的变化率构造量子旋转门更新调整策略，同时设计一种变异操作，保持算法的种群多样性，并引入两元素邻域搜索来增强算法的局部开发能力。仿真实验和算法比较验证了SAQGA的有效性和优越性。

1 问题描述

设配送中心(i=0)可用k辆配送车辆,k=1,2,…,K,对M位客户进行运输配送，每个车辆载重量为Q,每个各户的需求量为qi，且qi

目标函数

(1)

约束条件

(2)

(3)

(4)

(5)

(6)

式(1)为目标函数,表示运输成本最低,式(1)保证车辆k所承担的运输任务总和不超过本身的载重量；式(3)保证每个客户都被访问；式(4)和式(5)保证每个客户仅被一辆车访问一次；式(6)用于消除子回路。

在执行预优化阶段配送任务的某时刻进行再优化，在开始时刻，由于执行预优化阶段的配送任务，配送中心的部分车辆已离开配送中心并已服务部分客户，导致配送的车辆位于不同的客户处，拥有不同的剩余装载量，直接调度无法进行，所以,需引入虚拟配送中心的概念，将车辆所在的客户点视为虚拟配送中心。

设预优化阶段未服务客户数与第二阶段新增加的客户总数N,预优化阶段派出 辆车，每辆车的剩余装载量为Qs,s=1,2,…,S虚拟配送中心编号为N+1,N+2,…,N+S,新排出的车辆数为T,即：

目标函数

(7)

约束条件

(8)

(9)

(10)

(11)

(12)

(13)

式(7)为目标函数,表示运输成本最低；式(8)和式(9)保证车辆k所承担的运输任务总和不超过本身的载重量；式(10)保证每个客户都被访问；式(11)和式(12)保证每个客户仅被一辆车访问一次；式(13)用于消除子回路。

2 SAQGA

2.1 自适应量子旋转门更新机制

本文提出的SAQGA是通过更新量子旋转角的大小和方向，进而指导种群的进化方向，因而量子旋转角的大小和方向是影响算法性能的关键。SAQGA采用根据搜索点目标函数的变化率来确定量子旋转角的大小和方向。

自适应量子旋转角的定义如式(14)所示

(14)

式中θ0为初始旋转角;sign(A)为矩阵A的符号，同时决定旋转角的方向，旋转角的旋转方向由以下规则决定：当A≠0，旋转方向为-sign(A);当A=0，方向可正可负。A的定义如式(15)所示

(15)

式中α0和β0(本代)为全局最优解的概率幅;α1和β0为第t代的量子比特概率幅。自适应因子B的定义如式(16)所示

(16)

(17)

(18)

(19)

在式(17)～式(19)中，i=1,2,…m,m为种群大小；j为量子比特；Xp和Xc分别为父代与子代染色体。

(20)

2.2 变异操作

为防止算法陷入局部最优而导致“早熟收敛”，在SAQGA中引入变异操作，对gen代种群依照概率pmutation进行变异操作，得到变异后的种群，进而提高了种群的多样性和SAQGA的全局搜索的宽度。变异操作的步骤如下：

1)对于第gen代种群中的每一个量子位(i,j)，随机产生变异概率pmutation_rand(i,j);

2)如果pmutation>pmutation_rand(i,j),则θij=0.5π-θij;否则,θij=θij;

3)u=[cosθij-sinθijcosθijsinθij],y=u×[a;b]T。

2.3 两元素局部搜索

为增强算法的局部开发能力，SAQGA引入了两元素局部搜索。两元素局部搜索法通过对边交换,在初始可行解的邻域中对初始解进行调整，每次交换使可行解得到改进，直到邻域中不能再改进为止。如图1所示,以(i,j),(i+1,j+1)代替(j,i+1),(j,j+1),交换后线路中的路径被反向，若交换后的行车路线长度变小，则采用两元素法形成的新路线为更优解;否则,将原行车路线定位更优解。

图1 两元素局部搜索原理

2.4 适应度值计算

首先根据生成的可执行调度路线及每辆车的装载量确定每辆车的首个客户和最后一个客户，再进行行车路程及运输成本的计算，具体操作步骤如下：

1)根据每辆车的装载量确定每辆车所要服务的客户。

2)形成新的带车辆的可执行调度路线图。

3)计算可执行调度路线图的路程和运输成本。

2.5 SAQGA步骤

结合2.1～2.4，SAQGA的步骤如下：

1)令进化代数gen=1;

2)种群初始化，随机产生初始种群p;

3)染色体解码并计算每条染色体的适应度值;

4)量子旋转门更新;

5)量子比特种群变异操作;

6)对所形成的初始路径进行局部搜索，并进一步得到全局最优个体;

7)gen=gen+1,如果gen≤gen_max,则转步骤(2)，否则,输出最优路径。

由SAQGA步骤可知:SAQGA通过自适应量子旋转门操作，使算法获得更加明确的搜索方向和尺度，进而提高算法全局搜索的广泛性；通过变异操作，有效地保持种群的多样性，提高算法全局搜索的宽泛性；通过引入基于两元素的局部搜索，提高算法的局部搜索能力。综上所述，SAQGA在全局探索方式和局部搜索策略上均做了有效改进，算法有望取得DVRP的优良解。

3 仿真实验与算法比较

3.1 实验设置

为了对SAQGA的性能进行验证，将SAQGA与两种SAQGA的变形算法和一种其他文献中的算法进行比较。所有算法的测试程序均由Matlab编码实现，操作系统的CPU主频为2.8GHz，内存为1.0GB。每种算法均独立重复运行20次，每次运行的迭代次数为100。

SAQGA的关键操作主要包括：1)使用量子遗传算法(QGA)；2)使用基于搜索点目标函数的变化率原则的量子自适应旋转门调整策略；3)使用变异操作；4)使用基于两元素邻域搜索的局部搜索。为了考察上述操作的有效性，考虑如下变形算法：

1)QGA：标准的量子遗传算法，使用文献[11]所述的两阶段实时优化规则，所有参数的设置与文献一致;

2)SAQGA_V1：标准的量子遗传算法，使用自适应量子旋转门调整策略，参数设置与QGA一致;

3)SAQGA_V2：在SAQGA_V1的基础上加入变异操作;

4)SAQGA_V3：在SAQGA_V1的基础上加入两元素局部搜索操作;

5)SAQGA：在SAQGA_V2的基础上加入两元素邻域搜索。

3.2SAQGA与其变形算法比较

由图2可知，量子遗传算法在55代左右收敛，自适应量子遗传算在45代左右收敛，加入变异操作和两元素局部搜索的自适应量子遗传算法在30代左右收敛，这得益于自适应量子遗传算法以及变异操作和局部搜索的有效性。

图2 算法迭代

QGA,SAQGA_V1,SAQGA_V2,SAQGA_V3与SAQGA的比较结果如表1所示。由表1可知:SAQGA_V1解的质量明显优于QGA，表明在求解DVRP时，自适应量子旋转门更新机制更加有效，这是由于DVRP带有容量约束，同时又带有行车距离的限制；SAQGA_V2解优于SAQGA_V1，表明在自适应量子混合算法中加入变异操作后，有利于提高解的质量；SAQGA_V3解优于SAQGA_V1，虽然SAQGA_V3中的全局搜索不如SAQGA_V1中的有效，但加入有效的局部搜索后，仍然能明显提升算法的性能；SAQGA的解明显优于SAQGA_V2和SAQGA_V3，表明同时采用改进的全局搜索和有效的局部搜索可获得问题的优质解。综上所述，SAQGA中的自适应量子旋转门更新机制有助于提高算法的全局搜索能力，基于两元素局部搜索和变异操作可加强算法的局部搜索能力，从而使算法在全局搜索和局部搜索之间达到较好的平衡，有效求解DVRP。

表1 SAQGA与其变形算法比较结果

3.3 SAQGA与其他算法比较

采用文献[11]中的实验数据设置，每种算法均独立重复运行20次，每次运行的迭代次数为100。SAQGA与GA,IGA,ACA,IACA的比较结果如表2所示。

表2 SAQGA与其他算法比较结果

从表2可知，SAQGA的结果明显优于两种传统启发式算法和两种自适应启发式算法，从而表明了SAQGA求解DVRP的优越性。虽然SAQGA中加入两元素局部搜索，但其搜索成功率明显优于其他4种算法，从而表明了SAQGA求解DVRP的有效性。综上所述，SAQGA是求解DVRP的一种优越且有效的算法。

4 结束语

本文提出了一种SAQGA，用于求解动态车辆调度问题。首次将SAQGA用于求解该类问题。在算法改进上，SAQGA采用一种新的策略更新量子旋转门，进而使种群的进化方式得到了改进，使算法的搜索方向更加明确；此外，SAQGA融合了变异操作，有效保持了算法进化过程中的种群多样性水平；最后，通过引入两元素局部搜索来增强算法的局部开发能力。通过仿真实验和算法比较验证了SAQGA求解DVRP的有效性和优越性。下一步将针对多车场动态车辆调度问题设计基于QGA的有效求解算法。

[1] Berger J,Salois M,Begin R.A hybrid genetic algorithm for the vehicle routing problem with time windows[C]∥12th Biennial Conference of the Canadian Society for Computational Studies of Intelligence on Advances in Artificial Intelligence,1998:114-127.

[2] Czech Z J,Czarnas P.Parallel simulated for the vehicle routing problem with time windows[C]∥Proceedings of 10th Euromicro Workshop on Parallel,Distributed and Network-based Processing,2002:376-383.

[3] 肖健梅,黄有方,李军军.基于离散微粒子群优化的物流配送车辆路径问题[J].系统工程,2005,23(4):97-100.

[4] Dantzing G B,Ramser J H.The truck dispatching problem[J].Management Science,1959,4(6):80-91.

[5] 王友钊,彭宇翔,潘芬兰.基于贪心算法和遗传算法的仓储车辆调度算法[J].传感器与微系统,2012,31(10):125-128.

[6] 周 慧,周 良,丁秋林.多目标动态车辆路径问题建模及优化[J].计算机科学，2015,42(6):204-209.

[7] 倪 壮，肖 刚，敬忠良,等.改进蚁群算法的飞机冲突解脱路径规划方法[J].传感器与微系统,2016,35(4):130-133.

[8] 赵燕伟，彭典军，张景玲，等.有能力约束车辆路径问题的量子进化算法[J].系统工程理论与实践，2009,29(2):159-167.

[9] 赵燕伟.多车型同时取送货问题的低碳路径研究[J].浙江工业大学学报，2015,43(1):18-23.

[10] 王 旭,葛显龙.基于两阶段求解算法的动态车辆调度问题研究[J].控制与决策，2012,27(2):175-181.

[11] 陆建山,周鸿波,谢伟东.基于量子粒子群优化的动态标定辨识方法[J].传感器与微系统,2016,35(6):27-30.

[12] 沙林秀,贺昱曜.一种新的自适应量子遗传算法[J].计算机工程，2013,39(9):218-221.

Self-adaptive quantum genetic algorithm for dynamic vehicle scheduling problem*

ZHENG Dan-yang, MAO Jian-lin, GUO Ning, QU Wei-xian, WANG Chang-zheng

(School of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China)

Aiming at dynamic vehicle scheduling problem that is dynamic vehicle routing problem(DVRP)with vehicle capacity constraints in real time existed in process of logistics distribution,self-adaptive quantum genetic algorithm(SAQGA)is proposed to minimize the distribution cost.According to change rate of search point target functions, a new update mode adaptive quantum rotation gate is presented,and direction and magnitude of the quantum rotating angle is determined by changes in fitness values of sub-propulation,thus evolutionary direction of population is guided to improve depth of global search of algorithm.A mutation operation is designed to keep the population diversity of the self-adaptive quantum genetic algorithm and width of the global search of algorithm is improved.To enhance the local optimization ability,local search method based on the principle of two elements search is introduced.Simulation experiments and algorithm comparisons demonstrate the effectiveness and the superiority of the proposed algorithm.

logistics distribution; self-adaptive quantum genetic algorithm(SAQGA); dynamic vehicle routing problem(DVRP); global search; local optimization

10.13873/J.1000—9787(2017)08—0130—04

2016—07—27

国家自然科学基金资助项目(61163051); 云南省应用基础研究基金资助项目(2009ZC050M)

TP 301.6

A

1000—9787(2017)08—0130—04

郑丹阳(1992-)，女，硕士研究生，研究方向为算法优化，车辆调度。