一种多目标烟花算法的低碳疫苗冷链优化配送方法

摘要

本发明公开了一种多目标烟花算法的低碳疫苗冷链优化配送方法，包括以下步骤：(1)问题信息读取；(2)初始化算法参数；(3)随机生成个体，根据消除车辆约束的解码方式进行解码，并计算其目标向量，区分出可行解与不可行解；(4)部分映射爆炸算子；(5)变异算子；(6)双外部档案协同进化机制；(7)更新种群；(8)选择出下一代烟花后，从中随机选择一个个体，计算该个体与其他烟花的相似度；(9)判断是否达到终止条件，若达到，则终止迭代，输出可行解集。本发明具有较好的收敛性和多样性，求解准确且稳定，并具有良好的可扩展性，适用于求解低碳疫苗冷链配送问题这类约束多目标优化问题。

说明书

技术领域

本发明公开了一种多目标烟花算法的低碳疫苗冷链优化配送方法，涉及涉及路径规划技术领域。

背景技术

随着计划免疫和常态化防疫工作的深入开展，疫苗的需求量不断攀升，疫苗冷链物流成为现代物流中一个重要的分支。因此，低碳疫苗冷链优化配送已成为亟需解决的一类实际物流应用问题。该问题对固定数量配送车辆进行路径规划，它的成功求解，能使疫苗的冷链配送服务更有秩序、效率更高，及时满足各个地区的疫苗需求，提高当地的人民健康与医疗卫生服务水平。同时有效减少二氧化碳的排放量，改善周围大气环境。

目前，国内外学者已经分别对疫苗的运输策略和配送方式等方面进行了研究。路径规划问题属于NP难题。烟花算法是由北大谭营教授在2010年首次提出的一种元启发式算法。已成功应用于复杂网络关键点集确定、多区域电力系统调度、电能交易等实际问题的求解。传统多目标烟花算法求解物流车辆低碳路线规划未利用不可行解的有用信息和问题启发信息，搜索极为盲目，收敛速度较慢，种群同化严重，产生大量不可行解等不足，综上，提出一种有较好的收敛性和多样性，求解准确且稳定，并具有良好的可扩展性的路线规划方法极为必要。

发明内容

本发明针对上述背景技术中的缺陷，提供一种多目标烟花算法的低碳疫苗冷链优化配送方法，该方法具有较好的收敛性和多样性，求解准确且稳定。

为实现上述目的，本发明采用的技术方案如下：一种多目标烟花算法的低碳疫苗冷链优化配送方法,包括以下步骤：

S1：读取问题输入信息，定义优化目标，设定车辆约束条件；

S2：初始化双档案协同进化型多目标烟花算法参数；

S3：生成初始候选烟花种群POP，采用消除车辆约束条件的解码方式后计算适应度，将烟花种群POP中的可行解加入可行档案Feasible，不可行解加入不可行解档案Infeasible；

S4：对烟花采用部分映射爆炸算子生成爆炸火花，每个烟花根据4种不同的爆炸半径通过部分映射交叉操作产生8个爆炸火花；

S5：对烟花采用两点交换变异算子生成变异火花，对每个烟花编码进行随机的两点交换操作,将爆炸火花和变异火花中的非支配解加入NDS，并将其中的不可行解加入Infeasible；

S6：双外部档案协同进化型机制，对所有不可行解档案Infeasible进行可行性搜索，得到可行性搜索火花FS，其中可行解集为F，不可行解集为I，将I加入Infeasible；对NDS∪F实施目标驱动的启发式扩展搜索，得到扩展搜索火花SS；

S7：用NDS∪SS分别根据Pareto支配概念和ε支配概念更新POP和Feasible中个体的支配关系，若规模超出最大预设值，则根据拥挤距离对烟花种群POP和可行档案Feasible进行裁剪；使用I更新Infeasible；

S8：从POP和Feasible中各随机选择N/2个个体，若Feasible中个体数量小于N/2，则用POP中的个体补充。选择出下一代烟花后，从中随机选择一个个体，计算该个体与其他烟花的相似度，即个体编码中对应位置编号相同的位置个数，将相似度高于80％的个体进行随机长度的循环移位操作；

S9：判断是否达到终止条件，若否，回转执行所述步骤S4，若达到，则终止迭代，输出可行档案Feasible。

进一步的，步骤S1中：所述问题输入信息包括：物流车辆需要访问的客户点数量T和客户具体坐标信息以及客户所需的疫苗数量和时间要求；

