一种可跨层穿梭车存取系统调度决策方法

1.本发明涉及仓储系统调度与优化领域，尤其是涉及一种可跨层穿梭车存取系统调度决策方法。


背景技术：

2.可跨层穿梭车存取系统是近几年来由传统的自动存储与取货系统发展起来的新型自动化存储系统。该系统由多层货架内的穿梭车与提升机组成，不仅具有高空间利用率和存储容量的优点，而且具备更高的吞吐能力，以及较高的柔性以适应外界的订单波动。与层限制穿梭车存取系统相比，可跨层穿梭车存取系统的穿梭车可通过提升机实现跨层存取货物，具有更高的柔性和鲁棒性，并减少了穿梭车数量。由于穿梭车在执行任务中可能需要跨层，也因此带来了多台穿梭车执行任务时出现冲突的问题。任务排序、设备调度与货位分配方案的不同导致穿梭车和提升机的作业路线不同，从而影响系统执行批次订单任务的效率。巷道和货位的分配方案又直接影响着整个货架组的结构稳定性。因此，对任务排序，穿梭车和提升机的协同调度以及货位分配具有重要意义。
3.目前国内外对于传统的自动存储与取货系统已进行了相关研究，但是现有的大部分技术只单独考虑了仓储系统的任务调度或货位分配问题，少有对任务排序、设备调度和货位分配同时进行优化。对于可跨层穿梭车存取系统的调度决策研究少之更少，且少有考虑穿梭车执行任务时的冲突问题。


技术实现要素：

