1.本发明涉及智慧园区技术领域，尤其涉及一种基于拣货动线模型的卷烟成品智慧园区管控方法。
背景技术：2.随着物联网技术的飞速发展，互联网加的形式已应用到社会的各行各业，在为人类带来便利与企业管控等多方面，显示出了极大的应用效果。
3.越来越多的烟草企业通过建设智慧园区以提高工作效率，规范作业要求，实现合理化、人性化、及科学化的园区管控。
4.由于卷烟园区的管控涉及动态货物分配、拣货动线规划、仓库多目标理货、车辆装卸货等多个作业场景，只有建立多种模型及算法才能切实解决园区管控的核心问题。
5.目前成品卷烟(物料)的订单拣选路径规划仅针对单工作人员展开，在实际拣选过程中易造成巷道阻塞，园区内物流车辆作业过程中存在的耗时长，规划合理性差，效率低下，装卸记录准确性低，仓库内货物结构不清晰，辅助工具利用率低，无法实现智能化自动化分析预测等问题。
6.因此，亟需一种基于拣货动线模型的卷烟成品智慧园区管控方法。
技术实现要素：7.本发明的目的是提供一种基于拣货动线模型的卷烟成品智慧园区管控方法，以解决上述现有技术中的问题，能够降低企业内部运营成本，提高交货效率。
8.本发明提供了一种基于拣货动线模型的卷烟成品智慧园区管控方法，其中，包括：
9.构建以拣货时间和拣货路径最短为优化目标的拣货动线模型；
10.基于混沌理论策略改进的快速扩展随机树路径规划算法，对所述拣货动线模型进行求解。
11.如上所述的基于拣货动线模型的卷烟成品智慧园区管控方法，其中，优选的是，所述构建以拣货时间和拣货路径最短为优化目标的拣货动线模型，具体包括：
12.获取园区仓库数据、园区构造数据和资源数据；
13.根据所述园区的仓库数据、所述园区构造数据及所述资源数据，构建拣货动线路径优化模型。
14.如上所述的基于拣货动线模型的卷烟成品智慧园区管控方法，其中，优选的是，所述根据所述园区的仓库数据、所述园区构造数据及所述资源数据，构建拣货动线路径优化模型，具体包括：
15.将卷烟成品仓库分为k＝{k1,k2,...,kn}个存储单位，每个单位存储相同类别的卷烟成品，ki表示第i个储存单位，每个储存单位的容量ci；在正常的仓库经营情况下，同一时间可能出现一人拣多货，多人拣多货的情况，一个人的拣货容量为gi；在工作周期内，存在p＝{p1,p2,...,pn}个订单，pj为第j个订单；
16.拣货任务中，仓库采用多层货架，各存储单位间的距离由水平距离xi与垂直距离yi组成，通过以下公式计算任意两存储单位间的距离：
17.k
i,i+1
＝|x
i+1-xi|+|y
i+1-yi|
ꢀꢀꢀ
(1)
18.单个工作人员及其辅助工具在进行拣货时，满足以下公式的最大化原则，以提高拣货效率，节约人力成本：
[0019][0020][0021]
基于忽略各作业人员间的速度差异，均为v的假设，则通过以下公式计算单个工人通过拣货路径的时间ti：
[0022]
ti＝k
i,i+1
/v
ꢀꢀꢀ
(4)；
[0023]
在整个拣货周期中，单个工人在仓库内拣选时间ati和订单拣选完成后的整理打包所花费的时间bti满足以下公式：
[0024][0025]
确定卷烟成品仓库拣货动线模型的双目标函数如下式：
[0026]
f(x)＝|x
i+1-xi|+|y
i+1-yi|
ꢀꢀ
(7)
[0027][0028]
采用ahp法，通过以下公式确定两目标函数的权重：
[0029][0030][0031]
ω＝ωm+ωn/2
ꢀꢀꢀ
(11)；
[0032]
根据两目标函数的权重，构建拣货动线的目标函数为：
[0033]
minf(x)＝ω1f(x)+ω2g(x)
ꢀꢀꢀ
(12)。
[0034]
如上所述的基于拣货动线模型的卷烟成品智慧园区管控方法，其中，优选的是，所述基于混沌理论策略改进的快速扩展随机树路径规划算法，对所述拣货动线模型进行求解，具体包括：
[0035]
在随机步长路径上随机生成节点，并执行剪枝处理；
[0036]
引入logistic映射参数和混沌变量，得到新节点和新路径，并加入扩展树；
[0037]
判断是否达到最大迭代次数；
[0038]
若达到最大迭代次数，则采用基于levy飞行策略的混合差分乌鸦搜索算法，对所述拣货动线模型进行求解；
[0039]
若未达到最大迭代次数，则返回生成随机步长的步骤，直到迭代至最大。
[0040]
如上所述的基于拣货动线模型的卷烟成品智慧园区管控方法，其中，优选的是，所述在随机步长路径上随机生成节点，并执行剪枝处理，具体包括：
[0041]
初始化地形，设定起始点、目标点和拣货任务参数；
[0042]
扩展树在空间内生成随机点，从起始点向随机点生成随机步长；
[0043]
判断是否碰撞障碍物；
[0044]
若碰撞障碍物，则返回生成随机步长的步骤；
[0045]
若未碰撞障碍物，则判断是否远离起始点并接近目标点；
[0046]
若未远离起始点并接近目标点，则返回生成随机步长的步骤；
[0047]
若远离起始点并接近目标点，则在随机步长路径上随机生成节点，并执行剪枝处理。
[0048]
如上所述的基于拣货动线模型的卷烟成品智慧园区管控方法，其中，优选的是，所述扩展树在空间内生成随机点，从起始点向随机点生成随机步长，具体包括：
[0049]
通过以下公式确定随机点的路径中任意扩展节点的路径：
[0050]
l＝tree(x
child-x
parent
)+tree(x
parent-x
init
)
ꢀꢀꢀ
(13)，
[0051]
在远离起始点并接近目标点的情况下，所述在随机步长路径上随机生成节点，并执行剪枝处理，具体包括：
[0052]
从初始起点x
init
到父代节点x
parent
中任取一点x
potential
，让节点x
potential
替代父代节点x
parent
,从而生成更优的路径，则新扩展节点路径转化为：
[0053]
l
′
＝tree(x
child-x
potential
)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(14)
[0054]
其中，子代节点为x
child
，父代节点为x
parent
。
[0055]
如上所述的基于拣货动线模型的卷烟成品智慧园区管控方法，其中，优选的是，所述引入logistic映射参数和混沌变量，得到新节点和新路径，并加入扩展树，具体包括：
[0056]
确定logistic混沌映射方程，其表达式为：
[0057]
x
k+1
＝μxk(1-xk),0≤μ≤4,0＜xk＜1
ꢀꢀꢀꢀꢀꢀ
(15)
[0058]
其中，μ为logistic映射参数，xk为混沌变量，在xk∈(0,1)时，logistic映射处于混沌状态，且当μ＝4时，logistic映射处于完全混沌状态，此时的扩展树能够实现节点在混沌空间内的完全搜索；
[0059]
将logistic映射参数和混沌变量引入到剪枝处理后的新路径子代节点的位置生成中，得到一段路径中新的最佳路径节点，其表达式为：
[0060][0061]
其中，λ1为扩展树在混沌空间内的随机扩展步长，λ2为扩展树在混沌空间内的子代方向扩展步长，|x
child-x
potential
|为剪枝处理后子代节点x
child
与随机节点x
potential
的欧氏距离。
[0062]
如上所述的基于拣货动线模型的卷烟成品智慧园区管控方法，其中，优选的是，在达到最大迭代次数的情况下，所述采用基于levy飞行策略的混合差分乌鸦搜索算法，对所述拣货动线模型进行求解，具体包括：
[0063]
确定基于乌鸦搜索算法得到的乌鸦更新位置和乌鸦记忆更新位置；
[0064]
确定基于levy飞行策略得到的个体位置更新方式；
[0065]
确定差分进化策略的变异操作、交叉操作和选择操作；
[0066]
采用基于levy飞行策略的混合差分乌鸦搜索算法，对所述拣货动线模型进行求解。
[0067]
如上所述的基于拣货动线模型的卷烟成品智慧园区管控方法，其中，优选的是，所述确定基于乌鸦搜索算法得到的乌鸦更新位置和乌鸦记忆更新位置，具体包括：
[0068]
在记忆阶段，种群数量为n的乌鸦在维度为dim的搜索空间内，初始化每只乌鸦初始位置为：
[0069]
x
i，iter
(i＝1，2，
…
，n；iter＝1，2，
…
，iter
max
)
ꢀꢀꢀ
(17)
[0070]
其中，iter
max
为n只乌鸦进行跟踪的次数，即最大迭代次数；
[0071]
在记忆阶段，每只乌鸦的记忆藏食位置为：
[0072]mi,iter
(i＝1,2,
…
,n；iter＝1,2,
…
,iter
max
)
ꢀꢀꢀ
(18)
[0073]
在跟踪阶段，乌鸦i跟踪乌鸦j来偷取乌鸦j的食物，当乌鸦i成功偷取食物后，为防止自身被跟踪而产生感知概率ap
i,iter
，从而发生两种自身位置更新情况：
[0074]
若乌鸦j未感知到被乌鸦i跟踪，则乌鸦i通过以下公式更新它的位置：
[0075]
x
i,iter+1
＝x
i,iter
+randi*fl
i,iter
*(m
j,iter-x
i,iter
)
ꢀꢀꢀ
(19)
[0076]
若乌鸦j感知到被乌鸦i跟踪，则乌鸦j到达搜索空间内的随机位置点，以欺骗乌鸦i的位置更新至随机点；
[0077]
综合两种情况，乌鸦位置更新为：
[0078][0079]
乌鸦记忆位置更新为：
[0080][0081]
其中，randj是在区间[0,1]分布的随机数，fl
i,iter
是乌鸦i在迭代iter次中的飞行距离，ap
j,iter
是乌鸦j在经历iter次迭代后的感知概率，在不断的追踪迭代过程中，乌鸦群的感知概率越高，此迭代中的乌鸦的位置越优，
[0082]
所述确定基于levy飞行策略得到的个体位置更新方式，具体包括：
[0083]
在乌鸦跟踪过程中嵌入levy飞行策略，其个体位置更新方式为：
[0084][0085]
其中，levy(λ)表示服从levy分布的飞行移动，并且其满足：
[0086]
[0087]
其中u和v均服从正态分布：
[0088][0089][0090]
所述确定差分进化策略的变异操作、交叉操作和选择操作，具体包括：
[0091]
随机选取种群中的两个搜索代理，进行搜索代理间信息的传递，变异操作如下式：
[0092]vi,iter+1
＝x
r1,iter
+f*(x
r2,iter-x
r3,iter
)
ꢀꢀꢀꢀꢀꢀ
(26)
[0093]
其中，v
i,iter+1
为变异后的种群，f∈[0，2]为变异算子，x
r2,iter
和x
r3,iter
为随机选取的不同于x
r1,iter
的搜索代理；
[0094]
依据交叉概率对两个父代结构进行部分的替换，交叉操作如下式：
[0095][0096]
其中，cr∈[0，1]为交叉算子，rand是[0,1]间随机产生的随机数，u
ij,t+1
是交叉产生的新种群；
[0097]
搜索代理通过变异和交叉操作后需通过适应度函数值来判断进行保留原始种群或者交叉产生的新种群，选择操作如下式：
[0098][0099]
如上所述的基于拣货动线模型的卷烟成品智慧园区管控方法，其中，优选的是，所述采用基于levy飞行策略的混合差分乌鸦搜索算法，对所述拣货动线模型进行求解，具体包括：
[0100]
初始化乌鸦搜索算法的算法参数，并定义决策变量；
[0101]
随机选取一只乌鸦个体，并计算初始适应度函数值；
[0102]
若rand≥ap
i,iter
，则通过公式(17)更新位置；
[0103]
若rand＜ap
i,iter
，则通过公式(20)更新位置；
[0104]
计算并记录新位置适应度值，更新乌鸦新记忆位置m
i,iter+1
；
[0105]
根据公式(26)-(28)对当前搜索代理执行变异、交叉和选择操作，记录目标适应度函数值fitness；
[0106]
根据公式(3)记录路径总能耗ec，并通过巡逻重复率和巡逻面积计算平均步长能耗
[0107]
若达到最大迭代次数输出最优解，若未达到则返回计算初始适应度函数值的步骤，直到迭代至最大。
[0108]
本发明提供一种基于拣货动线模型的卷烟成品智慧园区管控方法，从拣货路径节点选择及随机性选择性能入手，进行剪枝处理并引入混沌理论策略，对rrt算法进行改进，
基于混沌理论策略改进的rrt路径规划算法，对拣货动线模型进行求解，将logistic映射参数和混沌变量引入到剪枝处理后的新路径子代节点的位置生成中，得到一段路径中新的最佳路径节点，并针对搜索精度和更新策略两个方面对传统乌鸦搜索算法进行改进，可以防止乌鸦群的盲目位置更新，同时增强全局搜索能力，以提高其收敛速度和搜索精度，有利于降低企业内部运营成本，提高交货效率。
附图说明
[0109]
为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明作进一步描述，其中：
[0110]
图1为本发明提供的基于拣货动线模型的卷烟成品智慧园区管控方法的实施例的流程图；
[0111]
图2为本发明提供的基于拣货动线模型的卷烟成品智慧园区管控方法的实施例的剪枝处理示意图；
[0112]
图3为本发明提供的基于拣货动线模型的卷烟成品智慧园区管控方法的实施例的剪枝处理效果对比图；
[0113]
图4为本发明提供的基于拣货动线模型的卷烟成品智慧园区管控方法的实施例的逻辑图。
具体实施方式
[0114]
现在将参照附图来详细描述本公开的各种示例性实施例。对示例性实施例的描述仅仅是说明性的，决不作为对本公开及其应用或使用的任何限制。本公开可以以许多不同的形式实现，不限于这里所述的实施例。提供这些实施例是为了使本公开透彻且完整，并且向本领域技术人员充分表达本公开的范围。应注意到：除非另外具体说明，否则在这些实施例中阐述的部件和步骤的相对布置、材料的组分、数字表达式和数值应被解释为仅仅是示例性的，而不是作为限制。
[0115]
本公开中使用的“第一”、“第二”：以及类似的词语并不表示任何顺序、数量或者重要性，而只是用来区分不同的部分。“包括”或者“包含”等类似的词语意指在该词前的要素涵盖在该词后列举的要素，并不排除也涵盖其他要素的可能。“上”、“下”等仅用于表示相对位置关系，当被描述对象的绝对位置改变后，则该相对位置关系也可能相应地改变。
[0116]
在本公开中，当描述到特定部件位于第一部件和第二部件之间时，在该特定部件与第一部件或第二部件之间可以存在居间部件，也可以不存在居间部件。当描述到特定部件连接其它部件时，该特定部件可以与所述其它部件直接连接而不具有居间部件，也可以不与所述其它部件直接连接而具有居间部件。
[0117]
本公开使用的所有术语(包括技术术语或者科学术语)与本公开所属领域的普通技术人员理解的含义相同，除非另外特别定义。还应当理解，在诸如通用字典中定义的术语应当被解释为具有与它们在相关技术的上下文中的含义相一致的含义，而不应用理想化或极度形式化的意义来解释，除非这里明确地这样定义。
[0118]
对于相关领域普通技术人员已知的技术、方法和设备可能不作详细讨论，但在适当情况下，技术、方法和设备应当被视为说明书的一部分。
[0119]
由于卷烟园区的管控涉及动态货物分配、拣货动线规划、仓库多目标理货、车辆装卸货等多个作业场景，只有建立多种模型及算法才能切实解决园区管控的核心问题。
[0120]
在现有技术中，通常采用传统算法及改进的群优化算法实现智慧园区的简单管控，但在现有技术的算法中，没有考虑成本、拣货路径、拣货时间、拣货车辆装载效率、人员作业负荷、车辆等待区选址等卷烟成品园区的多约束问题，且现有技术很难在满足约束条件的情况下设计出适应的卷烟成品智慧园区管控系统。
[0121]
目前的研究仅有少量涉及到考虑路径规划的园区管控系统。但是没有任何研究涉及到卷烟园区管控的真实环境条件约束。
[0122]
如图1和图4所示，本实施例提供的基于拣货动线模型的卷烟成品智慧园区管控方法在实际执行过程中，具体包括如下步骤：
[0123]
步骤s1、构建以拣货时间和拣货路径最短为优化目标的拣货动线模型。
[0124]
在本发明的基于拣货动线模型的卷烟成品智慧园区管控方法的一种实施方式中，所述步骤s1具体可以包括：
[0125]
步骤s11、获取园区仓库数据、园区构造数据和资源数据。
[0126]
其中，所述园区仓库数据包括仓库货位分配数据、仓库数量数据、仓库位置数据、仓库所涉作业人员及物流车辆数据等；所述资源数据包含资源种类、资源存贮量、资源所属仓库及货位；所述物流车辆数据包含物流车辆进出入园区时间、物理约束(载重上下限约束)，及所携带商业订单信息(所需资源种类及数量)等。
[0127]
步骤s12、根据所述园区的仓库数据、所述园区构造数据及所述资源数据，构建拣货动线路径优化模型。
[0128]
在本发明的基于拣货动线模型的卷烟成品智慧园区管控方法的一种实施方式中，所述步骤s12具体可以包括：
[0129]
步骤s121、将卷烟成品仓库分为k＝{k1,k2,...,kn}个存储单位，每个单位存储相同类别的卷烟成品，ki表示第i个储存单位，每个储存单位的容量ci；在正常的仓库经营情况下，同一时间可能出现一人拣多货，多人拣多货的情况，一个人的拣货容量为gi；在工作周期内，存在p＝{p1,p2,...,pn}个订单，pj为第j个订单。
[0130]
在本发明中，针对卷烟成品仓库的货样繁多的特点，将卷烟成品仓库分为多个存储单位。
[0131]
步骤s122、拣货任务中，仓库采用多层货架，各存储单位间的距离由水平距离xi与垂直距离yi组成，通过以下公式计算任意两存储单位间的距离：
[0132]ki,i+1
＝|x
i+1-xi|+|y
i+1-yi|
ꢀꢀ
(1)。
[0133]
步骤s123、单个工作人员及其辅助工具(例如可以为载具等)在进行拣货时，满足以下公式的最大化原则，以提高拣货效率，节约人力成本：
[0134][0135][0136]
步骤s124、基于忽略各作业人员间的速度差异，均为v的假设，则通过以下公式计
算单个工人通过拣货路径的时间ti：
[0137]
ti＝k
i,i+1
/v
ꢀꢀꢀ
(4)。
[0138]
步骤s125、在整个拣货周期中，单个工人在仓库内拣选时间ati和订单拣选完成后的整理打包所花费的时间bti满足以下公式：
[0139][0140]
步骤s126、确定卷烟成品仓库拣货动线模型的双目标函数如下式：
[0141]
f(x)＝|x
i+1-xi|+|y
i+1-yi|
ꢀꢀ
(7)
[0142][0143]
步骤s127、采用ahp法，通过以下公式确定两目标函数的权重：
[0144][0145][0146]
ω＝ωm+ωn/2
ꢀꢀꢀ
(11)。
[0147]
根据两目标函数的权重，构建拣货动线的目标函数为：
[0148]
minf(x)＝ω1f(x)+ω2g(x)
ꢀꢀꢀ
(12)。
[0149]
步骤s2、基于混沌理论策略改进的快速扩展随机树路径规划算法，对所述拣货动线模型进行求解。
[0150]
在本发明的基于拣货动线模型的卷烟成品智慧园区管控方法的一种实施方式中，所述步骤s2具体可以包括：
[0151]
步骤s21、在随机步长路径上随机生成节点，并执行剪枝处理。
[0152]
在本发明的基于拣货动线模型的卷烟成品智慧园区管控方法的一种实施方式中，所述步骤s21具体可以包括：
[0153]
步骤s211、初始化地形，设定起始点、目标点和拣货任务参数。
[0154]
步骤s212、扩展树在空间内生成随机点，从起始点向随机点生成随机步长。
[0155]
rrt算法(rapidly exploring random tree，快速扩展随机树)是一种随机性算法，它可以直接应用于非完整约束系统的规划，不需进行路径转换，所以它的算法复杂度较小，尤为适用于高维多自由度的系统。在传统rrt算法中从起始点出发随机生成树状节点，将目标点视为随机点，生成随机数判别与随机点的大小，从而决定树的扩展方向。具体地，通过以下公式确定随机点的路径中任意扩展节点的路径：
[0156]
l＝tree(x
child-x
parent
)+tree(x
parent-x
init
)
ꢀꢀꢀ
(13)。
[0157]
步骤s213、判断是否碰撞障碍物。
[0158]
步骤s214、若碰撞障碍物，则返回生成随机步长的步骤。
[0159]
步骤s215、若未碰撞障碍物，则判断是否远离起始点并接近目标点。
[0160]
步骤s216、若未远离起始点并接近目标点，则返回生成随机步长的步骤。
[0161]
步骤s217、若远离起始点并接近目标点，则在随机步长路径上随机生成节点，并执行剪枝处理。
[0162]
具体地，从初始起点x
init
到父代节点x
parent
中任取一点x
potential
，让节点x
potential
替代父代节点x
parent
,从而生成更优的路径，则新扩展节点路径转化为：
[0163]
l
′
＝tree(x
child-x
potential
)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(14)
[0164]
其中，子代节点为x
child
，父代节点为x
parent
。
[0165]
如图2所示，实线为剪枝后路径，虚线为原路径，通过对其该路径进行剪枝处理，可以解决此类路径生成方式步骤代价过大的问题。
[0166]
步骤s22、引入logistic映射参数和混沌变量，得到新节点和新路径，并加入扩展树。
[0167]
在本发明的基于拣货动线模型的卷烟成品智慧园区管控方法的一种实施方式中，所述步骤s22具体可以包括：
[0168]
步骤s221、确定logistic混沌映射方程，其表达式为：
[0169]
x
k+1
＝μxk(1-xk),0≤μ≤4,0＜xk＜1
ꢀꢀꢀꢀꢀꢀ
(15)
[0170]
其中，μ为logistic映射参数，xk为混沌变量，在xk∈(0,1)时，logistic映射处于混沌状态，且当μ＝4时，logistic映射处于完全混沌状态，此时的扩展树能够实现节点在混沌空间内的完全搜索。
[0171]
考虑到在rrt对路径中障碍物检测后，其通常会在空间中进行无用搜索，偏离目标点方向，时间成本较大。因此，本发明为减少时间成本和空间复杂度，引入logistic混沌映射对其进行改进。logistic混沌映射数学形式非常简单且功能性强，用来描述复杂的路径随机情况十分合适。
[0172]
步骤s222、将logistic映射参数和混沌变量引入到剪枝处理后的新路径子代节点的位置生成中，得到一段路径中新的最佳路径节点，其表达式为：
[0173][0174]
其中，λ1为扩展树在混沌空间内的随机扩展步长，λ2为扩展树在混沌空间内的子代方向扩展步长，|x
child-x
potential
|为剪枝处理后子代节点x
child
与随机节点x
potential
的欧氏距离。
[0175]
步骤s23、判断是否达到最大迭代次数。
[0176]
步骤s24、若达到最大迭代次数，则采用基于levy飞行策略的混合差分乌鸦搜索算法，对所述拣货动线模型进行求解。
[0177]
在本发明的基于拣货动线模型的卷烟成品智慧园区管控方法的一种实施方式中，在达到最大迭代次数的情况下，所述步骤s24具体可以包括：
[0178]
步骤s241、确定基于乌鸦搜索算法得到的乌鸦更新位置和乌鸦记忆更新位置。
[0179]
乌鸦搜索算法(crow search algorithm,csa)是一种基于人口优化的元启发式算
法。其主要思想是模仿乌鸦偷取食物、藏储食物的行为进行优化，乌鸦的智能行为主要分为两个阶段：记忆阶段、跟踪阶段。具体地，在记忆阶段，种群数量为n的乌鸦在维度为dim的搜索空间内，初始化每只乌鸦初始位置为：
[0180]
x
i，iter
(i＝1，2，
…
，n；iter＝1，2，
…
，iter
max
)
ꢀꢀꢀ
(17)
[0181]
其中，iter
max
为n只乌鸦进行跟踪的次数，即最大迭代次数；
[0182]
在记忆阶段，每只乌鸦的记忆藏食位置为：
[0183]mi，iter
(i＝1，2，
…
，n；iter＝1，2，
…
，iter
max
)
ꢀꢀꢀ
(18)
[0184]
在跟踪阶段，乌鸦i跟踪乌鸦j来偷取乌鸦j的食物，当乌鸦i成功偷取食物后，为防止自身被跟踪而产生感知概率ap
i,iter
，从而发生两种自身位置更新情况：
[0185]
若乌鸦j未感知到被乌鸦i跟踪，则乌鸦i通过以下公式更新它的位置：
[0186]
x
i,iter+1
＝x
i,iter
+randi*fl
i,iter
*(m
j,iter-x
i,iter
)
ꢀꢀꢀ
(19)
[0187]
若乌鸦j感知到被乌鸦i跟踪，则乌鸦j到达搜索空间内的随机位置点，以欺骗乌鸦i的位置更新至随机点；
[0188]
综合两种情况，乌鸦位置更新为：
[0189][0190]
乌鸦记忆位置更新为：
[0191][0192]
其中，randj是在区间[0,1]分布的随机数，fl
i,iter
是乌鸦i在迭代iter次中的飞行距离，ap
j,iter
是乌鸦j在经历iter次迭代后的感知概率，在不断的追踪迭代过程中，乌鸦群的感知概率越高，此迭代中的乌鸦的位置越优。
[0193]
步骤s242、确定基于levy飞行策略得到的个体位置更新方式。
[0194]
csa不属于贪心算法，即使新位置不优于当前位置，它仍然会进行更新至新位置。其优点在于搜索空间大，每一次迭代的目前最优解都会直接趋向于全局最优解。这也导致其搜索精度不高，且乌鸦以群居形式生存，当乌鸦i被乌鸦j感知而往随机点时，整个乌鸦群均会盲目更新。因此，本发明针对搜索精度和更新策略两个方面对传统乌鸦搜索算法进行改进。
[0195]
具体地，在乌鸦跟踪过程中嵌入levy飞行策略，其个体位置更新方式为：
[0196][0197]
其中，levy(λ)表示服从levy分布的飞行移动，并且其满足：
[0198][0199]
其中u和v均服从正态分布：
[0200]
[0201][0202]
本发明在乌鸦跟踪过程中嵌入levy飞行策略，从而防止乌鸦群的盲目位置更新。levy飞行策略的随机游走是一种偏向于较大搜索步长的搜索方式，其基本特性是将短距离飞行和随机性长距离飞行相结合，其“重尾”式的分布正态分布结构能够很好地构建稳定优化体系。
[0203]
步骤s243、确定差分进化策略的变异操作、交叉操作和选择操作。
[0204]
本发明引入差分进化策略，通过差分进化算法(differential evolution，de)中的交叉、变异和选择操作增强全局搜索能力，以提高其收敛速度和搜索精度。在本发明的基于拣货动线模型的卷烟成品智慧园区管控方法的一种实施方式中，所述步骤s243具体可以包括：
[0205]
步骤s2431、随机选取种群中的两个搜索代理，进行搜索代理间信息的传递，变异操作如下式：
[0206]vi,iter+1
＝x
r1,iter
+f*(x
r2,iter-x
r3,iter
)
ꢀꢀꢀꢀꢀꢀ
(26)
[0207]
其中，v
i,iter+1
为变异后的种群，f∈[0，2]为变异算子，x
r2,iter
和x
r3,iter
为随机选取的不同于x
r1,iter
的搜索代理。
[0208]
步骤s2432、依据交叉概率对两个父代结构进行部分的替换，交叉操作如下式：
[0209][0210]
其中，cr∈[0，1]为交叉算子，rand是[0,1]间随机产生的随机数，u
ij,t+1
是交叉产生的新种群。
[0211]
步骤s2433、搜索代理通过变异和交叉操作后需通过适应度函数值来判断进行保留原始种群或者交叉产生的新种群，选择操作如下式：
[0212][0213]
步骤s244、采用基于levy飞行策略的混合差分乌鸦搜索算法，对所述拣货动线模型进行求解。
[0214]
在本发明的基于拣货动线模型的卷烟成品智慧园区管控方法的一种实施方式中，所述步骤s244具体可以包括：
[0215]
步骤s2441、初始化乌鸦搜索算法的算法参数，并定义决策变量。
[0216]
具体地，初始化乌鸦种群x
i,iter
、v
i,iter+1
、u
ij,iter+1
、m
i,iter
，设置初始参数并定义决策变量。
[0217]
步骤s2442、随机选取一只乌鸦个体，并计算初始适应度函数值。
[0218]
步骤s2443、若rand≥ap
i,iter
，则通过公式(17)更新位置；若rand＜ap
i,iter
，则通过公式(20)更新位置。
[0219]
步骤s2444、计算并记录新位置适应度值，更新乌鸦新记忆位置m
i,iter+1
。
[0220]
步骤s2445、根据公式(26)-(28)对当前搜索代理执行变异、交叉和选择操作，记录目标适应度函数值fitness。
[0221]
步骤s2446、根据公式(3)记录路径总能耗ec，并通过巡逻重复率和巡逻面积计算平均步长能耗
[0222]
步骤s2447、若达到最大迭代次数输出最优解，若未达到则返回计算初始适应度函数值的步骤，直到迭代至最大。
[0223]
步骤s25、若未达到最大迭代次数，则返回生成随机步长的步骤，直到迭代至最大。
[0224]
本发明实施例提供的基于拣货动线模型的卷烟成品智慧园区管控方法，从拣货路径节点选择及随机性选择性能入手，进行剪枝处理并引入混沌理论策略，对rrt算法进行改进，基于混沌理论策略改进的rrt路径规划算法，对拣货动线模型进行求解，将logistic映射参数和混沌变量引入到剪枝处理后的新路径子代节点的位置生成中，得到一段路径中新的最佳路径节点，并针对搜索精度和更新策略两个方面对传统乌鸦搜索算法进行改进，可以防止乌鸦群的盲目位置更新，同时增强全局搜索能力，以提高其收敛速度和搜索精度，有利于降低企业内部运营成本，提高交货效率。
[0225]
至此，已经详细描述了本公开的各实施例。为了避免遮蔽本公开的构思，没有描述本领域所公知的一些细节。本领域技术人员根据上面的描述，完全可以明白如何实施这里公开的技术方案。
[0226]
虽然已经通过示例对本公开的一些特定实施例进行了详细说明，但是本领域的技术人员应该理解，以上示例仅是为了进行说明，而不是为了限制本公开的范围。本领域的技术人员应该理解，可在不脱离本公开的范围和精神的情况下，对以上实施例进行修改或者对部分技术特征进行等同替换。本公开的范围由所附权利要求来限定。
技术特征：1.一种基于拣货动线模型的卷烟成品智慧园区管控方法，其特征在于，包括：构建以拣货时间和拣货路径最短为优化目标的拣货动线模型；基于混沌理论策略改进的快速扩展随机树路径规划算法，对所述拣货动线模型进行求解。2.根据权利要求1所述的基于拣货动线模型的卷烟成品智慧园区管控方法，其特征在于，所述构建以拣货时间和拣货路径最短为优化目标的拣货动线模型，具体包括：获取园区仓库数据、园区构造数据和资源数据；根据所述园区的仓库数据、所述园区构造数据及所述资源数据，构建拣货动线路径优化模型。3.根据权利要求2所述的基于拣货动线模型的卷烟成品智慧园区管控方法，其特征在于，所述根据所述园区的仓库数据、所述园区构造数据及所述资源数据，构建拣货动线路径优化模型，具体包括：将卷烟成品仓库分为k＝{k1,k2,...,k
n
}个存储单位，每个单位存储相同类别的卷烟成品，k
i
表示第i个储存单位，每个储存单位的容量c
i
；在正常的仓库经营情况下，同一时间可能出现一人拣多货，多人拣多货的情况，一个人的拣货容量为g
i
；在工作周期内，存在p＝{p1,p2,...,p
n
}个订单，p
j
为第j个订单；拣货任务中，仓库采用多层货架，各存储单位间的距离由水平距离x
i
与垂直距离y
i
组成，通过以下公式计算任意两存储单位间的距离：k
i,i+1
＝|x
i+1-x
i
|+|y
i+1-y
i
|
ꢀꢀꢀꢀ
(1)单个工作人员及其辅助工具在进行拣货时，满足以下公式的最大化原则，以提高拣货效率，节约人力成本：效率，节约人力成本：基于忽略各作业人员间的速度差异，均为v的假设，则通过以下公式计算单个工人通过拣货路径的时间t
i
：t
i
＝k
i,i+1
/v
ꢀꢀꢀ
(4)；在整个拣货周期中，单个工人在仓库内拣选时间at
i
和订单拣选完成后的整理打包所花费的时间bt
i
满足以下公式：确定卷烟成品仓库拣货动线模型的双目标函数如下式：f(x)＝|x
i+1-x
i
|+|y
i+1-y
i
|
ꢀꢀꢀꢀ
(7)采用ahp法，通过以下公式确定两目标函数的权重：
ω＝ω
m
+ω
n
/2
ꢀꢀꢀ
(11)；根据两目标函数的权重，构建拣货动线的目标函数为：minf(x)＝ω1f(x)+ω2g(x)
ꢀꢀꢀ
(12)。4.根据权利要求3所述的基于拣货动线模型的卷烟成品智慧园区管控方法，其特征在于，所述基于混沌理论策略改进的快速扩展随机树路径规划算法，对所述拣货动线模型进行求解，具体包括：在随机步长路径上随机生成节点，并执行剪枝处理；引入logistic映射参数和混沌变量，得到新节点和新路径，并加入扩展树；判断是否达到最大迭代次数；若达到最大迭代次数，则采用基于levy飞行策略的混合差分乌鸦搜索算法，对所述拣货动线模型进行求解；若未达到最大迭代次数，则返回生成随机步长的步骤，直到迭代至最大。5.根据权利要求4所述的基于拣货动线模型的卷烟成品智慧园区管控方法，其特征在于，所述在随机步长路径上随机生成节点，并执行剪枝处理，具体包括：初始化地形，设定起始点、目标点和拣货任务参数；扩展树在空间内生成随机点，从起始点向随机点生成随机步长；判断是否碰撞障碍物；若碰撞障碍物，则返回生成随机步长的步骤；若未碰撞障碍物，则判断是否远离起始点并接近目标点；若未远离起始点并接近目标点，则返回生成随机步长的步骤；若远离起始点并接近目标点，则在随机步长路径上随机生成节点，并执行剪枝处理。6.根据权利要求5所述的基于拣货动线模型的卷烟成品智慧园区管控方法，其特征在于，所述扩展树在空间内生成随机点，从起始点向随机点生成随机步长，具体包括：通过以下公式确定随机点的路径中任意扩展节点的路径：l＝tree(x
child-x
parent
)+tree(x
parent-x
init
)
ꢀꢀꢀ
(13)，在远离起始点并接近目标点的情况下，所述在随机步长路径上随机生成节点，并执行剪枝处理，具体包括：从初始起点x
init
到父代节点x
parent
中任取一点x
potential
，让节点x
potential
替代父代节点x
parent
,从而生成更优的路径，则新扩展节点路径转化为：l
′
＝tree(x
child-x
potential
)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(14)
其中，子代节点为x
child
，父代节点为x
parent
。7.根据权利要求6所述的基于拣货动线模型的卷烟成品智慧园区管控方法，其特征在于，所述引入logistic映射参数和混沌变量，得到新节点和新路径，并加入扩展树，具体包括：确定logistic混沌映射方程，其表达式为：x
k+1
＝μx
k
(1-x
k
),0≤μ≤4,0＜x
k
＜1
ꢀꢀꢀꢀꢀꢀ
(15)其中，μ为logistic映射参数，x
k
为混沌变量，在x
k
∈(0,1)时，logistic映射处于混沌状态，且当μ＝4时，logistic映射处于完全混沌状态，此时的扩展树能够实现节点在混沌空间内的完全搜索；将logistic映射参数和混沌变量引入到剪枝处理后的新路径子代节点的位置生成中，得到一段路径中新的最佳路径节点，其表达式为：其中，λ1为扩展树在混沌空间内的随机扩展步长，λ2为扩展树在混沌空间内的子代方向扩展步长，|x
child-x
potential
|为剪枝处理后子代节点x
child
与随机节点x
potential
的欧氏距离。8.根据权利要求7所述的基于拣货动线模型的卷烟成品智慧园区管控方法，其特征在于，在达到最大迭代次数的情况下，所述采用基于levy飞行策略的混合差分乌鸦搜索算法，对所述拣货动线模型进行求解，具体包括：确定基于乌鸦搜索算法得到的乌鸦更新位置和乌鸦记忆更新位置；确定基于levy飞行策略得到的个体位置更新方式；确定差分进化策略的变异操作、交叉操作和选择操作；采用基于levy飞行策略的混合差分乌鸦搜索算法，对所述拣货动线模型进行求解。9.根据权利要求8所述的基于拣货动线模型的卷烟成品智慧园区管控方法，其特征在于，所述确定基于乌鸦搜索算法得到的乌鸦更新位置和乌鸦记忆更新位置，具体包括：在记忆阶段，种群数量为n的乌鸦在维度为dim的搜索空间内，初始化每只乌鸦初始位置为：x
i,iter
(i＝1,2,
…
,n；iter＝1,2,
…
,iter
max
)
ꢀꢀꢀ
(17)其中，iter
max
为n只乌鸦进行跟踪的次数，即最大迭代次数；在记忆阶段，每只乌鸦的记忆藏食位置为：m
i,iter
(i＝1,2,
…
,n；iter＝1,2,
…
,iter
max
)
ꢀꢀꢀ
(18)在跟踪阶段，乌鸦i跟踪乌鸦j来偷取乌鸦j的食物，当乌鸦i成功偷取食物后，为防止自身被跟踪而产生感知概率ap
i,iter
，从而发生两种自身位置更新情况：若乌鸦j未感知到被乌鸦i跟踪，则乌鸦i通过以下公式更新它的位置：x
i,iter+1
＝x
i,iter
+rand
i
*fl
i,iter
*(m
j,iter-x
i,iter
)
ꢀꢀꢀ
(19)若乌鸦j感知到被乌鸦i跟踪，则乌鸦j到达搜索空间内的随机位置点，以欺骗乌鸦i的位置更新至随机点；综合两种情况，乌鸦位置更新为：
乌鸦记忆位置更新为：其中，rand
j
是在区间[0,1]分布的随机数，fl
i,iter
是乌鸦i在迭代iter次中的飞行距离，ap
j,iter
是乌鸦j在经历iter次迭代后的感知概率，在不断的追踪迭代过程中，乌鸦群的感知概率越高，此迭代中的乌鸦的位置越优，所述确定基于levy飞行策略得到的个体位置更新方式，具体包括：在乌鸦跟踪过程中嵌入levy飞行策略，其个体位置更新方式为：其中，levy(λ)表示服从levy分布的飞行移动，并且其满足：其中u和v均服从正态分布：其中u和v均服从正态分布：所述确定差分进化策略的变异操作、交叉操作和选择操作，具体包括：随机选取种群中的两个搜索代理，进行搜索代理间信息的传递，变异操作如下式：v
i,iter+1
＝x
r1,iter
+f*(x
r2,iter-x
r3,iter
)
ꢀꢀꢀꢀꢀꢀ
(26)其中，v
i,iter+1
为变异后的种群，f∈[0，2]为变异算子，x
r2,iter
和x
r3,iter
为随机选取的不同于x
r1,iter
的搜索代理；依据交叉概率对两个父代结构进行部分的替换，交叉操作如下式：其中，cr∈[0，1]为交叉算子，rand是[0,1]间随机产生的随机数，u
ij,t+1
是交叉产生的新种群；搜索代理通过变异和交叉操作后需通过适应度函数值来判断进行保留原始种群或者交叉产生的新种群，选择操作如下式：10.根据权利要求9所述的基于拣货动线模型的卷烟成品智慧园区管控方法，其特征在
于，所述采用基于levy飞行策略的混合差分乌鸦搜索算法，对所述拣货动线模型进行求解，具体包括：初始化乌鸦搜索算法的算法参数，并定义决策变量；随机选取一只乌鸦个体，并计算初始适应度函数值；若rand≥ap
i,iter
，则通过公式(17)更新位置；若rand＜ap
i,iter
，则通过公式(20)更新位置；计算并记录新位置适应度值，更新乌鸦新记忆位置m
i,iter+1
；根据公式(26)-(28)对当前搜索代理执行变异、交叉和选择操作，记录目标适应度函数值fitness；根据公式(3)记录路径总能耗ec，并通过巡逻重复率和巡逻面积计算平均步长能耗若达到最大迭代次数输出最优解，若未达到则返回计算初始适应度函数值的步骤，直到迭代至最大。
技术总结本发明公开了一种基于拣货动线模型的卷烟成品智慧园区管控方法，包括：构建以拣货时间和拣货路径最短为优化目标的拣货动线模型；基于混沌理论策略改进的快速扩展随机树路径规划算法，对拣货动线模型进行求解。本发明的基于拣货动线模型的卷烟成品智慧园区管控方法，将Logistic映射参数和混沌变量引入到剪枝处理后的新路径子代节点的位置生成中，得到一段路径中新的最佳路径节点，并针对搜索精度和更新策略两个方面对传统乌鸦搜索算法进行改进，可以防止乌鸦群的盲目位置更新，同时增强全局搜索能力，以提高其收敛速度和搜索精度，有利于降低企业内部运营成本，提高交货效率。提高交货效率。提高交货效率。
技术研发人员：徐跃明 欧阳世波 王磊 徐珂 鲍景 吴颀 安裕强 周安祥 李苍云 张清友
受保护的技术使用者：红云红河烟草（集团）有限责任公司
技术研发日：2022.03.31
技术公布日：2022/7/5
