本发明涉及物流和仓储工业应用领域，尤其是一种基于遗传算法的适配装箱方法、装置、设备和存储介质。

背景技术：

随着电商的快速发展，消费者订单以及物品数量增多，对物流的智能化装箱需求也越来越多。在物流打包装箱过程中，经常会出现单个消费者订单物品超出单个装箱容器的装载量，需要进行多箱组合打包情况，而物品打包作为物流运输的重要环节，因此智能化装箱对整个物流服务体验影响重大。但是，实际中多箱组合打包相对单箱打包，其复杂度高、对人工依赖较大，容易出现的问题有：(1)纸箱空间利用率较低，浪费空间资源；(2)占用的纸箱数量超出实际所需，浪费物质资源；(3)装箱结果不满足配送要求时，需要重复打包，浪费人力资源。

因此，对需要进行同时打包的物品进行适配装箱是物流打包过程中亟待解决的问题。目前针对该问题提出装箱算法，如申请号为201410798189.3的发明专利《基于三维移动模式序列与密母算法的三维装箱方法》和申请号为201711398819.8的发明《解决三维装箱问题的三叉树规划计算方法》，提出采用三维装箱中x，y，z构造三叉树方法的装箱方案，这些算法提供了三维装箱问题的建模和算法实现方案，主要解决的是单箱物品的快速装箱问题，不适用多容器动态适配，也并没有提出在需要进行同时打包的物品进行多容器装箱时，根据待装箱物品进行动态适配装箱容器的问题的解决方法。

技术实现要素：

本发明旨在至少在一定程度上解决相关技术中的技术问题之一。为此，本发明的一个目的是提供一种基于遗传算法的适配装箱方法、装置、设备和存储介质。

本发明所采用的技术方案是：

一种基于遗传算法的适配装箱方法，包括步骤：

s1：随机产生多个装箱方案染色体，所述多个装箱方案染色体组成初始种群；

s2：对所述初始种群中每个装箱方案染色体进行装箱适配过程，获得父代种群，并计算父代种群中每个装箱方案染色体的适应度，并保留适应度最高的装箱方案染色体；

s3：对父代种群中装箱方案染色体进行交叉进化，并和所述父代种群中适应度最高的装箱方案染色体组合得到第一代进化种群；

s4：对所述第一代进化种群进行变异，生成第一代变异种群，计算所述第一代变异种群中每个装箱方案染色体的适应度，选择所述第一代变异种群中适应度最高的装箱方案染色体为第一代近似最优装箱方案染色体。

进一步地，还包括步骤：

s5：对近似最优装箱方案染色体进行进化迭代，具体为：将所述步骤s4中得出的近似最优装箱方案染色体作为所述步骤s1中初始种群中的其中一个装箱方案染色体，重复执行步骤s1至s4，进行进化迭代得到下一代近似最优方案；

s6，当迭代次数达到预设迭代次数，则将最后一代近似最优装箱方案染色体输出。

进一步地，步骤s1中所述装箱方案染色体包括待装箱物品的装箱顺序参数、放置方式参数和推荐容器参数；

进一步地，还包括步骤：

执行步骤s1前，根据第一约束条件筛选待装箱物品和可用的容器；

所述第一约束条件包括：待装箱物品尺寸小于运输渠道的最大尺寸和可用容器尺寸小于运输渠道的最大尺寸。

进一步地，所述步骤s2中对所述初始种群中每个装箱方案染色体进行装箱适配过程具体包括步骤：

s21：根据装箱顺序进行待装箱物品装箱，判断容器尺寸是否匹配，如果匹配将待装箱物品放入容器中，并进行三空间划分及空间合并；

s22：如果容器尺寸不适配，则根据推荐容器初始化新的空间，直至容器尺寸适配；

s23：判断待装箱物品是否全部装入容器中：

如果没有，则按照装箱顺序执行步骤s21至s23继续装箱，直至所有待装箱物品全部装入容器中；

如果已经全部装入容器中，则判断该装箱方案染色体的装箱适配过程完成。

进一步地，所述适应度计算方法具体为：

cost＝1-(m+waste)/(n+1)

waste＝1-vn/vuse

其中，cost为装箱方案适应度，m为容器数量，waste为空间浪费率，n为待装箱物品数量，vn为待装物品的总体积，vuse为使用容器的总体积。

进一步地，所述步骤s3对父代种群中装箱方案染色体进行交叉进化得到第一代进化种群具体为：

对父代种群中的装箱方案染色体按照顺序进行两两装箱方案染色体交叉进化形成多个第一代装箱方案染色体，多个第一代装箱方案染色体组成第一代进化种群；

