(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111351734.0 (22)申请日 2021.11.16 (71)申请人 济南大学 地址 250022 山东省济南市南 辛庄西路3 36 号 (72)发明人 赵诗奎　季晏庆　 (74)专利代理 机构 济南誉丰专利代理事务所 (普通合伙企业) 37240 代理人 赵凤 (51)Int.Cl. G06F 30/27(2020.01) G06N 3/12(2006.01) G06F 111/04(2020.01) G06F 111/08(2020.01) G06F 111/16(2020.01) (54)发明名称 一种基于遗传算法的板式家具智能打包方 法 (57)摘要 本发明公开了一种基于遗传算法的板式家 具智能打包方法。 获取板式家具的一个订单， 读 取所述订单的所有待打包板式家具信息、 包装纸 信息以及打包约束信息， 利用基于最低水平线搜 索方法生 成一系列打包初始方案， 将初始方案与 随机产生的其它打包方案共同组成遗传算法的 初始种群， 以最少包裹数量为优化目标， 最低水 平线法为解码方法进行迭代优化， 获得更优的打 包方案。 本发 明降低了板式家具打包 所用包裹的 数量， 减少了包装纸的使用量， 提高了后续工人 装车运输等工作的效率， 亦可应用于其它打包领 域的实际问题中。 权利要求书3页 说明书6页 附图5页 CN 114004167 A 2022.02.01 CN 114004167 A 1.一种基于 遗传算法的板式家具智能打包方法， 其特 征在于， 包括以下步骤： 步骤1： 读取问题数据， 初始化待打包家具尺寸数据集合、 包装纸参数数据集合、 打包约 束数据集 合、 种群数目、 染色体 基因维数、 最大迭代次数； 步骤2： 利用基于最低水平线搜索方法生成数量为种群规模一半的不同的打包初始方 案； 步骤3： 将初始方案与随机产生的其它打包方案按照种群数量各占一半的方式共 同组 成遗传算法的初始种群； 步骤4： 利用最低水平线法解码方法计算个 体适应度值， 即 打包所需包裹数量； 步骤5： 采用基于概率的方式选择进行操作的个体， 即先将适应度值进行归一化处理， 所用包裹数量越少， 适应度值越大， 个体适应度越大， 则被选择的机会也就越大， 每一轮产 生一个[0， 1]内的均匀随机数， 将该随机数与个体适应度进 行比较， 个体适应度大于该随机 数时， 保留此个 体到交配池中； 步骤6： 从交配池中随机选择一对个体， 随机选择两个交叉点位置， 依次交换交叉点之 间所选中的成对板式家具打包顺序， 以确定交叉后每 个板式家具只打包一次； 步骤7： 对选中的单个个体， 随机交换其一对板式家具的打包顺序作为变异操作， 产生 新的个体； 步骤8： 判断是否达到最大迭代次数： 若满足， 结束搜索过程， 输出最优值； 若不满足， 则 继续迭代优化， 转入步骤4。 2.根据权利要求1所述的打包约束， 其特征在于， 每个包裹的第一层只 能有一块板， 不 同的包裹 根据底板的不同和包裹重量的约束会有不同的打包层数约束。 3.根据权利要求1所述的遗传算法中的染色体， 其特征在于， 染色体编码为带符号的十 进制编码， 带负号的染色体基因表示对应的板式家具打包时按照高度大于宽度的方式进 行 打包， 若对应的板式家具被选择为底板， 需将该染色体 基因修正为正数后再进行打包操作。 4.根据权利要求1所述的优化目标为减少包裹数量。 5.根据权利要求1所述的方法， 其特征在于， 所述生成打包初始方案的基于最低水平线 搜索方法包括以下步骤： 步骤1： 读取问题数据， 初始化待打包家具尺寸数据集合、 包装纸参数数据集合、 打包约 束数据集 合； 步骤2： 对所有板 式家具按照宽度和高度进行处理： 首先对高度 大于宽度的板 式家具进 行旋转， 计算所有板式家具的面积 。 按照面积降序排序， 生 成集合RectSize1{}。 按照宽度降 序排序， 对于宽度相同的按照高度降序排序生成集合RectSize2{}。 按照高度降序排序， 对 于高度相同的按照宽度降序排序生成集 合RectSize3{}； 步骤3： 从矩形集合RectSize1{}中选择面积最大的未打包板式家具， 根据其宽度和高 度确定底板的尺寸， 以此选择合适的包装纸， 即包装纸的宽度和高度均大于板式家具 的宽 度和高度， 根据选取的包装纸和底板确定包裹的层数约束。 生成一个水平线集合， 将与所选 板式家具宽度对应的底部水平线作为基准排放水平线加入到所述水平线集合中。 若矩形空 间RectSize1{}中已经没有未打包板式家具， 结束打包， 导出初始打包 方案Order{}， 以作为 遗传算法的初始个 体； 步骤4： 找出最低水平线， 在矩形集合RectSize2{ }中寻找宽度小于等于所述最低水平权　利　要　求　书 1/3 页 2 CN 114004167 A 2线的宽度， 且排入后该矩形 的顶部水平线不高于底板高度的待排板式家具， 为了保持遗传 算法种群的多样性， 在搜索到的前三个板式家具中任选一个记录其宽度， 搜索不到则记为 0。 在矩形集合RectSize3{}中寻找高度小于等于所述最低水平线的宽度， 且旋转排入后该 矩形的顶部水平线不高于底板高度的待排板式家具， 为了保持遗传算法种群的多样性， 在 搜索到的前三个板式家具中任选一个记录其高度， 搜索不到则记为0； 步骤5： 判断记录的板式家具的宽度或高度是否大于0， 如果记录的数据大于0， 则说明 存在待排板式家具可以被打包放置， 取板式家具 的宽度和高度中较大 的， 若所取板式家具 的宽度大于高度， 将选取的板式家具宽度对应矩形集合RectSize2{}中的矩形靠左排放在 所述最低水平线 上， 并记录该板式家具的序号到集合Order{}， 转入步骤6， 若所取板式家具 的高度大于宽度， 将选取的板式家具高度对应矩形集合RectSize3{}中的矩形旋转后靠左 排放在所述最低水平线 上， 并记录带负号的该板式家具的序号到集合Order{}， 转入步骤6。 如果记录的板式家具 的宽度和高度均等于0， 说明没有任何待排板式家具可以被排放到该 位置， 则该空间视为浪费， 此时需要将最低水平线位置的高度提升为左邻居和右邻居中高 度最小的一个高度， 转入步骤4， 若只有一条最低水平线且不能放置任何板式家具， 转入步 骤7； 步骤6： 更新最低水平线集合， 将放置矩形位置对应的最低水平线替换为矩形对应的顶 部水平线集合。 删除矩形集合RectSize1{}、 RectSize2{}、 RectSize3{}中该板 式家具的尺 寸以及面积信息， 转入步骤4。 若矩形 空间RectSize1{}中已经没有未打包板式家具， 结束打 包， 导出初始打包方案Order{}， 以作为遗传算法的初始个 体； 步骤7： 判断该包裹是否装满， 未装满则需要重新生成一个尺寸大小与底板相同的最低 水平线集 合转入步骤4继续 排放未打包板件， 若该包裹已经装 满， 转入步骤3 。 6.根据权利要求1所述的方法， 其特征在于， 所述遗传算法解码方法为最低水平线法包 括以下步骤： 步骤1： 读取问题数据， 初始化待打包家具尺寸数据集合、 板式家具对应的矩形集合、 包 装纸参数数据集合、 打包约束数据集 合、 当前染色体对应的打包顺序集 合Order{}； 步骤2： 从打包顺序集合Order{}中按顺序从矩形集合中选择未打包板式家具， 根据其 宽度和高度确定底板的尺寸， 以此选择合适的包装纸， 即包装纸的宽度和高度均大于板式 家具的宽度和高度， 根据选取的包装纸和底板确定包裹的层数约束。 生成一个水平线集合， 将与所选板式家具宽度对应的底部水平线作为基准排放水平线加入到所述水平线集合中。 若已经没有未打包板式家具， 结束打包， 导出包裹数量 为适应度值； 步骤3： 找出最低水平线， 从打包顺序集合Order{ }中按顺序从矩形集合中选择未打包 板式家具， 判断当前板式家具是否能摆放在该水平线上， 即该板式家具宽度小于等于所述 最低水平线的宽度， 且排入后该矩形 的顶部水平线不高于底板高度， 对应的染色体基因为 负数时， 判断条件为该板式家具高度小于等于所述最低水平线的宽度， 且旋转排入后该矩 形的顶部水平线不高于底板高度： 如果满足条件， 转入步骤4； 若不满足条件， 转入步骤5； 步骤4： 更新最低水平线集合， 将放置矩形位置对应的最低水平线替换为矩形对应的顶 部水平线集合。 删除打包顺序集合Order{}中板式家具对应的打包顺序， 转入步骤3。 若已经 没有未打包板式家具， 结束打包， 导出包裹数量 为适应度值； 步骤5： 没有任何板式家具可以放到该位置， 则该空间视为浪费， 判断是否可以提升最权　利　要　求　书 2/3 页 3 CN 114004167 A 3