一种基于变邻域离散混合蛙跳算法的货位分配优化方法与流程

1.本发明涉及货位分配技术领域，具体而言，涉及一种基于变邻域离散混合蛙跳算法的货位分配优化方法。


背景技术：

2.随着社会经济和自动化技术的快速发展，许多企业为了节约用工、用地成本和提高自身的生产效率，在仓储环节使用自动化、信息化程度高和存储空间更合理的自动化立体仓库。货位分配是自动化立体仓库运行流程中的重要一环，货位分配是指根据货物的自身属性和相应的分配目标，为入库货物分配合理的摆放位置。合理的货位分配目标能够起到提高货物出入库效率和货架的整体稳定性等作用，继而加快企业对订单的响应速度，降低运营成本，实现更高的经济效益。
3.针对货位分配这一组合优化问题，许多研究人员建立了各种优化目标的数学模型并对其进行优化计算，而在货物相关性的数学模型上，未对货架的排坐标作优化处理，造成分配结果将同类货物分配在不同巷道的相邻的货架上，导致货物分布情况较为分散，不利于后期堆垛机取货的分工，也不利于工作人员对相应货物的盘点工作。在求解货物出入库效率、货架稳定性和货物相关性多目标货位分配问题的算法上，较多的研究人员使用遗传算法或改进的遗传算法。针对收敛速度较慢、计算结果质量和稳定性较差的带精英保留策略的改进遗传算法，本发明提出一种变邻域离散混合蛙跳算法。


技术实现要素：

