一种基于基因型遗传算法的纸箱混合码垛方法与流程

1.本发明属于码垛技术领域，具体涉及一种基于基因型遗传算法的纸箱混合码垛方法。

背景技术：

2.目前在仓储物流按订单出库作业中，一般采用人工码垛或机器人码垛。在物流仓储场景中，混合纸箱码垛机器人有着大量的应用需求，可以代替人工搬运，可以大大提升生产效率。但是对于乱序到来的、多种尺寸规格的箱子，如何用机器人实现自动、高效的码垛，节省人力的同时提升物流周转效率，是物流仓储自动化的一个难点问题。其核心是求解装箱问题(bin packing problem，bpp)这一经典的np难题，即为每一个纸箱规划在容器中的摆放位置，以最大化容器的空间利用率。由于每个订单需要的货物种类及数量都不相同，无法使用示教的方式完成混合码垛。
3.针对上述问题，需要有一套算法能够根据订单中货物的尺寸、数量、重量、承重等信息自动规划货物的出库顺序及码垛策略，用来引导机器人自动码垛，从而实现真正意义上的无人化仓储。

技术实现要素：

4.本发明的目的是针对上述现有技术的不足，而提供一种基于基因型遗传算法的纸箱混合码垛方法，以解决无人化仓库按订单出库时各个商品的出库及码放问题。
5.为解决上述技术问题，本发明采用的一个技术方案是：提供一种基于基因型遗传算法的纸箱混合码垛方法，包括如下步骤：
6.s1、根据订单信息，将每个纸箱作为一个基因以i表示，将所有纸箱的线性排列作为遗传算法的基因型以p表示，则初代个体为：p(0)＝{i0,i1,i2,
…
,in}，n为纸箱个数；
7.上述基因i＝{l,w,h,t,wt,m}，其中：l表示纸箱的长；w表示纸箱的宽；h表示纸箱的高；t表示纸箱的重量；wt表示纸箱能够承受的重量；m表示纸箱的摆放姿态m＝{0或1}，0表示纸箱长度方向与托盘坐标系的x方向平行，1表示纸箱长度方向与托盘坐标系的x方向垂直；
8.s2、将p(0)内的各个基因i
x
随机交叉排列以产生足够多的子代个体p(1)m，m为设定值,即子代个体的个数；
9.s3、将纸箱的摆放姿态m作为突变项，以托盘利用率u最大为遗传个体评价标准，以设定的终止判断条件进行遗传操作，以最终得到最优的纸箱抓取顺序；
10.s4、机器人按照上述最优纸箱抓取顺序依次抓取对应的纸箱，按照设定的摆放规则将其摆放在托盘的对应位置。
11.在本发明另一个实施例中，所述步骤s2中设定的终止判断条件为：设定的托盘利用率u或者设定的遗传代数。
12.在本发明另一个实施例中，托盘利用率u的计算公式为：
[0013][0014]
其中，vi为各个纸箱的体积；s为托盘允许放置纸箱的最大体积；n为本次订单所使用托盘的总数。
[0015]
在本发明另一个实施例中，所述步骤s3中设定的摆放规则如下：
[0016]
s31、以托盘一角点建立直角坐标系，以该角点作为纸箱码垛的起始点,每个纸箱设定一个摆放基准点q，将第一个纸箱按照规则摆放于坐标系起始点并产生3个新的待选摆放点；
[0017]
s32、依次抓取下一个纸箱，将其摆放基准点q按照设定比对原则依次与托盘上的待选摆放点进行比较，判断是否满足摆放要求；如果满足，则将该纸箱放置于该托盘的对应位置上同时产生3个新的待选摆放点；如果不满足，继续寻下一个摆放点，直至满足，或全部摆放点都不满足为止；若全部摆放点都不满足，则停止当前托盘的码放，重新出具一个托盘并将当前纸箱放置于新的托盘之上，同时产生3个新的摆放点；
[0018]
s33、重复上一步骤，直至所有纸箱都被码放于托盘之上。
[0019]
在本发明另一个实施例中，所述步骤s32中设定比对原则为：按照从低到高，从远到近的原则依次判断该纸箱能否摆放到该待选摆放点位置。
[0020]
在本发明另一个实施例中，所述步骤s32中摆放要求如下：
[0021]
(1)纸箱悬空率k不能小于设定值：k＝纸箱底面支撑面积/纸箱底面面积；
[0022]
(2)是否与其他纸箱发生干涉：当纸箱摆放在该摆放点时，不能与已经摆放的其它纸箱发生干涉；
[0023]
(3)是否超出了下方纸箱的承重：当纸箱摆放到该摆放点时，其下方纸箱的承受重量不能超过其所能承受的最大重量；
[0024]
(4)是否超出了托盘范围：纸箱摆放到该待选摆放点时，不能超出托盘的长、宽、高范围。
[0025]
在本发明另一个实施例中，纸箱悬空率的设定值为0.8。
[0026]
本发明的有益效果是：本发明是在标准遗传算法的基础上，提出了一种适用于混合码垛算法的基因型遗传算法，以获得纸箱混合码垛中各个纸箱码放顺序、位置及姿态的最优解，该方法继承了遗传算法快速求解最优解的特点，将每个纸箱看作一个遗传因子进行遗传，并根据订单有数量及种类要求的特点，采用自相交的方式进行遗传寻优。该方法能够解决在无人化仓库中，机器人无法根据订单信息，自动规划纸箱码放位置的问题。大大提高了机器人的智能化程度。
附图说明
[0027]
图1是本发明基于基因型遗传算法的纸箱混合码垛方法的流程图；
[0028]
图2是本发明基因型遗传算法的流程图；
[0029]
图3是托盘角点建立的直角坐标系图；
[0030]
图4是纸箱的摆放基准点及产生的待选摆放点示意图。
具体实施方式
[0031]
为了便于理解本发明，下面结合附图和具体实施例，对本发明进行更详细的说明。附图中给出了本发明的较佳的实施例。但是，本发明可以以许多不同的形式来实现，并不限于本说明书所描述的实施例。相反地，提供这些实施例的目的是使对本发明的公开内容的理解更加透彻全面。
[0032]
需要说明的是，除非另有定义，本说明书所使用的所有的技术和科学术语与属于本发明的技术领域的技术人员通常理解的含义相同。在本发明的说明书中所使用的术语只是为了描述具体的实施例的目的，不是用于限制本发明。本说明书所使用的术语“和/或”包括一个或多个相关的所列项目的任意的和所有的组合。术语“中心”、“底部”“顶部”“内”“外”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅仅是为便于描述本发明和简化描述，而不是指示或暗指所指的部件必须具有特定的方位、为特定的方位构造和操作，因而不能理解为对本发明保护内容的限制。
[0033]
如图1所示为本发明基于基因型遗传算法的纸箱混合码垛方法的流程图，由图可知，该方法包括如下步骤：
[0034]
s1、根据订单信息，将每个纸箱看做一个个体，每个个体包含的信息包括长、款、高、自重、承重、摆放姿态等，在本实施例中，将每个纸箱作为一个基因以i表示，i＝{l,w,h,t,wt,m}，其中：l表示纸箱的长；w表示纸箱的宽；h表示纸箱的高；t表示纸箱的重量；wt表示纸箱能够承受的重量；m表示纸箱的摆放姿态m＝{0或1}，0表示纸箱长度方向与托盘坐标系的x方向平行，1表示纸箱长度方向与托盘坐标系的x方向垂直；
[0035]
将所有纸箱的线性排列作为遗传算法的基因型以p表示，则初代个体为：p(0)＝{i0,i1,i2,
…
,in}，n为纸箱个数；
[0036]
s2、按照标准遗传算法，将p(0)内的各个基因i
x
随机交叉排列以产生足够多的子代个体p(1)m，m为设定值,即子代个体的个数；
[0037]
s3、将纸箱的摆放姿态m作为突变项，以托盘利用率u最大为遗传个体评价标准，以设定的终止判断条件进行遗传操作，以最终得到最优的纸箱抓取顺序；
[0038]
s4、机器人按照上述最优纸箱抓取顺序依次抓取对应的纸箱，按照设定的摆放规则将其摆放在托盘的对应位置。
[0039]
本实施例中的基因型遗传算法的流程如图2所示，其过程如下：将纸箱按照订单线性排列，每个纸箱作为一个基因，采用自相交的方式进行遗传，将纸箱的摆放姿态作为突变项，每次从子代及父代中寻托盘利用率最大的个体，当遗传到指定代数或者达到最大设定的托盘利用率时，停止并输出结果，指导机器人完成混合码垛。
[0040]
优选地，本发明是以托盘利用率作为个体适应度评定方法，每次选择托盘利用率最高的个体进行遗传。
[0041]
步骤s2中设定的终止判断条件为：设定的托盘利用率u或者设定的遗传代数，其中托盘利用率u的计算公式为：
[0042]
[0043]
其中，vi为各个纸箱的体积；s为托盘允许放置纸箱的最大体积；n为本次订单所使用托盘的总数。
[0044]
优选地，步骤s3中设定的摆放规则如下：
[0045]
s31、以托盘一角点建立直角坐标系，如图3所示，以该角点o作为纸箱码垛的起始点,每个纸箱设定一个摆放基准点q，如图4所示，将第一个纸箱按照规则摆放于坐标系起始点并产生3个新的待选摆放点，如图4所示的点1、2、3；
[0046]
s32、依次抓取下一个纸箱，将其摆放基准点q按照设定比对原则依次与托盘上的待选摆放点进行比较，判断是否满足摆放要求；如果满足，则将该纸箱放置于该托盘的对应位置上同时产生3个新的待选摆放点；如果不满足，继续寻下一个摆放点，直至满足，或全部摆放点都不满足为止；若全部摆放点都不满足，则停止当前托盘的码放，重新出具一个托盘并将当前纸箱放置于新的托盘之上，同时产生3个新的摆放点；
[0047]
优选地，本实施例中设定比对原则为：按照从低到高，从远到近的原则依次判断该纸箱能否摆放到该待选摆放点位置。
[0048]
本实施例设定的摆放要求如下：
[0049]
(1)纸箱悬空率k不能小于设定值0.8，即k＝纸箱底面支撑面积/纸箱底面面积》0.8；
[0050]
(2)是否与其他纸箱发生干涉：当纸箱摆放在该摆放点时，不能与已经摆放的其它纸箱发生干涉；
[0051]
(3)是否超出了下方纸箱的承重：当纸箱摆放到该摆放点时，其下方纸箱的承受重量不能超过其所能承受的最大重量；
[0052]
(4)是否超出了托盘范围：纸箱摆放到该待选摆放点时，不能超出托盘的长、宽、高范围。
[0053]
s33、重复上一步骤，直至所有纸箱都被码放于托盘之上。
[0054]
本方法能够在自动生成多种纸箱混合码放于托盘上时，自动计算纸箱码放位置及姿态，主要用于解决无人化仓库按订单出库时各个商品的出库及码放，用于引导机器人实现自动码垛的过程，能在解决物流仓储中外包装为纸箱类的商品按订单出库时，自动引导机器人实现混合码垛任务。
[0055]
以上所述仅为本发明的实施例，并非因此限制本发明的专利范围，凡是利用本发明说明书及附图内容所作的等效结构变换，或直接或间接运用在其他相关的技术领域，均包括在本发明的专利保护范围内。