所述两两装箱方案染色体交叉进化指：在两个进行交叉进化的装箱方案染色体中，随机选择一个装箱方案染色体的装箱顺序和推荐容器，然后按顺序交叉两个装箱方案染色体的放置方式，得到进化后的装箱方案染色体。

进一步地，所述步骤s4中所述变异具体为：

s41：按照预设变异概率选择需要进行变异的装箱方案染色体；

s42：在所述需要变异的装箱方案染色体中，随机改变装箱顺序参数，并根据改变后的装箱顺序参数对应改变放置方式参数或推荐容器参数。

进一步地，所述步骤s42具体为：

在所述需要变异的装箱方案染色体中，选择两个待装箱物品，调换其装箱顺序，同时分别随机生成其放置方式和推荐容器。

另一方面，本发明还提供一种基于遗传算法的适配装箱装置，包括

初始种群生成模块，用于随机产生多个装箱方案染色体，所述多个装箱方案染色体组成初始种群；

装箱适配模块，用于对初始种群生成模块输出的初始种群中每个装箱方案染色体进行装箱适配过程，获得父代种群，并计算父代种群中每个装箱方案染色体的适应度，并保留适应度最高的装箱方案染色体；

进化模块，用于对装箱适配模块输出的父代种群中装箱方案染色体进行交叉进化，并和所述父代种群中适应度最高的装箱方案染色体组合得到第一代进化种群，其输入为装箱适配模块的输出；

变异模块，用于对进化模块输出的第一代进化种群进行变异，生成第一代变异种群，计算所述第一代变异种群中每个装箱方案染色体的适应度，并选择所述第一代变异种群中适应度最高的装箱方案染色体为第一代近似最优装箱方案染色体；

进一步地，还包括：

迭代模块，用于对近似最优装箱方案染色体进行进化迭代，具体为：将变异模块中得出的近似最优装箱方案染色体作为初始种群生成模块中初始种群中的其中一个装箱方案染色体，重复执行将初始种群生成模块的输出送至装箱适配模块，装箱适配模块的输出送至进化模块，进化模块的输出送至变异模块，进行进化迭代得到下一代近似最优方案，当迭代次数达到预设迭代次数，则将最后一代近似最优装箱方案染色体输出。

另一方面，本发明还提供一种基于遗传算法的适配装箱操作的控制设备，包括：

至少一个处理器；以及，

与所述至少一个处理器通信连接的存储器；其中，

所述存储器存储有可被所述至少一个处理器执行的指令，所述指令被所述至少一个处理器执行，以使所述至少一个处理器能够执行任一项所述的基于遗传算法的适配装箱方法。

另一方面，本发明还提供一种计算机可读存储介质，所述计算机可读存储介质存储有计算机可执行指令，所述计算机可执行指令用于使计算机执行任一项所述的基于遗传算法的适配装箱方法。

本发明的有益效果是：

本发明采用遗传算法，根据待装箱物品的装箱顺序参数、放置方式参数和推荐容器参数组合成装箱方案，即遗传算法的染色体，进行染色体的进化变异迭代过程，生成近似最优的装箱方案，解决需要同时装箱时候，根据待装箱物品动态适配装箱容器的问题，当单个容器空间不足时，支持使用多个容器完成一次装箱过程，即在于组合使用最少的装箱容器完成固定量物品的装载，因此，本发明针对客户定量的物品进行装箱时，当单个容器不能装完所有待装箱物品时，通过遗传算法结合容器数量与空间利用率，筛选出使用容器最少且空间利用率最高的最佳容器组合装箱方案，完成物品装箱，减少资源浪费。

另一方面，本发明在实际物流打包应用场景中，可以提前根据客户货物计算装箱方案并准备装箱资源，缩短打包出库时间，使得物流打包更高效，并且提前根据客户货物结算打包资源费用，避免出库后加收，给客户提供更优质的服务。

本发明可广泛应用于各种物流打包系统。

附图说明

图1是本发明一种实施例的基于遗传算法的适配装箱方法流程图；

图2a～图2f是本发明一种实施例的基于遗传算法的适配装箱方法中放置方式示意图；

图3是本发明一种实施例的基于遗传算法的适配装箱方法中筛选可用容器流程图；

图4是本发明一种实施例的基于遗传算法的适配装箱方法中装箱适配流程图；

图5是本发明一种实施例的基于遗传算法的适配装箱方法中三空间划分示意图；

图6a～图6c是本发明一种实施例的基于遗传算法的适配装箱方法中空间合并示意图；

图7是本发明一种实施例的基于遗传算法的适配装箱方法中交叉进化流程图；

图8是本发明一种实施例的基于遗传算法的适配装箱方法中变异流程图；