4.基于此，为了解决背景技术所提出的问题，本发明提供了一种基于变邻域离散混合蛙跳算法的货位分配优化方法，其具体技术方案如下：
5.一种基于变邻域离散混合蛙跳算法的货位分配优化方法，其特征在于，所述方法包括如下步骤：
6.s1，定义仓库中货架以及存取货物设备的参数；
7.s2，根据货物出入库效率、货架稳定性以及货物相关性建立多目标数学模型；
8.s3，通过随机整数排列的编码方式初始化青蛙种群并计算各青蛙个体的目标函数值；
9.s4，对每只青蛙个体进行两种分别为单点交换操作、片段交换操作的变邻域搜索操作；
10.s5，对青蛙种群根据其目标函数值进行升序排列，并根据公式yk＝[u(j)k,f(j)k|u(j)k＝u(k+q(j-1)),f(j)k＝f(k+q(j-1))]划分q个模因组，其中j＝1,
…
,p,k＝1,
…
,q；
[0011]
s6，利用公式使每个模因组中的最差青蛙个体p
worst
，向模因组中最优青蛙个体p
best
学习更新，若更新后的青蛙个
体p
′
worst
的目标函数值优于更新前青蛙个体p
worst
的目标函数值，则使用p
′
worst
替代p
worst
；否则该最差青蛙个体p
worst
向全局即种群最优青蛙个体g
best
学习更新，若更新后的青蛙个体p
′
worst
的目标函数值优于更新前青蛙个体p
worst
的目标函数值，则使用p
′
worst
替代p
worst
，否则随机生成一只青蛙p
rand
替代p
worst
；
[0012]
若达到最大迭代次数maxgen，输出全局最优青蛙个体并解码，否则返回s3。
[0013]
进一步地，在步骤s1中，定义仓库中货架以及存取货物设备的参数的具体方法包括如下步骤：
[0014]
s10，假设仓库中有x排货架，每排货架有y列和z层，则在货位上的货物坐标可表示为(x,y,z)，其中1≤x≤x，1≤y≤y，1≤z≤z，且x，y，z为正整数；
[0015]
s11，假设每排货架的出入库口坐标为(x,0,0)，货架的长宽高均为l0，巷道宽度为l，vy和vz分别为堆垛机在巷道内水平方向的平均速度和垂直方向的平均速度。
[0016]
进一步地，在步骤s2中，货物出入库效率的数学模型为进一步地，在步骤s2中，货物出入库效率的数学模型为
[0017]
其中，n为货物的个数，yi和zi分别为第i个货物的列坐标和层坐标，pi为第i个货物的出入库频率。
[0018]
进一步地，在步骤s2中，货架稳定性数学模型：
[0019]
其中，qi为第i个货物的重量。
[0020]
进一步地，在步骤s2中，货物相关性数学模型：
[0021]
s为货物的类别总数，ni为第i类货物的总数，x
ij
、y
ij
和z
ij
分别表示第i类的第j个货物的排坐标、列坐标和层坐标，且其中ri(x)、ri(y)和ri(z)分别表示为第i类货物中心坐标的排坐标、列坐标和层坐标，r(x)、r(y)和r(z)分别为所有类别货物中心坐标的排坐标、列坐标和层坐标。
[0022]
进一步地，在步骤s2中，根据货物出入库效率、货架稳定性以及货物相关性建立多目标数学模型的具体方法还包括如下步骤：
[0023]
通过权重系数w线性加权对三个优化目标进行线性化，采用归一化操作消除不同优化目标量纲的影响，建立多目标货位分配优化模型
[0024]
其中，w1∈[0,1]，w2∈[0,1]，w3∈[0,1],w1+w2+w3＝1。
[0025]
进一步地，ri(x)、ri(y)和ri(z)的表达式分别为(z)的表达式分别为和
[0026]
进一步地，r(x)、r(y)和r(z)的表达式分别为进一步地，r(x)、r(y)和r(z)的表达式分别为
和
[0027]
进一步地，本发明提供一种计算机可读存储介质，其存储有计算机程序，当所述计算机程序被处理器执行时实现所述的基于变邻域离散混合蛙跳算法的货位分配优化方法。
[0028]
与现有技术相比，本发明提出的一种基于变邻域离散混合蛙跳算法的货位分配优化方法具有以下优点：
[0029]
1.所述的一种基于变邻域离散混合蛙跳算法的货位分配优化方法，在较大规模入库货物数量的情况下，针对求解货物出入库效率、货架稳定性和货物相关性的多目标货位分配模型，其中改进的货物相关性模型有利于堆垛机取货的分工及有利于工作人员对相应类别货物的盘点工作，该优化方法具有快速的收敛速度、高质量的解和稳定的计算结果。
[0030]
2.所述的一种基于变邻域离散混合蛙跳算法的货位分配优化方法，通过计算出符合多目标货位分配模型高质量的解，可以达到提高自动化立体仓库的运行效率和货架稳定性等目的，从而提高企业的经济效益和降低运营成本。
附图说明
[0031]
从以下结合附图的描述可以进一步理解本发明。图中的部件不一定按比例绘制，而是将重点放在示出实施例的原理上。在不同的视图中，相同的附图标记指定对应的部分。
[0032]
图1是本发明一实施例中一种基于变邻域离散混合蛙跳算法的货位分配优化方法的整体流程示意图；
[0033]
图2是本发明一实施例中随机整数排列的编码方式流程示意图；
[0034]
图3是本发明一实施例中单点交换操作流程示意图；
[0035]
图4是本发明一实施例中片段交换操作流程示意图；
[0036]
图5是本发明一实施例中变邻域搜索操作流程示意图；
[0037]
图6是本发明一实施例中学习更新机制流程示意图；
[0038]
图7是本发明一实施例中对同一巷道相邻货架的排坐标进行同化处理和加入敏感系数操作前后货物分布对比图；
[0039]
图8是本发明一实施例中变邻域离散混合蛙跳算法优化前后的货物分布对比图；
[0040]
图9是本发明一实施例中目标函数值迭代曲线示意图。
具体实施方式
[0041]
为了使得本发明的目的、技术方案及优点更加清楚明白，以下结合其实施例，对本发明进行进一步详细说明。应当理解的是，此处所描述的具体实施方式仅用以解释本发明，并不限定本发明的保护范围。
[0042]
需要说明的是，当元件被称为“固定于”另一个元件，它可以直接在另一个元件上或者也可以存在居中的元件。当一个元件被认为是“连接”另一个元件，它可以是直接连接到另一个元件或者可能同时存在居中元件。本文所使用的术语“垂直的”、“水平的”、“左”、“右”以及类似的表述只是为了说明的目的，并不表示是唯一的实施方式。
[0043]
除非另有定义，本文所使用的所有的技术和科学术语与属于本发明的技术领域的技术人员通常理解的含义相同。本文中在本发明的说明书中所使用的术语只是为了描述具
体的实施方式的目的，不是旨在于限制本发明。本文所使用的术语“及/或”包括一个或多个相关的所列项目的任意的和所有的组合。
[0044]
本发明中所述“第一”、“第二”不代表具体的数量及顺序，仅仅是用于名称的区分。
[0045]
如图1所示，本发明一实施例中的一种基于变邻域离散混合蛙跳算法的货位分配优化方法，其如下步骤：
[0046]
s1，定义仓库中货架以及存取货物设备的参数。
[0047]
s2，根据货物出入库效率、货架稳定性以及货物相关性建立多目标数学模型。
[0048]
s3，通过随机整数排列的编码方式初始化青蛙种群并计算各青蛙个体的目标函数值。
[0049]
s4，对每只青蛙个体进行两种分别为单点交换操作、片段交换操作的变邻域搜索操作。
[0050]
s5，如图5所示，对青蛙种群根据其目标函数值进行升序排列，并根据公式yk＝[u(j)k,f(j)k|u(j)k＝u(k+q(j-1)),f(j)k＝f(k+q(j-1))]划分q个模因组，其中j＝1,
…
,p,k＝1,
…
,q。其中，p为每个模因组中青蛙个体的数量，q为模因组的数量。
[0051]
s6，利用学习更新公式使每个模因组中的最差青蛙个体p
worst
，向模因组中最优青蛙个体p
best
学习更新，若更新后的青蛙个体p
′
worst
的目标函数值优于更新前青蛙个体p
worst
的目标函数值，则使用p
′
worst
替代p
worst
；否则该最差青蛙个体p
worst
向全局即种群最优青蛙个体g
best
学习更新，若更新后的青蛙个体p
′
worst
的目标函数值优于更新前青蛙个体p
worst
的目标函数值，则使用p
′
worst
替代p
worst
，否则随机生成一只青蛙p
rand
替代p
worst
；若达到最大迭代次数maxgen，输出全局最优青蛙个体并解码，否则返回s3。
[0052]
具体而言，在步骤s1中，定义仓库中货架以及存取货物设备的参数的具体方法包括如下步骤：
[0053]
s10，假设仓库中有x排货架，每排货架有y列和z层，则在货位上的货物坐标可表示为(x,y,z)，其中1≤x≤x，1≤y≤y，1≤z≤z，且x，y，z为正整数；
[0054]
s11，假设每排货架的出入库口坐标为(x,0,0)，货架的长宽高均为l0，巷道宽度为l，vy和vz分别为堆垛机在巷道内水平方向的平均速度和垂直方向的平均速度。
[0055]
在步骤s2中，货物出入库效率的数学模型为
[0056]
其中，n为货物的个数，yi和zi分别为第i个货物的列坐标和层坐标，pi为第i个货物的出入库频率。
[0057]
在步骤s2中，货架稳定性数学模型：
[0058]
其中，qi为第i个货物的重量。
[0059]
在步骤s2中，货物相关性数学模型：
[0060]
其中，s为货物的类别总数，ni为第i类货物的总数，x
ij
、y
ij
和z
ij
分别表示第i类的第j个货物的排坐标、列坐标和层坐标，且其中为对同一巷道相邻货架的排坐标进行同化处理和加入敏感系数操作，ri(x)、ri(y)和ri(z)分别表示为第i类货物中心坐标的排坐标、列坐标和层坐标，r(x)、r(y)和r(z)分别为所有类别货物中心坐标的排坐标、列坐标和层坐标。
[0061]
在步骤s2中，根据货物出入库效率、货架稳定性以及货物相关性建立多目标数学模型的具体方法还包括如下步骤：
[0062]
通过权重系数w线性加权对三个优化目标进行线性化，采用归一化操作消除不同优化目标量纲的影响，建立多目标货位分配优化模型
[0063]
其中，w1∈[0,1]，w2∈[0,1]，w3∈[0,1],w1+w2+w3＝1。
[0064]ri
(x)、ri(y)和ri(z)的表达式分别为和
[0065]
r(x)、r(y)和r(z)的表达式分别为和
[0066]
与现有技术相比，本发明提出的一种基于变邻域离散混合蛙跳算法的货位分配优化方法具有以下优点：
[0067]
1.所述的一种基于变邻域离散混合蛙跳算法的货位分配优化方法，在较大规模入库货物数量的情况下，针对求解货物出入库效率、货架稳定性和货物相关性的多目标货位分配模型，其中改进的货物相关性模型有利于堆垛机取货的分工及有利于工作人员对相应类别货物的盘点工作，该优化方法具有快速的收敛速度、高质量的解和稳定的计算结果。
[0068]
2.所述的一种基于变邻域离散混合蛙跳算法的货位分配优化方法，通过计算出符合多目标货位分配模型高质量的解，可以达到提高自动化立体仓库的运行效率和货架稳定性等目的，从而提高企业的经济效益和降低运营成本。
[0069]
在其中一个实施例中，通过随机整数排列的编码方式初始化青蛙种群并计算各青蛙个体的目标函数值。所述的随机整数排列的编码方式如图2所示，其长度为x*y*z，代表一只青蛙个体，每个整数元素m映射一个货位坐标(x,y,z)，其映射关系公式为f(x,y,z)＝(x-1)*x*y+(y-1)*z+z＝m。
[0070]
对每只青蛙个体进行两种分别为单点交换操作、片段交换操作的变邻域搜索操作。所述的单点交换操作指在青蛙个体中随机选择两个位置不相同的元素，将两个位置中的元素互相交换；所述的片段交换操作指在青蛙个体中随机选择两段位置不相同的元素，其中两段元素数量相同，元素数量优选为3-6个，将两个片段中的元素互相交换。
[0071]
由于入库货物数量小于或等于货位数量，即货物编码长度会出现与青蛙个体编码长度存在不一致的情况，且货物编码中的各货物以左对齐的方式放入青蛙个体编码中对应位置的货位中，再从青蛙个体编码中截取前n个元素以计算目标函数值，因此所述的单点交
换操作、片段交换操作在选择的两个位置中，至少有一个在青蛙个体编码前n个位置中。所述的单点交换操作、片段交换操作示意图分别如图3和图4。
[0072]
如图5所示，变邻域搜索操作的具体流程，首先执行单点交换操作，若交换后的青蛙个体p
′
的目标函数值优于原青蛙个体p的目标函数值，则使用p
′
替代p，且继续执行单点交换操作；否则执行片段交换操作，若交换后的青蛙个体p
′
的目标函数值优于原青蛙个体p的目标函数值，则使用p
′
替代p，且继续执行片段交换操作，否则结束一次变邻域搜索操作循环。变邻域搜索操作流程如图6所示。
[0073]
所述的学习更新公式中的指全局或模因组中最优青蛙个体编码元素与模因组中最差青蛙个体编码对应位置元素不相同的个数乘以一个0-1之间的随机数并取整；所述的公式指g
best
/p
best
个体的前step个与p
worst
个体元素不同位置的元素依次替换p
worst
的前step个元素不同位置的元素，在每个位置的元素替换后，p
worst
青蛙个体中与替换位置元素重复的元素，更改为对应位置替换前的元素，图7为学习更新机制示意图。
[0074]
在其中一个实施例中，本发明还提供一种计算机可读存储介质，其存储有计算机程序，当所述计算机程序被处理器执行时实现所述的基于变邻域离散混合蛙跳算法的货位分配优化方法。
[0075]
本发明结合自动化立体仓库具体实施示例进行实验分析，其包括如下内容：
[0076]
(1)定义仓库中货架、存取货物设备的参数：仓库中有10排货架，每排货架有10列和8层，货架的长宽高均为1.2米，巷道宽度为2米，堆垛机在巷道内水平方向的平均速度和垂直方向的平均速度均为1.2m/s。
[0077]
(2)货物信息：本实施示例的货物数量总共为400个，其中货物出入库频率为0.1-0.9，货物重量为10kg-100kg，1-5类的货物数量均为70个，第6类货物数量为50个。
[0078]
(3)精英保留策略的改进遗传算法(ga)和变邻域离散混合蛙跳算法(dsfla)的参数如表1所示:
[0079][0080]
表1
[0081]
(4)首先，通过变邻域离散混合蛙跳算法(dsfla)迭代1500次，对同一巷道相邻货架的排坐标进行同化处理和加入敏感系数操作前后的单目标模型求解，以验证模型的有效性，操作前后对比图如图7所示，其中不同颜色代表不同类型的货物。由所示图7可知，操作后同类货物被分配在同一巷道相邻两排的货架上，且分布更加紧凑，更有利于堆垛机取货的分工和工作人员对相应类别货物的盘点工作。
[0082]
(5)然后，使用带精英保留策略的改进遗传算法(ga)和变邻域离散混合蛙跳算法(dsfla)对多目标货位分配优化模型f求解，其中w1＝0.5，w2＝0.3，w3＝0.2，迭代次数为
3000次，变邻域离散混合蛙跳算法(dsfla)优化前后的货物分布图如图8所示，其中深灰色、灰色和黑色分别代表0.6《p、0.3≤p≤0.6和p＜0.3的货物出入库频率，目标函数值迭代曲线如图9所示，对多目标货位分配优化模型求解15次，取多目标货位分配优化模型最优函数值f的平均值及其对应的f1、f2和f3函数值的平均值，相关数据如表2所示。两个算法求解多目标货位分配优化模型最优函数值f的标准差及其对应的f1、f2和f3函数值的标准差如表3所示。
[0083][0084]
表2
[0085][0086][0087]
表3
[0088]
(6)从优化后货物分布图可以看出，货物分布紧密有致，符合多目标货位分配优化模型的优化方向；从图8、表2和表3可以看出，变邻域离散混合蛙跳算法具有更快的收敛速度，计算优化结果的质量和稳定性更高。
[0089]
(7)综上，通过示例实验分析，验证了本发明模型和算法的有效性，能够有效解决自动化立体仓库较大规模入库货物的货位分配优化问题，达到提高自动化立体仓库的运行效率和货架稳定性等目的，从而提高企业的经济效益和降低运营成本。
[0090]
以上所述实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。
[0091]
以上所述实施例仅表达了本发明的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对发明专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干变形和改进，这些都属于本发明的保护范围。因此，本发明专利的保护范围应以所附权利要求为准。