所述优化目标包括：考虑碳排放的企业运输成本和客户不满意度最小；

所述车辆约束条件包括：每个客户只能由一辆车服务；对于每个被服务的客户点，一定会有一辆车从某个地点行驶到该客户点，并从该客户点离开；保证每辆车的行驶路线中没有子回路；车辆容量约束，车辆数量约束和模糊时间窗约束。

进一步的，步骤S2中：烟花种群规模为N、最大评价次数为Eva

进一步的，步骤S3中：生成初始候选种群具体包括以下步骤：采用整数编码客户访问序列，均匀随机生成规模为N的烟花种群POP，每个个体表示物流车辆前往客户点送货的顺序：

X＝{x

其中，x

进一步的，根据消除车辆约束的解码方式进行解码，并计算其目标向量具体包括：f

其中，C

其中，t

其中，V

其中：ET

LT

ET

LT

[ET

进一步的，定义约束条件包括以下六个：

(1)每个客户只能由一辆车服务，即：

(2)对于每个被服务的客户点，一定会有一辆车从某个地点行驶到该客户点，并从该客户点离开，即：

(3)经典的子回路消除约束，保证每辆车的行驶路线中没有子回路，即：

其中：S为子回路；

(4)车辆容量约束，即：

其中：Q为运输车辆的最大容量；

(5)车辆数量约束，即：

(6)模糊时间窗约束，即：

ET

进一步的，步骤S3中，所述消除车辆约束条件的解码方式实现步骤如下：

S31，整数编码客户访问序列按车辆容量约束和模糊时间窗约束进行解码；

S32，判断子回路数量，即使用的车辆数是否超过问题可用车辆数，采用一种新型修复算子处理不可行解；

S33，对客户访问序列按车辆容量约束解码后，当子回路数量达到可用车辆数时，将剩余未访问的所有客户放入一个集合中；S32中修复算子为：对该集合依次进行插入操作和置换操作；

S34，若集合变为空集，则该修复操作终止；

S35，若集合无法变为空集，即经插入和置换操作后，仍不能同时满足车辆数量和容量约束，则随机初始化一串访问序列替代原整数编码个体，并重新解码；

S36，输出初始解。

进一步的，步骤S4中，所述烟花采用部分映射爆炸算子生成火花的实现步骤为：

S4，将每个烟花的两个目标值分别进行归一化；再将归一化后的结果相乘，得到N个乘积；

S42，根据第i(i＝1,2,...,N)个乘积在N个乘积中所占的比例来计算第i个烟花需要变化的编号个数；

S43，令每个烟花产生4种爆炸半径不同的爆炸火花，其爆炸半径分别为：

r

其中：r

S44，将编码中的配送中心0删除，得到一串客户的访问序列；随机选取4个其它烟花的客户访问序列，分别与当前烟花进行部分映射交叉操作。

进一步的，步骤S6中，所述双外部档案协同进化型机制，具体实现步骤如下：

S61，设置了可行解档案和不可行解档案两个不重叠的外部档案，分别保存可行解和不可行解中的精英个体；

S62，对不可行解档案实施可行性搜索，可能生成新的可行解和新的不可行解；

S63，可行性搜索策略对某个配送方案中时间窗约束违反程度最大的子回路，按客户可接受到达时间的先后进行排序，所得新的配送方案称为可行性搜索火花FS；

S64，对于不可行解档案经可行性搜索后产生的可行解，将其与子代中的非支配个体利用碳排放量和客户不满意度两种信息共同进行启发式扩展搜索。

有益效果：

(1)本发明建立了低碳疫苗冷链配送问题的约束多目标优化模型；该模型以企业运输成本和平均客户不满意度作为优化目标，同时包含可用车数量约束、车辆容量约束和模糊时间窗约束，更贴合实际应用。

(2)本发明采用一种基于双档案协同进化多目标烟花算法的低碳疫苗冷链优化配送方法，消除车辆约束的解码方式，使得解码后的解大部分为可行解或仅违反时间窗约束的解，避免大量不可行解对搜索进程的干扰，促使该算法的性能优于传统的烟花算法。

(3)本发明部分映射爆炸算子能够增强对局部区域的搜索，更好地实现全局搜索和局部搜索之间的平衡，提高算法的求解精度。

(4)本发明采用双外部档案协同进化机制，保留寻优过程中产生的约束违反程度较小的不可行解。利用可行性搜索产生的可行解辅助可行解档案进行寻优，同时利用可行性搜索产生的不可行解更新不可行解档案，引导其逐渐向可行域移动，不可行解中的有用信息因此得以利用，提高了算法的求解效率。

(5)本发明对不可行解档案进行可行性搜索的策略，消除或降低了个体对模糊时间窗约束的违反程度，有利于加速生成质量更高的可行解。

附图说明

图1为双档案协同进化型多目标烟花算法流程图；

图2为双外部档案协同进化机制示意图；

图3为本发明IGD的收敛曲线；

图4为本发明HV的收敛曲线。

具体实施方式

下面结合附图对技术方案的实施作进一步的详细描述。以下实施例仅用于更加清楚地说明本发明的技术方案，而不能以此来限制本发明的保护范围。

如图1～2所示的一种实施例：

在一个医院数量为20的低碳疫苗冷链配送问题中，每个医院(编号1～20)位置坐标、配送中心(编号为0)的位置坐标、每个医院的需求量、相应时间窗限制和服务时间信息如表1所示：

表1配送中心和各医院的详细信息

由于实际生活中配送车辆资源有限，因此需要根据所有医院的总需求量和车辆的最大容量来提前估算此次配送任务的最大可用车辆数K：

其中，μ表示配送任务难度，本章实验中设置μ＝0.5。

使用本发明提出的双档案协同进化型多目标烟花算法求解仿真实例得到的最佳路线规划方案，具体步骤如下：

(1)初始化。读取实例的输入信息，包括访问客户坐标信息和问题规模T；给出优化目标的定义，并设定约束条件。

优化目标为考虑碳排放的企业运输成本和客户不满意度最小，它定义为：

其中，V

定义约束条件包括以下六个：

1.每个客户只能由一辆车服务，即：

2.对于每个被服务的客户点，一定会有一辆车从某个地点行驶到该客户点，并从该客户点离开，即：

3.经典的子回路消除约束，保证每辆车的行驶路线中没有子回路，即：

4.车辆容量约束，即：

5.车辆数量约束，即：

6.模糊时间窗约束，即：

ET

(2)初始化双档案协同进化型多目标烟花算法参数：

设置双档案协同进化型多目标烟花算法进化种群规模为N＝10、可行解档案和不可行解档案的最大规模设置为100点、相似度阈值K＝0.8、最大评价次数Eva

(3)生成初始候选种群，采用消除车辆约束的解码方式后计算适应度：

采用整数编码，均匀随机生成规模为N的烟花种群POP，每个个体表示物流车辆前往客户点送货的顺序：

X＝{x

其中，x

对整数编码序列按车辆容量约束和模糊时间窗约束进行解码，采用一种新型修复算子处理不可行解，具体实现如下；

1.整数编码客户访问序列按车辆容量约束和模糊时间窗约束进行解码；

2.判断子回路数量即使用的车辆数是否超过问题可用车辆数，采用一种新型修复算子；

3.对客户访问序列按车辆容量约束解码后，当子回路数量达到可用车辆数时，将剩余未访问的所有客户放入一个集合中。上述修复算子：为对该集合依次进行插入操作和置换操作；

4.若集合变为空集，则该修复操作终止；

5.若集合无法变为空集，即经插入和置换操作后，仍不能同时满足车辆数量和容量约束，则随机初始化一串访问序列替代原整数编码个体，并重新解码；

6.输出初始解。

根据步骤(1)计算目标向量。

(4)采用部分映射爆炸算子生成火花：

1.将每个烟花的两个目标值分别进行归一化；再将归一化后的结果相乘，得到N个乘积；

2.根据第i(i＝1,2,...,N)个乘积在N个乘积中所占的比例来计算第i个烟花需要变化的编号个数；

3.令每个烟花产生4种爆炸半径不同的爆炸火花，其爆炸半径分别为：

r

4.将编码中的配送中心0删除，得到一串客户的访问序列。随机选取4个其它烟花的客户访问序列，分别与当前烟花进行部分映射交叉操作。

(5)变异算子：

对每个烟花编码进行随机的两点交换操作。

(6)双外部档案协同进化机制：

1.设置了可行解档案和不可行解档案两个不重叠的外部档案，分别保存可行解和不可行解中的精英个体；

2.对不可行解档案实施可行性搜索，可能生成新的可行解和不可行解；

3.可行性搜索策略对某个配送方案中时间窗约束违反程度最大的子回路，按客户可接受到达时间的先后进行排序，所得新的配送方案称为可行性搜索火花；

4.对于不可行解档案经可行性搜索后产生的可行解，将其与子代中的非支配个体利用碳排放量和客户不满意度两种信息共同进行启发式扩展搜索。

(7)更新种群：

分别根据Pareto支配概念和ε支配概念更新POP和Feasible，若规模超出最大预设值，则根据拥挤距离对POP和Feasible进行裁剪。使用I更新Infeasible。

(8)选择策略：

从POP和Feasible中各随机选择N/2个个体，若Feasible中个体数量小于N/2，则用POP中的个体补充。在选出的烟花种群中随机选择一个个体，计算该个体与其他烟花的相似度，即个体编码中对应位置编号相同的位置个数。将相似度高于80％的个体进行随机长度的循环移位操作。

本发明的效果可以通过以下仿真实验进一步说明：

1.实验条件：

在Intel(R)Core(TM)i5-10210U CPU@1.60GHz，运行内存为12G的计算机上采用MATLAB R2019a软件运行。

2.实验内容：

选取医院数量为20的低碳疫苗冷链配送问题，相关信息和参数设置如上述表1和下述表2所示。

表2

3.实验结果

i.采用本发明与现有的求解带时间窗约束VRP的算法(HMOEA、hybrid DEalgorithm和MOEA-FCS)进行实验对比；

ii.采用本发明双档案协同进化型多目标烟花算法与现有的多目标烟花算法(S-DMOFWA)分别对该问题进行求解。

实验在实例中分别独立地运行30次。表2分别列出了对比算法与双档案协同进化多目标烟花算法在IGD和HV上的平均值和标准差。双档案协同进化多目标烟花算法在仿真实例上的IGD和HV值均显著优于4种对比算法。上述实验结果表明，双档案协同进化多目标烟花算法能够搜索到收敛精度更高、分布更加宽广、支配的目标空间体积更大的Pareto最优前沿，且算法的求解稳定性。

图3为本发明IGD的收敛曲线，图4为本发明HV的收敛曲线。每500次目标评价次数对IGD和HV值进行一次采样，因此在一个收敛曲线中共有100个数据点。从收敛曲线可以看出双档案协同进化多目标烟花算法的IGD和HV收敛精度均高于对比算法，收敛速度也较快。由于采用有效的约束处理机制，充分利用可行解和不可行解中的重要进化信息，使得可行解档案和不可行解档案不断更新和进化。同时，变异算子使得它具备一定的跳出局部最优的能力。因此，能够在前期和中期以较快的速度收敛到精度较高的近似Pareto最优前沿，并在后期保持稳定，具有更好的收敛性和多样性。

综上，本发明提出的基于双档案协同进化型多目标烟花算法的低碳疫苗冷链优化配送路线规划方法，在多目标的车辆路线规划基础上，建立了考虑碳排放的企业运输成本和客户不满意度的数学模型。通过消除车辆约束的解码方式，将问题转化为仅带有模糊时间窗约束的问题，降低了其求解难度。部分映射爆炸算子生成分布较为均匀的爆炸火花，实现了对烟花周围局部区域的精细搜索，提高了算法的收敛性。利用可行性搜索产生的不可行解更新不可行解档案，保留约束违反程度较小的个体，提高了不可行解转化为可行解的概率。同时，对不可行解档案进行可行性搜索后，使产生的可行解参与可行解档案中目标驱动的启发式扩展搜索，既能增加解的多样性，又能强化算法对于当前Pareto前沿附近区域的局部搜索，使得算法的求解精度得到提高。所提算法在每次求解过程中都能对整个可行域进行充分的探索和利用，同时挖掘不可行解的有用信息，使算法尽可能找到更多的可行非支配解。因此，能够高效稳定地实现冷链运输中的低碳路线规划。

在本公开中参照附图来描述本发明的各方面，附图中示出了许多说明的实例。本公开的实例不必定义在包括本发明的所有方面。应当理解，上面介绍的多种构思和实例，可以以很多方式中任意一种来实施，这是因为本发明所公开的构思和实例并不限于任何实施方式。另外，本发明公开的一些方面可以单独使用，或者与本发明公开的其他方面的任何适当组合来使用。

虽然本发明已以较佳实施例揭露如上，然其并非用以限定本发明。本发明所属技术领域中具有通常知识者，在不脱离本发明的精神和范围内，当可作各种的更动与润饰。因此，本发明的保护范围当视权利要求书所界定者为准。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明技术原理的前提下，还可以做出若干改进和变形，这些改进和变形也应视为本发明的保护范围。