基于越库配送车辆调度的混合量子遗传算法(QGA)研究

白士宇殷雪峰

(1.沈阳工学院 辽宁省数控机床信息物理融合与智能制造重点实验室, 辽宁 抚顺 113122；2.沈阳工学院 信息与控制学院，辽宁 抚顺 113122)

0 引言

物流配送在消费活动过程中与消费者有密不可分的关系，在整个物流过程当中，高效配送一直是物流行业的核心问题之一，配送调度是否高效合理对于公司成本、收益都有至关重要的影响。由此可见，车辆调度优化是物流的关键一环，对车辆进行调度优化的理论进行分析和研究是当代物流集约化、发展职能交通运输系统、建立新时代智能电子商务体系的重要基础。

配送中心作为当代整个物流系统的中枢系统，其配送调度的智能越来越多样化，但是其根本工作职能依旧是对大批订单多调度和控制[1]，其中主要包含生成合理、高效的调度方案，发送调度的执行命令以及能够向供应商发送自动补充货源的指令，因此，作为现代物流体系核心之一的配送中心，其面临的最困难的任务就是提交高效配送方案。

在1959年，Dantzig和Ramser首次提出了物流配送以及车辆优化调度的相关问题，问题提出后，运筹学、管理学、应用数学、图与网络、计算机应用科学等一系列相关学科的领域内的专家和管理者对该问题产生了极大的重视[2]，车辆调度优化一时间成为了一个研究热点问题，在众多科研人员努力之后，取得了一系列该课题的进展和成果。而对于这个难点，研究学者经常采用的方案有遗传算法、职能优化算法以及启发式算法等一系列解决方法[3]。

本文尝试采用混合量子遗传算法求解该问题，实验结果证明，混合量子遗传算法是解决该问题的一种有效的方案。

1 量子遗传算法概述

1.1 量子计算及遗传算法

1.1.1 量子计算

量子信息处理以及其计算过程是建立在量子比特基础上的一种新型概念，量子比特常常被作为一种非常抽象的数学对象被科研学者进行对待，文章通过介绍编码的基本概念以及相关的特性，将车辆调度和配送量之间进行关联，从而将抽象的物理学概念和现实中的应用工程建立起联系[4]。

在经典比特框架下，只有0和1两种存在状态，但是在量子学中，量子比特可以介于0和1两种本征状态之外的第三中叠加状态，如下公式所示：

|ψ> =α|0>+β|1>

其中:α和β分别是左失和右矢的幅度，在实际操作量子比特的过程当中，应当有以下的约束。

|α|2+|β|2=1

量子态的相干性指的是两种状态的振幅相互可以干涉，如果将这种相干的特性应用在车辆配送的问题当中，则可以看作影响配送量的两种不同的趋势，一旦两种α、β概率幅度改变，则量子比特|α|2和|β|2处于0和1的概率也会变化，映射到实际问题当中则是配送量发生变化，这样就能够表示出配送中心是否全额占有或者不完全占有，并且可以处于两种状态下的任意一个状态，能够极大地扩展信息搜索空间[5]。

传统QGA中，量子门的作用是使种群产生变异，其更新过程如下:

[α'iβ'i]T=U·[αiβi]T

其中旋转量子门U为：

根据设计的调整策略来给定旋转角的大小和符号。

1.1.2 遗传算法

遗传算法是一种新型的并行计算寻优算法，它所基于的思想是达尔文进化论中的“适者生存”[6]，它利用这种思想将寻优问题的求解过程表示为不同“染色体”的适者生存的过程，通过“染色体”随着迭代次数的增加不断进化，在这个过程中产生复制、交叉、变异等一系列行为，最终收敛到问题的最优解或者满意解的过程[7]。

遗传算法的主要步骤为：首先构造满足一定约束条件的染色体，对数据进行编码，这个过程的目的主要是使优化问题的解形式与遗传算法的运算相适应。在实际编码过程中， 应该尽可能的选取符合问题的约束，否则将会对遗传算法的计算效率产生较大的影响。编码过程如下：

ouuty= Encoding(inputx)

其中：x为所输入的数据，进行一定方式的编码后得到编码输出y。

第二步为产生初始化种群，选择初始化种群的数量，其次是根据实际问题的目标函数进行适应度函数的选择或构造，通过计算每个染色体的适应度反映出染色体的优劣程度。假设f为目标函数，F是相对适应度，则若目标函数为最大化问题，则有：

F(x)=f(x)

其中:Cmin为f(x)的最小估计。