技术特征：
1.一种基于变邻域离散混合蛙跳算法的货位分配优化方法，其特征在于，所述方法包括如下步骤：s1，定义仓库中货架以及存取货物设备的参数；s2，根据货物出入库效率、货架稳定性以及货物相关性建立多目标数学模型；s3，通过随机整数排列的编码方式初始化青蛙种群并计算各青蛙个体的目标函数值；s4，对每只青蛙个体进行两种分别为单点交换操作、片段交换操作的变邻域搜索操作；s5，对青蛙种群根据其目标函数值进行升序排列，并根据公式y
k
＝[u(j)
k
,f(j)
k
|u(j)
k
＝u(k+m(j-1)),f(j)
k
＝f(k+m(j-1))]划分模因组，其中j＝1,
…
,p,k＝1,
…
,q；s6，利用学习更新公式使每个模因组中的最差青蛙个体p
worst
向模因组中最优青蛙个体p
best
学习更新，若更新后的青蛙个体p
′
worst
的目标函数值优于更新前青蛙个体p
worst
的目标函数值，则使用p
′
worst
替代p
worst
，否则所述最差青蛙个体p
worst
向种群最优青蛙个体g
best
学习更新，若更新后的青蛙个体p
′
worst
的目标函数值优于更新前青蛙个体p
worst
的目标函数值，则使用p
′
worst
替代p
worst
，否则随机生成一只青蛙p
rand
替代p
worst
；若达到最大迭代次数maxgen，输出全局最优青蛙个体并解码，否则返回s3。2.如权利要求1所述的一种基于变邻域离散混合蛙跳算法的货位分配优化方法，其特征在于，在步骤s1中，定义仓库中货架以及存取货物设备的参数的具体方法包括如下步骤：s10，假设仓库中有x排货架，每排货架有y列和z层，则在货位上的货物坐标可表示为(x,y,z)，其中1≤x≤x，1≤y≤y，1≤z≤z，且x，y，z为正整数；s11，假设每排货架的出入库口坐标为(x,0,0)，货架的边长均为l0，巷道宽度为l，v
y
和v
z
分别为堆垛机在巷道内水平方向的平均速度和垂直方向的平均速度。3.如权利要求2所述的一种基于变邻域离散混合蛙跳算法的货位分配优化方法，其特征在于，在步骤s2中，货物出入库效率的数学模型为其中，n为货物的个数，y
i
和z
i
分别为第i个货物的列坐标和层坐标，p
i
为第i个货物的出入库频率。4.如权利要求3所述的一种基于变邻域离散混合蛙跳算法的货位分配优化方法，其特征在于，在步骤s2中，货架稳定性数学模型：征在于，在步骤s2中，货架稳定性数学模型：其中，q
i
为第i个货物的重量。5.如权利要求4所述的一种基于变邻域离散混合蛙跳算法的货位分配优化方法，其特征在于，在步骤s2中，货物相关性数学模型：征在于，在步骤s2中，货物相关性数学模型：s为货物的类别总数，n
i
为第i类货物的总数，x
ij
、y
ij
和z
ij
分别表示第i类的第j个货物的
排坐标、列坐标和层坐标，r
i
(x)、r
i
(y)和r
i
(z)分别表示为第i类货物中心坐标的排坐标、列坐标和层坐标，r(x)、r(y)和r(z)分别为所有类别货物中心坐标的排坐标、列坐标和层坐标。6.如权利要求5所述的一种基于变邻域离散混合蛙跳算法的货位分配优化方法，其特征在于，在步骤s2中，根据货物出入库效率、货架稳定性以及货物相关性建立多目标数学模型的具体方法还包括如下步骤：通过权重系数w线性加权对三个优化目标进行线性化，采用归一化操作消除不同优化目标量纲的影响，建立多目标货位分配优化模型其中，w1∈[0,1]，w2∈[0,1]，w3∈[0,1],w1+w2+w3＝1。7.如权利要求6所述的一种基于变邻域离散混合蛙跳算法的货位分配优化方法，其特征在于，r
i
(x)、r
i
(y)和r
i
(z)的表达式分别为(z)的表达式分别为以及8.如权利要求7所述的一种基于变邻域离散混合蛙跳算法的货位分配优化方法，其特征在于，r(x)、r(y)和r(z)的表达式分别为征在于，r(x)、r(y)和r(z)的表达式分别为以及9.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质存储有计算机程序，当所述计算机程序被处理器执行时实现如权利要求1-8任一项所述的基于变邻域离散混合蛙跳算法的货位分配优化方法。

技术总结
本发明提供了一种基于变邻域离散混合蛙跳算法的货位分配优化方法，其包括如下步骤：定义仓库中货架以及存取货物设备的参数；根据货物出入库效率、货架稳定性以及货物相关性建立多目标数学模型；通过随机整数排列的编码方式初始化青蛙种群并计算各青蛙个体的目标函数值；对每只青蛙个体进行两种分别为单点交换操作、片段交换操作的变邻域搜索操作；对青蛙种群根据其目标函数值进行升序排列并划分模因组，使每个模因组中的最差青蛙个体向模因组中最优青蛙个体学习更新，若达到最大迭代次数，输出全局最优青蛙个体并解码。本发明通过计算出符合多目标货位分配模型高质量的解，可以达到提高自动化立体仓库的运行效率和货架稳定性等目的。稳定性等目的。稳定性等目的。


技术研发人员：王凯 叶胜挺 曾中荣 卢泽坚 杜俊文
受保护的技术使用者：广东世创金属科技股份有限公司
技术研发日：2023.03.29
技术公布日：2023/7/25