4.本发明的目的就是为了克服上述现有技术存在的缺陷而提供一种可跨层穿梭车存取系统调度决策方法。
5.本发明的目的可以通过以下技术方案来实现：
6.一种可跨层穿梭车存取系统调度决策方法，解决了可跨层穿梭车存取系统的任务排序、设备调度和货位分配集成优化问题，以得到货架综合稳定性较好，批次任务出库作业时间较短，且不含设备冲突的帕累托解集方案，包括以下步骤：
7.s1：以出库总作业时间最小化和货架综合稳定性最大化为目标建立可跨层穿梭车存取系统多目标集成优化数学模型；
8.s2：设计一种改进的多目标野马优化算法；
9.s3：分析系统执行任务过程中的设备冲突问题，提出一种冲突检测与修正策略并集成到步骤s2的算法中；
10.s4：采用步骤s2和s3中的方法对步骤s1中的多目标集成优化模型进行求解以得到任务排序、设备调度和货位分配集成优化方案。
11.优选的，所述的多目标集成优化数学模型的目标函数包括：出库总作业时间和货架综合稳定性。所述的出库总作业时间函数为：
12.13.其中为巷道lam的任务队列的完成时间，m为巷道编号，rm为巷道lam的任务队列长度。
14.所述的货架综合稳定性最大化表示为：
15.f2＝min(max(stm)),m＝1,2,
…
,m
16.其中，stm表示巷道lam的货架组的综合稳定性，stm越大表示货架组综合稳定性越差。
17.优选的，所述出库作业时间函数中计算如下：
[0018][0019]
其中，表示货物提升机lcm执行巷道lam最后一个任务的起始时刻,表示货物提升机lcm执行巷道lam最后一个任务所占用的时间。lcm表示巷道lam配备的货位提升机。
[0020]
优选的，所述的计算中表示货物提升机lcm执行巷道lam的任务队列的第r个任务的起始时刻，计算如下：
[0021][0022]
其中，表示穿梭车执行任务到达出库货位层的时刻，表示巷道lam配备的第j台穿梭车，表示任务位于穿梭车的任务队列的第k个任务，表示lcm执行任务的结束时刻。
[0023]
对于非跨层任务，其中，表示执行任务的起始时刻。的计算公式为：
[0024][0025]
其中，表示执行任务的结束时刻。
[0026]
对于跨层出库任务，与穿梭车提升机lsm执行任务的起始时刻一致，lsm表示巷道lam配备的穿梭车提升机，表示任务位于穿梭车提升机lsm的任务队列的第f个任务，表示穿梭车提升机lsm执行任务的占用时间。的计算公式为：
[0027][0028]
其中，表示穿梭车提升机lsm执行任务的结束时刻。
[0029]
计算公式为：
[0030][0031]
其中，和分别表示竖直方向上穿梭车提升机从当前所在层到达穿梭车所在层的行程时间和从穿梭车所在层到达目标货位所在层的行程时间。t
ld2
表示穿梭车提升机装载穿梭车的时间，t
uld2
表示穿梭车提升机卸载穿梭车的时间。
[0032]
优选的，所述的的计算中表示货物提升机lcm执行巷道lam的第r个任务所占用的时间，计算如下：
[0033][0034]
其中，和分别表示竖直方向上货物提升机从巷道i/o点到达目标货位所在层的行程时间和从目标货位所在层返回巷道i/o点的行程时间。t
ld3
表示货物提升机装载货物的时间，t
uld3
表示货物提升机卸载货物的时间。
[0035]
为穿梭车执行任务的占用时间，对于非跨层出库任务，计算如下：
[0036][0037]
表示水平方向上穿梭车在所在层i/o点与目标货位之间的单行程时间，t
ld1
表示穿梭车装载货箱的时间，t
uld1
表示穿梭车卸载货箱的时间。
[0038]
对于跨层出库任务，计算如下：
[0039][0040]
所述的竖直方向上提升机从货架z1层到达z2层的行程时间计算如下：
[0041][0042]
其中，h0表示货架单元的高度，z为货架的总层数，a
l
为提升机的加速度，v
l
为提升机的最大行驶速度。
[0043]
所述的水平方向上穿梭车从货架y1列到达y2列的行程时间计算如下：
[0044][0045]
其中，w0表示货架单元的宽度，c为货架的总列数，as为穿梭车的加速度，vs为穿梭车的最大行驶速度。
[0046]
优选的，所述的巷道lam的货架组综合稳定性函数为：
[0047]
stm＝ε*ghm+γ*δmm[0048]
其中，ghm表示巷道lam的货架组的结构稳定性，δmm表示巷道lam的货架组的抗倾
覆性，ε和γ分别为货架组的结构稳定性和抗倾覆性的指标权重，且满足ε+γ＝1。
[0049]
所述的货架组的结构稳定性函数为：
[0050][0051]
其中，z为货架的总层数，c为货架的总列数，x表示货架排号，y表示货架列号，z表示货架层号，q
xyz
表示货位占用状态，若[x,y,z]处的货位被占用，取1，否则，取0。m
xyz
表示存储在[x,y,z]货位处的货物的质量，h0表示货架单元的高度。
[0052]
所述的货架组的抗倾覆性函数为：
[0053][0054]
优选的，所建立的数学模型约束条件为：
[0055][0056][0057][0058][0059][0060]
其中，n
im
为任务oi在巷道lam中的货位总数，当巷道lam中的第n个货位被选为任务i的出库货位时，取1；否则，取0。i表示批次任务总数。j表示每条巷道配备的穿梭车总数。当订单任务oi被巷道lam中的第j台穿梭车执行时，取1；否则，取0。当任务oi被货物提升机lcm执行时，取1；否则，取0。k
mj
表示穿梭车的任务队列长度。rm为巷道lam的任务队列长度。
[0061]
优选的，所述的步骤s2中的改进具体包括：
[0062]
s21：分别针对任务排序段、提升机选择段、穿梭车选择段和货位分配段设计编码与解码方法。
[0063]
s22：引入非支配排序方法，重新定义种马、小马驹和栖息地的选择方法，并对马群的竞选领导行为进行修正。
[0064]
s23：设计双离群分段多点交叉机制，改进马群的交配繁衍行为，增加算法的全局搜索能力。
[0065]
s24：引入莱维飞行策略，改进马群的引导行为，增加算法跳出局部最优的能力。
[0066]
优选的，所述的步骤s21中任务排序段、提升机选择段、穿梭车选择段和货位分配段的编码与解码方法包括：为解决任务调度和货位分配问题，每个解中包括四段：即任务排序段、提升机选择段、穿梭车选择段和货位分配段，每段编码的长度等于批次订单任务总数，其中，提升机和穿梭车选择段构成设备选择段。任务排序段采用随机键编码，设备选择
段和货位分配采用实数编码。四段编码同一次序位置的编码为一组，且随着任务排序的变化一同变化。任务排序段的随机键数值范围为[0,1]，随机键越小的任务排序越靠前。提升机选择段的编码数值范围为[1,m+1)，穿梭车选择段的编码数值范围为[1,j+1)。其中，m为巷道数量，j为每个巷道配备的穿梭车的数量。对设备选择段的编码取整得到解码后的结果，如某一任务在提升机选择段的编码3.42取整后为3，则该任务由3#货物提升机完成出库，也表示该任务被添加到3#巷道的队列；在穿梭车选择段编码2.77取整后为2，则该任务由3#巷道的2#穿梭车完成搬运。货位分配段的编码数值范围为[1,n+1)，其中，n为该任务在被选巷道的货位数量。对编码数值取整解码，如4.09取整后为4，表示该任务分配的出库货位为被选巷道的货位集的4#货位。
[0067]
优选的，所述的步骤s22中，种马、小马驹和栖息地的选择方法为：对于马群初始化，将种群中所有个体划分为不同集合种马优先从中选择，剩余数目的种马从其余集合的个体中随机选择。其余成员被随机分配给种马作为小马驹，形成不同马群。之后，马群的种马根据适应度选择。对所有种马进行非支配排序得到随机从中选择一匹种马作为栖息地。马群的竞选领导行为公式为：
[0068][0069]
其中，为马群中的小马驹当前所在的位置。stallion
ω
为马群ω种马的位置。
[0070]
优选的，所述的步骤s23中的双离群分段多点交叉机制包括：成熟期的小马驹与来自不同马群的达到成熟期的小马驹离群后进行交配，产生两个子代，分别随机加入到与原先不同的另外两个马群中。所述的分段多点交叉具体步骤如下：
[0071]
s231：任务排序段随机选择成员1的a个编码，与成员2相同位置的编码交换，1≤a≤i/2。其中，i为订单任务数。
[0072]
s232：提升机和穿梭车选择段随机选择成员1的b个邻位双编码，与成员2相邻位置的邻位双编码交换，1≤b≤i/4。
[0073]
s233：货位分配段随机选择成员1的g个邻位三编码，与成员2随机的g个邻位三编码交换，1≤g≤i/3。
[0074]
优选的，所述的步骤s24中的莱维飞行策略包括：对所有的种马进行非支配排序得到帕累托集合从中随机选择一匹种马作为放弃向栖息地移动，改为莱维飞行。莱维飞行的具体如下：
[0075][0076][0077]
[0078]
其中α表示步长缩放因子，d表示个体位置的维度，r1和r2服从标准正态分布，通常设定β＝1.5，γ(x)＝(x-1)！。表示种马stallion
ω
移动后的位置。
[0079]
优选的，所述的步骤s3中，冲突检测与修正策略包括：记录穿梭车提升机和穿梭车的起始层和每次执行任务后的停留层。对解码后的个体进行冲突检测。同巷道配备的所有穿梭车，对于同一执行次序的任务，以下两类情况可能发生冲突：1)穿梭车a的任务目标货位层存在穿梭车b(a≠b)；2)存在至少两台穿梭车的任务目标货位层相同。以巷道为单位进行冲突检测。由分配的货位编号得到任务货位所在层，根据任务货位所在层和穿梭车当前所在层判断是否会出现冲突。对于检测出的冲突，通过更改任务的货位编号以修正个体编码，从而避免冲突。对于无法通过此方法修正的个体，进行适应度惩罚。
[0080]
优选的，所述的冲突检测与修正策略的具体步骤如下：
[0081]
设1#巷道配有3台穿梭车c11、c12、c13
[0082]
s31：计算检测循环次数max_cycle＝最长穿梭车任务队列的任务数；初始化冲突标志con＝0,穿梭车c11、c12、c13所停留的层st1、st2、st3；令cycle
←1[0083]
s32：得到c11,c12,c13当前cycle的目标货位层ot1,ot2,ot3[0084]
s33：若ot1＝＝st2或ot1＝＝st3，则检索c11正在执行任务同巷道的剩余货位，随机选择其中1个货位取代原先货位，并更新ot1；重复此步骤直到不满足此条件；如果该任务剩余货位数为0，则令con＝1,跳至步骤s37
[0085]
s34：若ot2＝＝st1或ot2＝＝st3或ot2＝＝ot1，则检索c12正在执行任务同巷道的剩余货位，随机选择其中1个货位取代原先货位，并更新ot2；重复此步骤直到不满足此条件；如果该任务剩余货位数为0，则令con＝1，跳至步骤s37
[0086]
s35：ot3＝＝st1或ot3＝＝st2或ot3＝＝ot1orot3＝＝ot2，则检索c13正在执行任务同巷道的剩余货位，随机选择其中1个货位取代原先货位，并更新ot3；重复此步骤直到不满足此条件；如果该任务剩余货位数为0，则令con＝1,跳至步骤s37
[0087]
s36：st1←
ot1,st2←
ot2,st3←
ot3；令cycle
←
cycle+1，如果cycle≤max_cycle，返回至步骤s32
[0088]
s37：结束，输出con和修正的货位分配段
[0089]
优选的，所述的步骤s4中，求解方法的完整步骤如下：
[0090]
s41：设置种群规模n，种马比例ps，交叉概率pc，迭代次数iter
←1[0091]
s42：随机初始化种群，计算每个个体的适应度函数f1、f2，并进行冲突检测与修正得到con，如果con＝1，则f1←
f1×
(1+pe),f2←
f2×
(1+pe)，其中pe为惩罚系数
[0092]
s43：根据适应度对所有个体进行非支配排序，并得到所有个体的帕累托集合选择种马并分配小马驹，形成马群
[0093]
s44：对所有种马进行非支配排序，得到种马的帕累托集合随机从中选择一匹种马的位置作为栖息地wh，从中随机选择一匹种马作为
[0094]
s45：计算tdr＝1-(1/maxtier)
×
iter，其中tdr为由1线性递减至0的系数，maxiter为算法的最大迭代次数
[0095]
s46：对于每一个马群ω，计算自适应机制向量
[0096]
其中，idx＝(ξ＝＝0)，ξ为由0和1组成的向量，与变量的维度相
同，和为[0,1]内服从均匀分布的随机向量，rand2为[0,1]内服从均匀分布的随机数，idx为满足(ξ＝＝0)条件的随机向量返回的索引
[0097]
s47：对于每一个小马驹如果rand5＞pc，小马驹放牧行为，更新公式为：否则，该小马驹离群并移至离群存档archive
[0098]
其中，为马群中的小马驹当前所在的位置。stallion
ω
为马群ω种马的位置。r是均匀随机数在范围[-2,2]内产生，π为圆周率取值为3.14，rand5为[0,1]内服从均匀分布的随机数
[0099]
s48：对archive中的小马驹进行交配，由双离群分段多点交叉机制得到子代小马驹的位置，将更新的子代小马驹分配给不同于其原先且存在空缺位置的马群，之后清空archive
[0100]
s49：对于每一个种马stallion
ω
，若果其进行莱维飞行，否则按照如下公式更新其位置：
[0101][0102]
其中，rand4为[0,1]内服从均匀分布的随机数。如果更新后种马的位置支配原先的位置，则
[0103]
s410：更新所有个体的适应度，并进行冲突检测与修复，得到最终适应度
[0104]
s411：对于每一个马群的每一匹小马驹，进行马群的竞选领导行为
[0105]
s412：iter
←
iter+1，如果iter≤maxiter，返回至步骤s44，否则跳至步骤s413
[0106]
s413：对所有个体进行非支配排序，得到输出
[0107]
与现有技术相比，本发明具有以下优点：
[0108]
(1)针对可跨层穿梭车存取系统的任务排序、设备调度和货位分配问题，建立以最小化总作业时间，最大化货架组综合稳定性为目标的集成优化数学模型，并设计一种改进的野马优化算法对问题进行了求解。
[0109]
(2)分别针对任务排序段、提升机选择段、穿梭车选择段和货位分配段设计编码与解码方法。引入非支配排序方法和莱维飞行策略，设计双离群分段多点交叉机制，增强算法的全局搜索和跳出局部最优的能力，从而平衡算法的探索与利用，提高算法的性能。
[0110]
(3)分析设备跨层执行任务带来的冲突问题，设计一种冲突检测与修正策略，并集成到算法中，以避免所获得的解集中设备运行出现冲突问题。
[0111]
(4)将提出的方法用于求解上述建立的可跨层穿梭车存取系统的数学模型，以得到任务排序、设备调度和货位分配集成优化方案。
附图说明
[0112]
图1为本发明的编码与解码示意图；
[0113]
图2为本发明方法流程图。
具体实施方式
[0114]
下面结合附图和具体实施例对本发明进行详细说明。本实施例以本发明技术方案为前提进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。
[0115]
实施例
[0116]
可跨层穿梭车系统的构成为：每条巷道由两排密集型货架组成，巷道首端配置两台复合提升机，对于单指令周期的出库作业，其中一台作为穿梭车提升机，另一台作为货物提升机。穿梭车和货箱可以通过复合提升机实现垂直方向上的运输。巷道配备有数台穿梭车，穿梭车可以在货架每层的轨道上水平移动。任务分配到某一巷道后，穿梭车提升机和货物提升机随之被确定。每层货架与提升机之间设有缓存区，用于缓存货箱。每种货物在不同巷道的货架上设有多个存储货位。系统接收到的订单被划分成不同的批次，每个批次包含确定数量的订单。批次订单上的出库货物在整个货架上的货位分布已知。
[0117]
本技术提出一种可跨层穿梭车存取系统调度决策方法，包括以下步骤：
[0118]
s1：以出库总作业时间最小化和货架综合稳定性最大化为目标建立可跨层穿梭车存取系统多目标集成优化数学模型，具体如下：
[0119]
多目标集成优化数学模型的目标函数包括：出库总作业时间和货架综合稳定性。出库总作业时间函数为：
[0120][0121]
其中为巷道lam的任务队列的完成时间，m为巷道编号，rm为巷道lam的任务队列长度。计算如下：
[0122][0123]
其中，表示货物提升机lcm执行巷道lam最后一个任务的起始时刻,表示货物提升机lcm执行巷道lam最后一个任务所占用的时间。lcm表示巷道lam配备的货位提升机。表示货物提升机lcm执行巷道lam的任务队列的第r个任务的起始时刻，计算如下：
[0124][0125]
其中，表示穿梭车执行任务到达出库货位层的时刻，表示巷道lam配备的第j台穿梭车，表示任务位于穿梭车的任务队列的第k个任务，表示lcm执行任务的结束时刻。
[0126]
对于非跨层任务，其中，表示执行任务的起始时刻。的计算公式为：
[0127]
[0128]
其中，表示执行任务的结束时刻。
[0129]
对于跨层出库任务，与穿梭车提升机lsm执行任务的起始时刻一致，lsm表示巷道lam配备的穿梭车提升机，表示任务位于穿梭车提升机lsm的任务队列的第f个任务，表示穿梭车提升机lsm执行任务的占用时间。的计算公式为：
[0130][0131]
其中，表示穿梭车提升机lsm执行任务的结束时刻。
[0132]
计算公式为：
[0133][0134]
其中，和分别表示竖直方向上穿梭车提升机从当前所在层到达穿梭车所在层的行程时间和从穿梭车所在层到达目标货位所在层的行程时间。t
ld2
表示穿梭车提升机装载穿梭车的时间，t
uld2
表示穿梭车提升机卸载穿梭车的时间。
[0135]
的计算公式中表示货物提升机lcm执行巷道lam的第r个任务所占用的时间，计算如下：
[0136][0137]
其中，和分别表示竖直方向上货物提升机从巷道i/o点到达目标货位所在层的行程时间和从目标货位所在层返回巷道i/o点的行程时间。t
ld3
表示货物提升机装载货物的时间，t
uld3
表示货物提升机卸载货物的时间。
[0138]
为穿梭车执行任务的占用时间，对于非跨层出库任务，计算如下：
[0139][0140]
表示水平方向上穿梭车在所在层i/o点与目标货位之间的单行程时间，t
ld1
表示穿梭车装载货箱的时间，t
uld1
表示穿梭车卸载货箱的时间。
[0141]
对于跨层出库任务，计算如下：
[0142][0143]
优选的，所述的巷道lam的货架组综合稳定性函数为：
[0144]
stm＝ε*ghm+γ*δmm[0145]
其中，ghm表示巷道lam的货架组的结构稳定性，δmm表示巷道lam的货架组的抗倾覆性，ε和γ分别为货架组的结构稳定性和抗倾覆性的指标权重，且满足ε+γ＝1。
[0146]
所述的竖直方向上提升机从货架z1层到达z2层的行程时间计算如下：
[0147][0148]
其中，h0表示货架单元的高度，z为货架的总层数，a
l
为提升机的加速度，v
l
为提升机的最大行驶速度。
[0149]
所述的水平方向上穿梭车从货架y1列到达y2列的行程时间计算如下：
[0150][0151]
其中，w0表示货架单元的宽度，c为货架的总列数，as为穿梭车的加速度，vs为穿梭车的最大行驶速度。
[0152]
货架综合稳定性最大化表示为：
[0153]
f2＝min(max(stm)),m＝1,2,
…
,m
[0154]
其中，stm表示巷道lam的货架组的综合稳定性，stm越大表示货架组综合稳定性越差。
[0155]
货架组综合稳定性函数为：
[0156]
stm＝ε*ghm+γ*δmm[0157]
其中，ghm表示巷道lam的货架组的结构稳定性，δmm表示巷道lam的货架组的抗倾覆性，ε和γ分别为货架组的结构稳定性和抗倾覆性的指标权重，且满足ε+γ＝1。
[0158]
货架组的结构稳定性函数为：
[0159][0160]
其中，z为货架的总层数，c为货架的总列数，x表示货架排号，y表示货架列号，z表示货架层号，q
xyz
表示货位占用状态，若[x,y,z]处的货位被占用，取1，否则，取0。m
xyz
表示存储在[x,y,z]货位处的货物的质量，h0表示货架单元的高度。
[0161]
货架组的抗倾覆性函数为：
[0162][0163]
所建立的数学模型约束条件为：
[0164][0165][0166]
[0167][0168][0169]
其中，n
im
为任务oi在巷道lam中的货位总数，当巷道lam中的第n个货位被选为任务i的出库货位时，取1；否则，取0。i表示批次任务总数。j表示每条巷道配备的穿梭车总数。当订单任务oi被巷道lam中的第j台穿梭车执行时，取1；否则，取0。当任务oi被货物提升机lcm执行时，取1；否则，取0。k
mj
表示穿梭车的任务队列长度。rm为巷道lam的任务队列长度。
[0170]
s2：设计一种改进的多目标野马优化算法，具体包括：
[0171]
s21：分别针对任务排序段、提升机选择段、穿梭车选择段和货位分配段设计编码与解码方法，具体如下：
[0172]
为解决任务调度和货位分配问题，每个解中包括四段：即任务排序段、提升机选择段、穿梭车选择段和货位分配段，每段编码的长度等于批次订单任务总数，其中，提升机和穿梭车选择段构成设备选择段。任务排序段采用随机键编码，设备选择段和货位分配采用实数编码。四段编码同一次序位置的编码为一组，且随着任务排序的变化一同变化。任务排序段的随机键数值范围为[0,1]，随机键越小的任务排序越靠前。提升机选择段的编码数值范围为[1,m+1)，穿梭车选择段的编码数值范围为[1,j+1)。其中，m为巷道数量，j为每个巷道配备的穿梭车的数量。对设备选择段的编码取整得到解码后的结果，如某一任务在提升机选择段的编码3.42取整后为3，则该任务由3#货物提升机完成出库，也表示该任务被添加到3#巷道的队列；在穿梭车选择段编码2.77取整后为2，则该任务由3#巷道的2#穿梭车完成搬运。货位分配段的编码数值范围为[1,n+1)，其中，n为该任务在被选巷道的货位数量。对编码数值取整解码，如4.09取整后为4，表示该任务分配的出库货位为被选巷道的货位集的4#货位。
[0173]
s22：引入非支配排序方法，重新定义种马、小马驹和栖息地的选择方法，并对马群的竞选领导行为进行修正，具体如下：
[0174]
对于马群初始化，将种群中所有个体进行非支配排序，划分得到不同集合种马优先从中选择，剩余数目的种马从其余集合的个体中随机选择。其余成员被随机分配给种马作为小马驹，形成不同马群。之后，马群的种马根据适应度选择。对所有种马进行非支配排序得到随机从中选择一匹种马作为栖息地。马群的竞选领导行为公式为：
[0175][0176]
其中，为马群中的小马驹当前所在的位置。stallion
ω
为马群ω种马的位置。
[0177]
s23：设计双离群分段多点交叉机制，改进马群的交配繁衍行为，增加算法的全局搜索能力。具体如下：
[0178]
成熟期的小马驹与来自不同马群的达到成熟期的小马驹离群后进行交配，产生两
个子代，分别随机加入到与原先不同的另外两个马群中。所述的分段多点交叉具体步骤如下：
[0179]
s231：任务排序段随机选择成员1的a个编码，与成员2相同位置的编码交换，1≤a≤i/2。其中，i为订单任务数。
[0180]
s232：提升机和穿梭车选择段随机选择成员1的b个邻位双编码，与成员2相邻位置的邻位双编码交换，1≤b≤i/4。
[0181]
s233：货位分配段随机选择成员1的g个邻位三编码，与成员2随机的g个邻位三编码交换，1≤g≤i/3。
[0182]
s24：引入莱维飞行策略，改进马群的引导行为，增加算法跳出局部最优的能力。
[0183]
莱维飞行策略包括：对所有的种马进行非支配排序得到帕累托集合从中随机选择一匹种马作为放弃向栖息地移动，改为莱维飞行。莱维飞行的具体如下：
[0184][0185][0186][0187]
其中α表示步长缩放因子，d表示个体位置的维度，r1和r2服从标准正态分布，通常设定β＝1.5，γ(x)＝(x-1)！。表示种马stallion
ω
移动后的位置。
[0188]
s3：分析系统执行任务过程中的设备冲突问题，提出一种冲突检测与修正策略并集成到步骤s2的算法中；
[0189]
记录穿梭车提升机和穿梭车的起始层和每次执行任务后的停留层。对解码后的个体进行冲突检测。同巷道配备的所有穿梭车，对于同一执行次序的任务，以下两类情况可能发生冲突：1)穿梭车a的任务目标货位层存在穿梭车b(a≠b)；2)存在至少两台穿梭车的任务目标货位层相同。以巷道为单位进行冲突检测。由分配的货位编号得到任务货位所在层，根据任务货位所在层和穿梭车当前所在层判断是否会出现冲突。对于检测出的冲突，通过更改任务的货位编号以修正个体编码，从而避免冲突。对于无法通过此方法修正的个体，进行适应度惩罚。
[0190]
冲突检测与修正策略的具体步骤如下：
[0191]
设1#巷道配有3台穿梭车c11、c12、c13
[0192]
s31：计算检测循环次数max_cycle＝最长穿梭车任务队列的任务数；初始化冲突标志con＝0,穿梭车c11、c12、c13所停留的层st1、st2、st3；令cycle
←1[0193]
s32：得到c11,c12,c13当前cycle的目标货位层ot1,ot2,ot3[0194]
s33：若ot1＝＝st2或ot1＝＝st3，则检索c11正在执行任务同巷道的剩余货位，随机选择其中1个货位取代原先货位，并更新ot1；重复此步骤直到不满足此条件；如果该任务
剩余货位数为0，则令con＝1,跳至步骤s37
[0195]
s34：若ot2＝＝st1或ot2＝＝st3或ot2＝＝ot1，则检索c12正在执行任务同巷道的剩余货位，随机选择其中1个货位取代原先货位，并更新ot2；重复此步骤直到不满足此条件；如果该任务剩余货位数为0，则令con＝1，跳至步骤s37
[0196]
s35：ot3＝＝st1或ot3＝＝st2或ot3＝＝ot1orot3＝＝ot2，则检索c13正在执行任务同巷道的剩余货位，随机选择其中1个货位取代原先货位，并更新ot3；重复此步骤直到不满足此条件；如果该任务剩余货位数为0，则令con＝1,跳至步骤s37
[0197]
s36：st1
←
ot1,st2
←
ot2,st3
←
ot3；令cycle
←
cycle+1，如果cycle≤max_cycle，返回至步骤s32
[0198]
s37：结束，输出con和修正的货位分配段
[0199]
s4：采用步骤s2和s3中的方法对步骤s1中的多目标集成优化模型进行求解以得到任务排序、设备调度和货位分配集成优化方案。具体步骤如下：
[0200]
s41：设置种群规模n，种马比例ps，交叉概率pc，迭代次数iter
←1[0201]
s42：随机初始化种群，计算每个个体的适应度函数f1、f2，并进行冲突检测与修正得到con，如果con＝1，则f1←
f1×
(1+pe),f2←
f2×
(1+pe)，其中pe为惩罚系数
[0202]
s43：根据适应度对所有个体进行非支配排序，并得到所有个体的帕累托集合选择种马并分配小马驹，形成马群
[0203]
s44：对所有种马进行非支配排序，得到种马的帕累托集合随机从中选择一匹种马的位置作为栖息地wh，从中随机选择一匹种马作为
[0204]
s45：计算tdr＝1-(1/maxtier)
×
iter，其中tdr为由1线性递减至0的系数，maxiter为算法的最大迭代次数
[0205]
s46：对于每一个马群ω，计算自适应机制向量
[0206]
其中，idx＝(ξ＝＝0)，ξ为由0和1组成的向量，与变量的维度相同，和为[0,1]内服从均匀分布的随机向量，rand2为[0,1]内服从均匀分布的随机数，idx为满足(ξ＝0)条件的随机向量返回的索引
[0207]
s47：对于每一个小马驹如果rand5＞pc，小马驹放牧行为，更新公式为：否则，该小马驹离群并移至离群存档archive
[0208]
其中，为马群中的小马驹当前所在的位置。stallion
ω
为马群ω种马的位置。r是均匀随机数在范围[-2,2]内产生，π为圆周率取值为3.14，rand5为[0,1]内服从均匀分布的随机数
[0209]
s48：对archive中的小马驹进行交配，由双离群分段多点交叉机制得到子代小马驹的位置，将更新的子代小马驹分配给不同于其原先且存在空缺位置的马群，之后清空archive
[0210]
s49：对于每一个种马stallion
ω
，若果其进行莱维飞行，否则按照如下公式更新其位置：
[0211][0212]
其中，rand4为[0,1]内服从均匀分布的随机数。如果更新后种马的位置支配原先的位置，则
[0213]
s410：更新所有个体的适应度，并进行冲突检测与修复，得到最终适应度
[0214]
s411：对于每一个马群的每一匹小马驹，进行马群的竞选领导行为
[0215]
s412：iter
←
iter+1，如果iter≤maxiter，返回至步骤s44，否则跳至步骤s413
[0216]
s413：对所有个体进行非支配排序，得到输出
[0217]
本实施例中，为测试模型和算法的有效性，需要利用案例进行测试。共生成20种测试案例，包括7中任务规模和4种巷道数目的组合。所有案例每排巷道配备3台多层穿梭车。每个货架20层，40列。各巷道存放货物的种类、位置及质量信息已知。如表1所示。
[0218]
表1
[0219][0220]
由于参数的抉择会直接影响算法的性能，因此需设定最佳的算法参数以确保获得的解的质量。改进的多目标野马优化算法包括2个重要参数：(1)种马比例ps；(2)交叉概率pc。采用田口法对参数选择实验，得到最佳性能参数组：ps＝0.25,pc＝0.25。为验证算法的有效性，将本技术的算法(imowho)与经典的多目标算法——多目标粒子群算法(mopso)算法对比。以表1中的20个案例作为对比实验。所有实验的种群规模统一设为300，算法运行时间设为任务数秒，每一实验案例运行20次。平均的cmetric指标如表2所示。
[0221]
表2
[0222][0223]
由表2对比可得，以上20组实验中，本技术所提出的方法所获得的帕累托解能够支配mopso的大多数解。因此本方法能够更有效的求解可跨层穿梭车存取系统的任务排序、设备调度和货位分配问题，并获得更优的解。
[0224]
为验证模型和算法的有效性，以某大型仓储运行中心作为实际案例，该仓储中心包含4排巷道，8座立体货架，每个巷道配备3台可跨层穿梭车，每座货架设有20层40列。批次订单任务数为50，仓库的货位信息已知。仓库及设备的参数如表3所示。利用本技术所提出的方法求解得到的解的目标值如表4所示。
[0225]
表3
[0226][0227]
表4
[0228][0229]
由表4可得，得到的帕累托解集中，作业时间位于331.795-479.221区间，货架综合稳定性位于8.514-33.378区间，两个目标都具有较大的优化空间与潜能。因此，本技术提出的模型和算法可以有效解决可跨层穿梭车存取系统的任务排序、设备调度与货位分配集成优化问题。
[0230]
综上，本技术提出了一种可跨层穿梭车存取系统调度决策方法，以出库总作业时间最小化和货架综合稳定性最大化为目标建立可跨层穿梭车存取系统集成优化数学模型，设计一种改进的多目标野马优化算法，引入非支配排序方法和莱维飞行策略，设计双离群分段多点交叉机制，增强算法的性能。提出一种冲突检测与修正策略以解决系统执行任务
过程中的设备冲突问题。利用设计的算法对不同规模的问题案例进行求解，并与求解相同问题的mopso算法进行对比，最后，以某一实际案例为例验证了所提出的集成优化模型与改进的多目标野马优化算法的有效性。