技术特征：

1.一种基于基因型遗传算法的纸箱混合码垛方法，其特征在于，包括如下步骤：s1、根据订单信息，将每个纸箱作为一个基因以i表示，将所有纸箱的线性排列作为遗传算法的基因型以p表示，则初代个体为：p(0)＝{i0,i1,i2,
…
,i
n
}，n为纸箱个数；上述基因i＝{l,w,h,t,wt,m}，其中：l表示纸箱的长；w表示纸箱的宽；h表示纸箱的高；t表示纸箱的重量；wt表示纸箱能够承受的重量；m表示纸箱的摆放姿态m＝{0或1}，0表示纸箱长度方向与托盘坐标系的x方向平行，1表示纸箱长度方向与托盘坐标系的x方向垂直；s2、将p(0)内的各个基因i
x
随机交叉排列以产生足够多的子代个体p(1)
m
，m为设定值,即子代个体的个数；s3、将纸箱的摆放姿态m作为突变项，以托盘利用率u最大为遗传个体评价标准，以设定的终止判断条件进行遗传操作，以最终得到最优的纸箱抓取顺序；s4、机器人按照上述最优纸箱抓取顺序依次抓取对应的纸箱，按照设定的摆放规则将其摆放在托盘的对应位置。2.根据权利要求1所述的基于基因型遗传算法的纸箱混合码垛方法，其特征在于，所述步骤s2中设定的终止判断条件为：设定的托盘利用率u或者设定的遗传代数。3.根据权利要求2所述的基于基因型遗传算法的纸箱混合码垛方法，其特征在于，托盘利用率u的计算公式为：其中，v
i
为各个纸箱的体积；s为托盘允许放置纸箱的最大体积；n为本次订单所使用托盘的总数。4.根据权利要求2所述的基于基因型遗传算法的纸箱混合码垛方法，其特征在于，所述步骤s3中设定的摆放规则如下：s31、以托盘一角点建立直角坐标系，以该角点作为纸箱码垛的起始点,每个纸箱设定一个摆放基准点q，将第一个纸箱按照规则摆放于坐标系起始点并产生3个新的待选摆放点；s32、依次抓取下一个纸箱，将其摆放基准点q按照设定比对原则依次与托盘上的待选摆放点进行比较，判断是否满足摆放要求；如果满足，则将该纸箱放置于该托盘的对应位置上同时产生3个新的待选摆放点；如果不满足，继续寻下一个摆放点，直至满足，或全部摆放点都不满足为止；若全部摆放点都不满足，则停止当前托盘的码放，重新出具一个托盘并将当前纸箱放置于新的托盘之上，同时产生3个新的摆放点；s33、重复上一步骤，直至所有纸箱都被码放于托盘之上。5.根据权利要求4所述的基于基因型遗传算法的纸箱混合码垛方法，其特征在于，所述步骤s32中设定比对原则为：按照从低到高，从远到近的原则依次判断该纸箱能否摆放到该待选摆放点位置。6.根据权利要求5所述的基于基因型遗传算法的纸箱混合码垛方法，其特征在于，所述步骤s32中摆放要求如下：(1)纸箱悬空率k不能小于设定值：k＝纸箱底面支撑面积/纸箱底面面积；
(2)是否与其他纸箱发生干涉：当纸箱摆放在该摆放点时，不能与已经摆放的其它纸箱发生干涉；(3)是否超出了下方纸箱的承重：当纸箱摆放到该摆放点时，其下方纸箱的承受重量不能超过其所能承受的最大重量；(4)是否超出了托盘范围：纸箱摆放到该待选摆放点时，不能超出托盘的长、宽、高范围。7.根据权利要求6所述的基于基因型遗传算法的纸箱混合码垛方法，其特征在于，纸箱悬空率的设定值为0.8。

技术总结

本发明公开了一种基于基因型遗传算法的纸箱混合码垛方法，是在标准遗传算法的基础上，提出了一种适用于混合码垛算法的基因型遗传算法，以获得纸箱混合码垛中各个纸箱码放顺序、位置及姿态的最优解，该方法继承了遗传算法快速求解最优解的特点，将每个纸箱看作一个遗传因子进行遗传，并根据订单有数量及种类要求的特点，采用自相交的方式进行遗传寻优。该方法能够解决在无人化仓库中，机器人无法根据订单信息，自动规划纸箱码放位置的问题。大大提高了机器人的智能化程度。提高了机器人的智能化程度。提高了机器人的智能化程度。