基于量子遗传算法的作战油料调运优化∗

2021-11-11郭月凯屈少辉朱愈欢陈宇昕

舰船电子工程 2021年10期

关键词：油料运力遗传算法

王帅郭月凯屈少辉朱愈欢王灿陈宇昕

（1.中国人民解放军陆军勤务学院重庆 401331）（2.中国人民解放军32322部队乌鲁木齐 830000）

1 引言

油料调度的突发性、安全性、可靠性等要求都增加了调度油料的困难程度［1～3］。油料的调度问题除了要考虑需求量约束和储备量约束外［4］，还要考虑需求点时间窗口和运力约束等要求［5］。因此传统的数学规划模型难以对问题进行描述［6～7］。

本文对油料调度问题的研究，通过引入需求点时间窗、调度过程中安全性因子，考虑相关单位的运力约束，基于此建立了油料调度模型，采用量子遗传算法对模型进行求解，并通过算例验证了模型和算法的有效性。

2 战时油料调运优化模型

2.1 模型假设

本文中的模型假设如下。

假设1油料储备点均配置有一定数量的运力。运力可以将储备点的油料调往所有的需求点，在本储蓄点储备量为0前，只可返回本储备点且只有返回储备点后才能执行下次调度任务。

假设2油料装（卸）载时间忽略不计，运力运输速度在任何情况下保持不变。

假设3油料储备点与需求点之间、需求点与需求点之间的最佳路径均已知，路程均已知，运力沿最佳路径往返。最佳路径有安全威胁时，路程可适当增加。

假设4油料储备点与需求点地理位置均已知。

一般情况下，各油料储备点均配置有一定数量的运力，在完成本储备点调度任务后可以参与其他储备点任务，因此，假设1符合油料调度的实际；假设2～4主要是为了方便计算，最佳路径的安全威胁可以简化为路程增加10%。

2.2 问题形式化描述

本文以某地区的油料调度为例，多个需求点对某种油料提出需求。选择临近地区若干油料仓库、野战油料仓库等作为油料供给点。通过对供给点的油料储存量和各需求点的油料需求量，并充分考虑需求点的时间窗约束，规划出油料调度方案，使得各需求点获取油料的时间最短。

2.3 模型的建立

根据上述对问题的描述，在满足油料保障时间窗口约束下，最大限度地满足需求点的需求，同时保证各需求点开始保障的时间尽可能早，从而构建数学模型如下：

其中η和 ρ分别为目标Z1和Z2的权重，分别取0.4、0.6，即优先满足需求量目标。根据上述公式，可将目标函数转化为

综合上述的分析，本模型的约束条件可以表示如下：

式（5）表示每个需求点的需求量不低于该需求点的供给量，式（6）表示调运的油料总和应不高于油料的储备总量，式（7）表示每个运力梯队离开供给点的时间不早于需求点最早开始保障的时间，不早于运力梯队完成保障任务回到需求点的时间，式（8）表示第a个供给点在出任务的运力数量不大于第a个供给点的运力数量，式（9）表示当第a个供给点的所有运力被派出后，下一个梯队从供给点出发的时间应不小于上一运力梯队回到供给点的时间。

3 求解算法

本文针对上述问题采用量子遗传算法进行计算。量子遗传算法是一种求解全局最优解的方法，具有鲁棒性强、易操作等特点，是解决优化问题的重要算法。

3.1 问题的转化

结合相关文献，本文采用按照运输工具任务序列的编码方式。编码方式描述为在某个油料调度方案中，将所有任务序列排列在一条染色体中，以每个运输工具的任务作为染色体的子基因，每个子基因的基因位表示为供应点或者需求点。根据所建模型可知，运输工具需要在保障时间窗内多次派送才能满足某个需求点的需求，故根据任务量和运载力的比值设定虚拟需求点，描述为将一次派送所满足的需求设置为一个需求点，则满足所有需求的总虚拟需求点的个数为

上式中，s为总虚拟需求点个数，βb为需求点b的需求量，x1为一次派送的运载量。

3.2 算法的实现

3.2.1 量子编码转化

染色体编码方式描述为将所有虚拟需求点和供应点以及运输工具的序号编码在染色体上，形成由3个子串编码而成的染色体，如下例：

1-2-1-4-1-1（子串1）-1-3-2-3-1-2（子串2）-1-5-12-7-9-8（子串3）

子串1表示由自然数1～4随机生成的s个供应点编码，表示方案中4个供应点的总供应次数为s次，子串2表示由自然数1～3随机生成的s个运输工具编码，表示3种运输工具的所有运输次数为s次，子串3表示由自然数5～16随机生成的s个需求点编码，表示12个实际需求点的虚拟需求点为s个。