图9是本发明一种实施例的基于遗传算法的适配装箱装置框图。

具体实施方式

需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。

实施例一：

如图1所示，为实施例一的基于遗传算法的适配装箱方法流程图，

包括步骤s1：生成初始种群。具体为：随机产生多个装箱方案染色体，并且多个装箱方案染色体组成初始种群；s2：装箱适配获得父代种群，具体为：对初始种群中每个装箱方案染色体进行装箱适配过程，获得父代种群，并计算父代种群中每个装箱方案染色体的适应度，并保留适应度最高的装箱方案染色体；s3：交叉进化获得第一代进化种群，具体为：对父代种群中装箱方案染色体进行交叉进化，并和父代种群中适应度最高的装箱方案染色体组合得到第一代进化种群；s4：种群变异获得第一代近似最优装箱方案，具体为：对第一代进化种群进行变异，生成第一代变异种群，计算第一代变异种群中每个装箱方案染色体的适应度，选择第一代变异种群中适应度最高的装箱方案染色体为第一代近似最优装箱方案染色体；s5：进化迭代输出近似最优装箱方案，具体为：对近似最优装箱方案染色体进行进化迭代，具体为：将步骤s4中得出的近似最优装箱方案染色体作为步骤s1中初始种群中的其中一个装箱方案染色体，重复执行步骤s1至s4，进行进化迭代得到下一代近似最优方案，当迭代次数达到预设迭代次数，则将最后一代近似最优装箱方案染色体输出。

其中，在该实施例中，还包括执行步骤s1前，根据第一约束条件筛选待装箱物品和可用的容器，第一约束条件包括：待装箱物品尺寸小于运输渠道的最大尺寸和可用容器尺寸小于运输渠道的最大尺寸，本实施例中将带装箱物体的外形看作是一种规则的具有长宽高的长方体。

约束情况有两种：当待装箱物品的尺寸超出运输渠道的最大尺寸限制，则不能运输；当仓库可用于装箱的容器(如纸箱)尺寸超出运输渠道的最大尺寸限制，则不采用该尺寸的容器装箱。

如图2a～图2f所示，是本实施例中放置方式的示意图，图中示出了6中放置方式，其中坐标系x-y-z，待装箱物品的左下角位于坐标系原点的位置，图2a～图2f分别表示六种不同的放置方式，分别为：

g1＝[长宽面朝上，横放]；g2＝[长高面朝上，横放]；g3＝[宽高面朝上，横放]；g4＝[长宽面朝上，直放]；g5＝[长高面朝上，直放]；g6＝[宽高面朝上，直放]。

如图3所示，是本实施例中筛选可用容器流程图，在满足第一约束条件的运输渠道最大尺寸限制的情况下，在可使用的装箱容器中，筛选出每个待装箱物品可使用的装箱容器的过程。

流程具体如下：

首先判断是否符合第一约束条件，当不符合第一约束条件的情况下提示装箱方案获取失败，在满足第一约束条件的情况时，提取可用容器的规格，即本次装箱过程可以使用的不同容器的规格列表，然后遍历待装箱物品，即对每一个待装箱物品判断每一个可用容器是否与之匹配，匹配指：待装箱物品能够放置在该容器中，记录每个待装箱物品的可用容器列表，如果待装箱物品找不到匹配的容器，则提示装箱方案获取失败，遍历完成后，筛选每个待装箱物品可使用的装箱容器的过程结束。

经过筛选可用容器的过程可以得到每个待装箱物品的可用容器列表，在本实施例中，匹配方法是将每个待装箱物品和可用容器的长度，宽度和高度按数值比，小到大排序后，例如待装箱物品w1的尺寸的排序后三个数值，与容器c1尺寸排序后的三个值，一一对应做比较，若是待装箱物品w1的长宽高数值全部小于容器c1的长宽高数值，则待装箱物品w1与容器c1匹配，将容器c1放入带装箱物体w1的可用容器列表中。

本实施例中装箱方案染色体组成部分包括待装箱物品的：装箱顺序参数、放置方式参数、推荐容器参数作为染色体组成部分。

根据装箱方案染色体的组成部分进行装箱方案染色体的初始化，染色体的长度即待装箱物品的数量，假设待装箱物品的数量为n，初始化步骤如下：

(1)待装箱物品的装箱顺序参数：随机生成长度为n的随机数组，并进行随机排序，获取排序后数据的索引，即可确定本条装箱方案染色体中待装箱物品的装箱顺序。

(2)放置方式参数：为每一个待装箱物品在6种放置方式种随机选择一种放置方式。