技术特征：
1.一种可跨层穿梭车存取系统调度决策方法，其特征在于，包括以下步骤：s1：以出库总作业时间最小化和货架综合稳定性最大化为目标建立可跨层穿梭车存取系统多目标集成优化数学模型；s2：设计一种改进的多目标野马优化算法；s3：分析系统执行任务过程中的设备冲突问题，提出一种冲突检测与修正策略并集成到步骤s2的算法中；s4：采用步骤s2和s3中的方法对步骤s1中的多目标集成优化模型进行求解以得到任务排序、设备调度和货位分配集成优化方案。2.根据权利要求1所述的一种可跨层穿梭车存取系统调度决策方法，其特征在于，所述多目标集成优化数学模型的目标函数包括：出库总作业时间和货架综合稳定性；所述出库总作业时间函数为：其中为巷道la
m
的任务队列的完成时间，m为巷道编号，r
m
为巷道la
m
的任务队列长度；所述货架综合稳定性最大化表示为：f2＝min(max(st
m
)),m＝1,2,
…
,m其中，st
m
表示巷道la
m
的货架组的综合稳定性，st
m
越大表示货架组综合稳定性越差；所述出库总作业时间函数中计算如下：其中，表示货物提升机lc
m
执行巷道la
m
最后一个任务的起始时刻,表示货物提升机lc
m
执行巷道la
m
最后一个任务所占用的时间；lc
m
表示巷道la
m
配备的货位提升机；所述计算中表示货物提升机lc
m
执行巷道la
m
的任务队列的第r个任务的起始时刻，计算如下：其中，表示穿梭车执行任务到达出库货位层的时刻，表示巷道la
m
配备的第j台穿梭车，表示任务位于穿梭车的任务队列的第k个任务，表示lc
m
执行任务的结束时刻；对于非跨层任务，其中，表示执行任务的起始时刻；的计算公式为：
其中，表示执行任务的结束时刻；对于跨层出库任务，对于跨层出库任务，与穿梭车提升机ls
m
执行任务的起始时刻一致，ls
m
表示巷道la
m
配备的穿梭车提升机，表示任务位于穿梭车提升机ls
m
的任务队列的第f个任务，表示穿梭车提升机ls
m
执行任务的占用时间；的计算公式为：其中，表示穿梭车提升机ls
m
执行任务的结束时刻；计算公式为：其中，和分别表示竖直方向上穿梭车提升机从当前所在层到达穿梭车所在层的行程时间和从穿梭车所在层到达目标货位所在层的行程时间；t
ld2
表示穿梭车提升机装载穿梭车的时间，t
uld2
表示穿梭车提升机卸载穿梭车的时间；所述计算中表示货物提升机lc
m
执行巷道la
m
的的第r个任务所占用的时间，计算如下：其中，和分别表示竖直方向上货物提升机从巷道i/o点到达目标货位所在层的行程时间和从目标货位所在层返回巷道i/o点的行程时间；t
ld3
表示货物提升机装载货物的时间，t
uld3
表示货物提升机卸载货物的时间；为穿梭车执行任务的占用时间，对于非跨层出库任务，计算如下：的占用时间，对于非跨层出库任务，计算如下：表示水平方向上穿梭车在所在层i/o点与目标货位之间的单行程时间，t
ld1
表示穿梭车装载货箱的时间，t
uld1
表示穿梭车卸载货箱的时间；对于跨层出库任务，计算如下：3.根据权利要求1所述的一种可跨层穿梭车存取系统调度决策方法，其特征在于，所述巷道la
m
的货架组综合稳定性函数为：st
m
＝ε*gh
m
+γ*δm
m
其中，gh
m
表示巷道la
m
的货架组的结构稳定性，δm
m
表示巷道la
m
的货架组的抗倾覆性，ε和γ分别为货架组的结构稳定性和抗倾覆性的指标权重，且满足ε+γ＝1；货架组的结构稳定性函数为：
其中，z为货架的总层数，c为货架的总列数，x表示货架排号，y表示货架列号，z表示货架层号，q
xyz
表示货位占用状态，若[x,y,z]处的货位被占用，取1，否则，取0；m
xyz
表示存储在[x,y,z]货位处的货物的质量，h0表示货架单元的高度；货架组的抗倾覆性函数为：4.根据权利要求3所述的一种可跨层穿梭车存取系统调度决策方法，其特征在于，所述步骤s2中的改进具体包括：s21：分别针对任务排序段、提升机选择段、穿梭车选择段和货位分配段设计编码与解码方法；s22：引入非支配排序方法，重新定义种马、小马驹和栖息地的选择方法，并对马群的竞选领导行为进行修正；s23：设计双离群分段多点交叉机制，改进马群的交配繁衍行为，增加算法的全局搜索能力；s24：引入莱维飞行策略，改进马群的引导行为，增加算法跳出局部最优的能力。5.根据权利要求4所述的一种可跨层穿梭车存取系统调度决策方法，其特征在于，所述步骤s22中，种马、小马驹和栖息地的选择方法为：对于马群初始化，将种群中所有个体划分为不同集合种马优先从中选择，剩余数目的种马从其余集合的个体中随机选择；其余成员被随机分配给种马作为小马驹，形成不同马群；之后，马群的种马根据适应度选择；对所有种马进行非支配排序得到随机从中选择一匹种马作为栖息地；马群的竞选领导行为公式为：其中，为马群中的小马驹当前所在的位置；stallion
ω
为马群ω种马的位置。6.根据权利要求4所述的一种可跨层穿梭车存取系统调度决策方法，其特征在于，所述步骤s23中的双离群分段多点交叉机制包括：成熟期的小马驹与来自不同马群的达到成熟期的小马驹离群后进行交配，产生两个子代，分别随机加入到与原先不同的另外两个马群中；所述分段多点交叉具体步骤如下：s231：任务排序段随机选择成员1的a个编码，与成员2相同位置的编码交换，1≤a≤i/2；其中，i为订单任务数；s232：提升机和穿梭车选择段随机选择成员1的b个邻位双编码，与成员2相邻位置的邻位双编码交换，1≤b≤i/4；s233：货位分配段随机选择成员1的g个邻位三编码，与成员2随机的g个邻位三编码交换，1≤g≤i/3。7.根据权利要求4所述的一种可跨层穿梭车存取系统调度决策方法，其特征在于，所述
步骤s24中的莱维飞行策略包括：对所有的种马进行非支配排序得到帕累托集合从中随机选择一匹种马作为放弃向栖息地移动，改为莱维飞行。8.根据权利要求4所述的一种可跨层穿梭车存取系统调度决策方法，其特征在于，所述步骤s3中，冲突检测与修正策略包括：记录穿梭车提升机和穿梭车的起始层和每次执行任务后的停留层；对解码后的个体进行冲突检测；同巷道配备的所有穿梭车，对于同一执行次序的任务，以下两类情况可能发生冲突：1)穿梭车a的任务目标货位层存在穿梭车b(a≠b)；2)存在至少两台穿梭车的任务目标货位层相同；以巷道为单位进行冲突检测；由分配的货位编号得到任务货位所在层，根据任务货位所在层和穿梭车当前所在层判断是否会出现冲突；对于检测出的冲突，通过更改任务的货位编号以修正个体编码，从而避免冲突；对于无法通过此方法修正的个体，进行适应度惩罚。9.根据权利要求8所述的一种可跨层穿梭车存取系统调度决策方法，其特征在于，所述的冲突检测与修正策略的具体步骤如下：设1#巷道配有3台穿梭车c11、c12、c13s31：计算检测循环次数max_cycle＝最长穿梭车任务队列的任务数；初始化冲突标志con＝0,穿梭车c11、c12、c13所停留的层st1、st2、st3；令cycle
←
1；符号
←
表示赋值；s32：得到穿梭车c11,c12,c13当前cycle的目标货位层ot1,ot2,ot3；s33：若ot1＝＝st2或ot1＝＝st3，则检索穿梭车c11正在执行任务同巷道的剩余货位，随机选择其中1个货位取代原先货位，并更新ot1；重复此步骤直到不满足此条件；如果该任务剩余货位数为0，则令con＝1,跳至步骤s37；s34：若ot2＝＝st1或ot2＝＝st3或ot2＝＝ot1，则检索穿梭车c12正在执行任务同巷道的剩余货位，随机选择其中1个货位取代原先货位，并更新目标货位层ot2；重复此步骤直到不满足此条件；如果该任务剩余货位数为0，则令con＝1，跳至步骤s37；s35：ot3＝＝st1或ot3＝＝st2或ot3＝＝ot
1 or ot3＝＝ot2，则检索穿梭车c13正在执行任务同巷道的剩余货位，随机选择其中1个货位取代原先货位，并更新目标货位层ot3；重复此步骤直到不满足此条件；如果该任务剩余货位数为0，则令con＝1,跳至步骤s37；s36：st1←
ot1,st2←
ot2,st3←
ot3；令cycle
←
cycle+1，如果cycle≤max_cycle，返回至步骤s32；s37：结束，输出冲突标志con和修正的货位分配段。10.根据权利要求9所述的一种可跨层穿梭车存取系统调度决策方法，其特征在于，所述的步骤s4中，求解方法的完整步骤如下：s41：设置种群规模n，种马比例ps，交叉概率pc，迭代次数iter
←
1；s42：随机初始化种群，计算每个个体的适应度函数f1、f2，并进行冲突检测与修正得到冲突标志con，如果con＝1，则f1←
f1×
(1+pe),f2←
f2×
(1+pe)，其中pe为惩罚系数；s43：根据适应度对所有个体进行非支配排序，并得到所有个体的帕累托集合选择种马并分配小马驹，形成马群；s44：对所有种马进行非支配排序，得到种马的帕累托集合随机从中选择一匹种马的位置作为栖息地wh，从中随机选择一匹种马作为s45：计算tdr＝1-(1/maxtier)
×
iter，其中tdr为由1线性递减至0的系数，maxiter为
算法的最大迭代次数；s46：对于每一个马群ω，计算自适应机制向量其中，idx＝(ξ＝＝0)，ξ为由0和1组成的向量，与变量的维度相同，和为[0,1]内服从均匀分布的随机向量，rand2为[0,1]内服从均匀分布的随机数，idx为满足(ξ＝＝0)条件的随机向量返回的索引；s47：对于每一个小马驹如果rand5＞pc，小马驹放牧行为，更新公式为：否则，该小马驹离群并移至离群存档archive；其中，其中为马群中的小马驹当前所在的位置；stallion
ω
为马群ω种马的位置；r是均匀随机数在范围[-2,2]内产生，π为圆周率取值为3.14，rand5为[0,1]内服从均匀分布的随机数；s48：对archive中的小马驹进行交配，由双离群分段多点交叉机制得到子代小马驹的位置，将更新的子代小马驹分配给不同于其原先且存在空缺位置的马群，之后清空archive；s49：对于每一个种马stallion
ω
，若果其进行莱维飞行，否则按照如下公式更新其位置：其中，rand4为[0,1]内服从均匀分布的随机数；如果更新后种马的位置支配原先的位置，则s410：更新所有个体的适应度，并进行冲突检测与修复，得到最终适应度；s411：对于每一个马群的每一匹小马驹，进行马群的竞选领导行为；s412：iter
←
iter+1，如果iter≤maxiter，返回至步骤s44，否则跳至步骤s413；s413：对所有个体进行非支配排序，得到输出

技术总结
本发明涉及一种可跨层穿梭车存取系统调度决策方法，其包括以下步骤：S1：以出库总作业时间最小化和货架综合稳定性最大化为目标建立可跨层穿梭车存取系统集成优化数学模型；S2：设计一种改进的多目标野马优化算法；S3：分析系统执行任务过程中的设备冲突问题，提出一种冲突检测与修正策略并集成到步骤S2的算法中；S4：采用步骤S2和S3中的方法对步骤S1中的多目标集成优化模型进行求解。与现有技术相比，此方法同时解决了可跨层穿梭车存取系统的任务排序、设备调度和货位分配问题，以得到货架综合稳定性较好，批次订单出库作业时间较短，且设备运行无冲突的帕累托解集方案以供管理者决策。理者决策。理者决策。


技术研发人员：徐立云 徐准 韦烽 商港
受保护的技术使用者：同济大学
技术研发日：2023.06.12
技术公布日：2023/9/14