当适应度函数被确定下来后，今后的复制过程即为依据适应度大小的概率分布确定下一代中哪些染色体“适应生存”或者“不适者被淘汰”[8]。染色体的交叉同样是进行遗传的一个重要步骤，子代遗传的基因是由父代染色体之间的交叉相互并入而产生的[9]。子代的产生不仅仅是一个生产过程，同样是一个变异过程，在新的解产生后，随着基因突变的发生，量子旋转门U使得某些染色体的编码发生了变化:

因此新的解会有更多可能性和更大的遍历性。

1.2 混合量子遗传算法的实现过程

在应用当中，量子算法和遗传算法都是针对量子位进行实现的，因此转化到二进制串仅仅是为了计算个体适配值，但是在函数优化中存在大量针对二进制直接编码的操作，因此考虑传统遗传算法和量子算法进行混合[10]，考虑采用如图1所示的混合量子遗传算法。

图1 混合量子遗传算法分析框架

考虑将传统二进制编码的BGA和实数编码的RGA进行混合，得到BQGA编码方式。进行随机初始化第一代种群:

Gi(0)=randominit()

混合算法在纵向不断将Gi(0)进行迭代QGA搜索，采用单点交叉和算数交叉的方法，保留优势种群:

Gi(n+1)=QGAsearch(Gi(n))

横向对每一代进行一定种群变换

G'i(n)=Transform(Gi(n))

G'i(n)为同代变换后的种群，将种群进行择优后，获得优势种群，横向同样可以采用多代搜索的方法。

2 车辆调度优化问题建模

对于最优物流路径的优化问题，我们可以将其用模型进行概括。图2是传统的物流配送模式示意图,而新型的物流调度模型为图3所示。

图2 传统物流配送模式

首先从物流中心调度多辆汽车派往不同的客户进行送货，此时每辆车的载重量是一定的，而每个客户的位置以及需求也是确定的，因此问题即为高效规划一条车辆配送的路线，使得目标函数得到优化，此时每条路径上的汽车总承载量要大于客户的需求总量、每条路径上的长度要小于汽车配送的最大行驶距离，最关键的一点是所有客户的需要要得到满足，在送货过程中只有一两车进行配送[11]。

图3 新型物流配送模式

将此过程用数学模型确立，假设总调度中心有量货车，第k量火车的承重为Qk(1，2，3，…，C)，一次送货的行驶距离最远Dk，总共要求运往L个站点，其中每个站点需要qi(1，2，3，…，L)，两个站点之间的间距可以表示为dij(i，j=1，2，3，…，L)，中心到各个站点的距离表示为d0j(i，j=1，2，3，…，L)。再设置为第辆货车配送的需求点(nk=0表示未使用的第k辆汽车)，并且第辆汽车的行进路线表示Rk，Rk中的元素表示需求点rki在路径Rk中的顺序为i。物流中心则表示为rk0=0，目标函数取到最优时，配送距离可以达到最短，因此可以建立起车辆调度优化问题的基本数学模型。

目标函数可以表示为:

规定了每条路径的总长度不会大于货车一次行驶的最远距离，约束了每条行驶路径上的客户总数小于等于总客户的数量。

表明每个站点都会得到货物的配送。限制单个客户仅可有一辆货车进行送货，而不能多个货车进行送货。

上式说明当某货车服务的站点数目大于等于1，则该货车已经作出了配送的行为。

3 基于路径优化的混合量子遗传算法

3.1 编码方法和适应度研究

3.1.1 编码方式研究

如前所述，在量子计算中存储信息的最小单元是量子位或量子比特，而量子位可能处于不同的状态0或1，也可能是两种状态的线性叠加[12]。

在混合量子遗传算法中，第m代种群Q(m)中的一个长度为M位的量子比特的个体可以用下式进行表示：

公式中的N代表了种群的大小，m为种群进化的代的次数，对于所有的i值，均有：

|αi|2+|βi|2=1

量子遗传算法采用了量子比特的形式来代表染色体，因此一个染色体可以同时用多个状态信息来进行表示，当位数为M时，量子染色体即可以表示2^M个能够发生的状态，因此可以有效地保持种群的多样性，在应用中即表现为车辆调度优化的更多可能性，能够克服陷入局部收敛的结果。

3.1.2 适应度研究

对于某一车辆的具体配送方案，如果需要判断其是否优秀，首先要使其满足一定的约束条件，其次要正确计算问题的目标函数[13]。本文尝试采用的是将客户进行直接排列的编码方式，确定其配送方案，因此每个客户都可以得到配送的服务，此外假定了每个客户仅由一台车辆进行配送的约束，该方案同时满足了每条行车路径上的各个站点的需求量会小于等于单个车辆进行一次送货的最大运货量的约束，但是其无法对配送路径的数量小于送货车数进行限制。

个体的适应度就可以表示为：

F=1/(Z+K×Pw)