(3)推荐容器参数：筛选可用容器的过程完成后，即得到每个待装箱物品的可用容器列表，按上述装箱物品顺序，随机获取每一个待装箱物品的可用容器列表中的一个容器，作为此待装箱物品的推荐容器。

确定装箱顺序以及每个待装箱物品放置方式和推荐容器参数后，该装箱方案染色体初始化完毕。

本实施例中遗传算法初始种群由多个装箱方案染色体组成，随机产生多个装箱方案染色体，多个装箱方案染色体组成初始种群，通常取值为待装箱物品数量的10倍，对初始种群中每个装箱方案染色体进行装箱适配过程，其中装箱适配过程包括步骤：

s21：根据装箱顺序进行待装箱物品装箱，判断容器尺寸是否匹配，如果匹配将待装箱物品放入容器中，并进行三空间划分及空间合并；s22：如果容器尺寸不适配，则根据推荐容器初始化新的空间，直至容器尺寸适配；s23：判断待装箱物品是否全部装入容器中：如果没有，则按照装箱顺序执行步骤s21至s23继续装箱，直至所有待装箱物品全部装入容器中；如果已经全部装入容器中，则判断该装箱方案染色体的装箱适配过程完成。

如图4所示，其具体流程为：

获取需要进行装箱适配过程的装箱方案染色体，按照该染色体的装箱顺序以及每个待装箱物品放置方式和推荐容器参数，放入第一个待装箱物品，对可用的容器内部独立空间进行初始化，判断下一个待装箱物品的最小可用空间是否存在，如果存在，即放入下一个待装箱物品，然后判断所有的待装箱物品是否已经全部装箱，如果还存在需要装箱的物品，就对剩余的空间进行三空间划分，判断划分的三空间是否满足空间合并的条件，如果满足条件即进行空间合并，并更新可用的独立空间信息，直至所有的待装箱物品均已完成装箱。

如果装箱过程中，下一个待装箱物品的最小可用空间不存在，就根据推荐容器参数，为该待装箱物品初始化一个新的容器，放入该待装箱物品之后，可用的独立空间就包括已经使用的所有容器的可用空间，在进行下一个待装箱物品装箱的时候，按容器顺序进行最小可用空间判断，即前一个容器空间不足时，判断下一个容器空间是否能放入该物品。

如图5所示，为本实施例中三空间划分示意图，图中示出了坐标系x-y-z，该坐标系为三维笛卡尔坐标系，用于建立容器内的空间模型，其中三个坐标轴x,y,z分别对应容器的长度方向、宽度方向、高度方向，该坐标系的原点在容器的左后下角，还示出了容器1和其内部放置的物品2，按照坐标系z-y-x划分的三空间包括z方向的上空间23、y方向的前空间21以及x方向的左空间22。

如图6a～图6c所示，为本实施例中空间合并示意图，通过三空间划分方式，每放入一个待装箱物品就会产生3个子空间，随着待装箱物品越来越多，产生的子空间也越来越小，有些过狭窄而无法装入任何物品，因此需要在装箱之前对空间进行合并，即将同一空间中有共同面的两个空间进行合并成一个大的空间，形成新的可用独立空间，从而提高空间利用率。

图6a～6c示出了空间合并的三种情况，第一种为前后合并，图中示出了前空间211和后空间212，这两个空间有共同的xz面，可以进行前后合并成新空间213；第二种为左右合并，图中示出了左空间221和右空间222，这两个空间有共同的zy面，可以进行左右合并成新空间223；第三种为上下合并，图中示出了上空间231和下空间232，这两个空间有共同的xy面，可以进行上下合并成新空间233。

初始种群中所有装箱方案染色体的装箱适配过程完成后，获得父代种群，计算父代种群中每个装箱方案染色体的适应度，并保留适应度最高的装箱方案染色体。

适应度计算方法具体为：

cost＝1-(m+waste)/(n+1)

waste＝1-vn/vuse

其中，cost为装箱方案适应度，m为容器数量，waste为空间浪费率，n为待装箱物品数量，vn为待装物品的总体积，vuse为使用容器的总体积。

对父代种群中装箱方案染色体进行交叉进化，进化过程具体为：对父代种群中的装箱方案染色体按照顺序进行两两装箱方案染色体交叉进化形成多个第一代装箱方案染色体，多个第一代装箱方案染色体组成第一代进化种群。其中两两装箱方案染色体交叉进化指：在两个进行交叉进化的装箱方案染色体中，随机选择一个装箱方案染色体的装箱顺序和推荐容器，然后按顺序交叉两个装箱方案染色体的放置方式，得到进化后的装箱方案染色体。

如图7所示为本实施例装箱方案染色体交叉进化流程图，具体流程如下：

首先选择第n,n+1个染色体，其中0