对于运输工具1，找到子串2中序号1的所有位置，并对应查找到子串1和子串3中对应位置的供应点序号和需求点序号，则表示运输工具1的调运方案为

1-14-4-11-1-5-1-9-2-15

上述描述为实数编码方式，在量子遗传算法中需要将实数编码方式转化为量子编码方式，并通过二进制转换成0-1矩阵进行量子旋转门操作得到进化之后的染色体编码。

3.2.2 量子旋转门操作

由于量子比特的叠加态形式复杂，不能采取传统遗传算法的染色体选择、交叉、变异等操作实现染色体的更新。量子比特由于采用概率幅的表示方式，可以采取旋转复数幅的方式进行量子态的干涉和杂交，这种基于量子比特基态的染色体进化方式的重点在于量子旋转门的设计，其形式为

量子更新为

[αi，βi]'表示第i量子态，θi为旋转角。

θi的取值由α，β决定。具体如表1。

表1 α，β取值表（部分）

3.2.3 量子交叉、变异、灾变操作

对转化为量子编码后的染色体进行旋转门操作后得到杂交后的新染色体，下一步进行量子交叉操作：选取配对的染色体的子串中随机选取两个交叉点，互换交叉点基因，得到新个体。若交叉后的个体在进行适应函数迭代优化后没有达到最优，此时应采取量子变异操作，基于高斯变异或者均匀变异方式对量子位进行改变，避免了算法的过早收敛。量子遗传算法如果陷入了局部最优，则应对染色体进行灾变操作。

3.3 算法的终止条件

设定量子遗传算法的最大迭代次数MAX⁃GEN，当迭代次数gen＞MAXGEN时自动终止。

4 模型的应用及分析

4.1 模型的应用

为验证模型的可行性，通过算例进行仿真试验。假设有两个油料储备油库、两个野战油库、12个需求点，其位置信息在400km*400km的平面坐标上展示，需求点为随机生成，各个点的编号及位置分布。担任油料调度任务的运力均由供给点提供，运力由运输工具1、运输工具2、运输工具3组成，具体数据见表2。

表2 供给点相关数据（部分数据）

表3 需求点相关数据

表4 运力相关数据（部分数据）

针对上述算例，采用量子遗传算法进行油料的调度方案优化，同时采用实数编码方式运用常规遗传算法对本算例进行优化求解。常规遗传算法中的交叉概率、变异概率以及代沟设置为Pc=0.9、Pm=0.05、GGAP=0.9，量子遗传算法的变异因子设定为pmutaition=0.01。根据相关参数设置，得到如下的油料调度方案。

根据表5，做出任务甘特图，较为直观地看出需求点对应的每个时间窗内的调度任务。

表5 油料调运方案（部分数据）

图1 调度任务甘特图

4.2 结果分析

图2为分别采用常规遗传算法以及量子遗传算法优化过程中最优个体的适应度收敛情况对比，可以看出由于量子遗传算法采用了量子比特编码方式，最优个体的适应度的遗传代数较小，收敛速度快。而标准遗传算法在接近最大遗传代数时最优适应度仍未稳定下来，可见在求解复杂的油料的调度模型时，量子遗传算法较之常规遗传算法更适合用于求解最优解。

图2 量子遗传算法与常规遗传算法对比图

图3为采用量子遗传算法得到的油料调度热力图，圆越大代表由该供应点至需求点派送的运输工具数量越多，如图中［supply_3，Demand_2］=4，表示在保障时间窗口内从供应点3至需求点2总共调度了4辆运输工具1。油料调度热力图清晰地展示了各种运输工具的油料调度情况。

图3 运输工具1的油料调度热力图

图4则为某运输工具的油料调度安排图，以带运输工具数量的地理坐标有向箭头表示油料的调度情况，结合arcgis技术可以进一步在地图上精准显示，实现油料调度的地理信息可视化。

图4 运输工具调度安排图

图5为某需求点的运力情况色块图，其中，深色色块［i，j］对应的判断矩阵数值为-1，表示供应点i对应的运输工具j存在运力不足的情况。此时为满足该需求点的油料需求应当进行横向协调或纵向协调。横向协调即由其他供应点提供运力支援，纵向协调则表示运力不足部分由其他运输工具替代。通过需求点的运力情况判断，可以精准反映该点需求量的实际满足情况，从而为油料调度决策提供第一手资料。