对于一个单独的个体来说，假设对应的配送路径的条数与送货货车的数量的差为K，目标函数的数值为Z，K看作个体所对应的送货路径中不可行的路线的数目，对于每一条不可行的路线存在一个惩罚因子Pw，惩罚因子的取值根据目标函数来具体确定。

3.2 路径优化混合量子遗传算法流程

整个混合量子遗传算法如图4所示。

图4 混合量子遗传算法图

首先初始化量子比特种群，之后通过初始的量子比特种群产生二进制种群，对于不可行解，我们采用修复函数对其进行修正，使其可解，将得到的二进制数据进行解码后，得到每个车辆生成的线路，得到线路后加入免疫因子使其再优化，筛选较好的路径，之后对每条路径进行评价，挑选出其中最佳的个体(行驶路径)，之后进行量子旋转门的更新，判断是否满足停止条件，从而进行算法的迭代或终止。

假定存在一个调度中心共有5辆货车，每辆货车的最大承重均为8吨，每辆车每次配送的最远距离为50，需要向20个客商进行配送。调度中心的坐标设定为(14.5，13.0)，每个客户的需求与其需求的关系如表所示，根据此选择最佳的送货路线，使得送货距离的值最小。

分别设定20个地区的坐标如下：(12.8,8.5)，(18.4,3.4)，(15.4,16.6)，(18.9,15.2)，(15.5,11.6)，(3.9,10.6)，(10.6,7.6)，(8.6,8.4)，(12.5,2.1)，(13.8,5.2)，(6.7,16.9)，(14.8,2.6)，(1.8,8.7)，(17.1，11.0)，(7.4,1.0)，(0.2,2.8)，(11.9,19.8)，(13.2,15.1)，(6.4,5.6)，(9.6,14.8)，其客户的需求依次设置如下：0.1，0.4，1.2，1.5，0.8，1.3，1.7，0.6，1.2，0.4，0.9，1.3，1.3，1.9，1.7，1.1，1.5，1.6，1.7，1.5。

4 实验仿真及结果

4.1 实验描述

实际过程中，车辆调度的软件环境如图5所示。在本次实验过程中采用Matlab进行仿真和测试，如图6所示。

图6 实验仿真环境

在具体实现过程中，为了进行对比，传统的量子遗传算法的参数设置如下：设置初始种群的规模为50，每条染色体上的量子位数设置为2，种群最大迭代次数分别设置为1000次和2000次，惩罚权重为设置为100。

在添加免疫算子参数后的混合量子遗传算法中，将接种率设置为50%，其余基本参数设置与传统量子遗传算法相同。

图7 20个客户的位置

4.2 实验结果

实验中将传统的量子遗传算法和混合量子遗传算法相比较，得到结果如图8所示，可以看出，在初始数据相同的情况下，同样运行5次取平均值，可以看出无论是1000次还是2000次迭代，混合量子遗传算法的归一化最佳适应度的结果要明显优于传统量子遗传算法。

图8 归一化最佳适应度曲线对比

其最佳的运货物流路径为第一辆车为0—18—17—3—4—14—0；第二辆货车的路径为0—20—11—6—13—16—19—0；第三辆车的路径为0—7—8—15—9—12—2—10—1—0；第四辆车的路径为0—5—0；由于目标函数经过变换后得到的归一化适应度则可以反映出算法的优劣。因此可以看出，混合量子遗传算法得到的最优解的效果要更好，在一定程度上优化了车辆调度的问题。图9是车辆路线。

图9 最佳路线

5 实验仿真及结果

对于车辆调度优化的问题，一般可以概括为:存在众多的车辆卸货点与车辆装货点，车辆调度中心选择并组织高效的行车线路，使得运货车辆能够成功依次通过不同节点，同时在满足如货物需求、交货与发货时间、车辆容量等一系列要求的情况下，达到如行车路程最短、花费的成本最低、使用尽可能少的车辆等一系列目标。

本文以车辆调度为模型，具体针对配送中心调度货车进行货物配送进行了分析和探讨，通过建立简单明了的数学模型对复杂的问题进行简化和分析。通过本次实验，利用一个加入免疫算子的用于求解优化车辆路径的混合量子遗传算法，对传统的量子遗传算法进行优化，通过实际实验对比，设置在相同的参数条件下， 改进后的混合量子遗传算法具有更好的性能表现，是一个能更有效地解决车辆调度路径优化问题的算法。

这种算法不仅仅能够解决调度中心的货物配送问题，同时也可以应用在其他背景下去解决相应的组合优化问题，对货物的供应链管理以及调度有很大的借鉴和参考价值，本文中所展示的混合量子遗传算法在求解优化问题上具有较为广阔的发展前景，值得深入研究。