(19)中华 人民共和国 国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202111503424.6 (22)申请日 2021.12.09 (65)同一申请的已公布的文献号 申请公布号 CN 114048926 A (43)申请公布日 2022.02.15 (73)专利权人 广东工业大 学 地址 510062 广东省广州市越秀区东 风东 路729号 专利权人 广州秉优信息科技有限公司 (72)发明人 张浩　王润钦　王孙康宏　魏丽军　 林利彬　 (74)专利代理 机构 佛山市禾才知识产权代理有 限公司 4 4379 代理人 资凯亮　陆应健 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 10/06(2012.01) G06Q 10/08(2012.01) G06F 30/20(2020.01) (56)对比文件 US 6587466 B1,2003.07.01CN 101515 372 A,20 09.08.26 CN 10797 7756 A,2018.0 5.01 CN 109685278 A,2019.04.26 US 2021133677 A1,2021.0 5.06 邢志伟 等.基 于动态四叉树搜索的民航行 李车码放 算法. 《北京航空航天大 学学报 （CNKI网 络首发） 》 .2021, 刘胜 等.求 解三维装箱问题的多层树搜索 算法. 《自动化学报》 .2020,第46卷(第0 6期), QiangLiu 等.Algorithm s for the variable-sized bi n packing problem w ith time windows. 《Computers & I ndustrial Engineering》 .2021,第15 5卷 LiuSheng 等.A tre e search algorithm for the co ntainer loading problem. 《Computers & I ndustrial Engi neering》 .2014,第75卷 Qiang Liu 等.A Heuristic Ap proach to the Thre e Dimensi onal Strip Pack ing Problem Co nsidering Practical Constraints. 《IEA/AIE 2020》 .2020, 审查员 张子瑜 (54)发明名称 一种基于多叉树搜索的多箱型三维装箱优 化方法及系统 (57)摘要 本发明公开了一种基于多叉树搜索的多箱 型三维装箱优化方法及系统， 包括下述步骤： 建 立模型： 建立多箱型三维装箱优化模型； 构建多 叉树搜索结构： 构建求解多箱型三维装箱优化问 题的多叉树搜索结构； 优化算法： 在多叉树搜索 过程中， 每次拓展生成节点时， 调用一次单箱三 维装箱优化算法， 获取最优的单箱装载方案； 在 多叉树搜索过程中， 使用启发式剪枝策略和漏斗 式的节点数控制策略优化算法； 输出结果； 本申 请旨在提供一种基于多叉树搜索 的多箱型三维 装箱优化方法及系统， 通过调用单箱三维装箱优化算法获取当前最优装箱方案， 并运用启发式剪 枝策略与漏斗式的节点数控制策略来缩减树的 搜索规模， 提高搜索效率， 减少大量冗余搜索， 缩 短计算时间。 权利要求书4页 说明书13页 附图8页 CN 114048926 B 2022.04.15 CN 114048926 B 1.一种基于多叉树搜索的多箱型三维装箱优化方法， 其特 征在于， 包括下述 步骤： 建立模型： 建立多箱型三维装箱优化模型； 在建立模型的步骤中， 给定S种规格的箱子， S∈[1,S]， 每种箱子的体积为Vs， 从多种箱 子中选出一个或多个的一种或多种箱子， 将总数为n的货物全部装载， 每个货物的体积为 Vi， i∈[1,n]， 使得箱子的装载率 最高， 即装载完所有货物所用的箱子总体积最小； 以x轴的正方向为前方向， x轴的负方向为后方向， 以y轴的正方向为右方向， y轴的负方 向为左方向， 以z轴的正方向为上 方向， x轴的负方向为下 方向， 建立 正向的直角坐标系； 定义： 位于坐标系内的货物的后左下的角为A点， 位于坐标系内的货物的前右上的角为 B点； 建立模型： 最小化装载完所有货物所使用的箱子总体积为： ； 以使得： 当f箱子中装有货物时， yf=1， 有公式： ； 当所有货物必须全被装载完， 且一个货物只能被装载到一个箱子中时， 有公式： ； 当任意一个货物被装载到箱子之后， A， B两点的坐标均不能超出箱子的尺寸， 有公式： x方向：  ； y方向： ； z方向： ； 当货物只能以六种方式的其中一种方式摆放， 且B点 坐标由A点 坐标推导获得， 有公式： ； ； ； A点坐标推导出B点 坐标的公式有： ；权　利　要　求　书 1/4 页 2 CN 114048926 B 2； ； 当同一箱子中任意两个货物不能相交， 即k货物在i货物的前后左右上 下， 有公式： 前： （x1）kf‑（x2）if=α， α ≥0； 后： （x1）if‑（x2）kf=β， β ≥0； 左： （y1）if‑（y2）kf=γ， γ≥0； 右： （y1）kf‑（y2）if= δ， δ ≥0； 上： （z1）kf‑（z2）if= ε， ε ≥0； 下： （z1）if‑（z2）kf=ζ， ζ ≥0； i， k=1， 2， …， n且i≠k； 上述公式可转 化为： yif（yikf1α + yikf2β + yikf3γ+ yikf4δ + yikf5ε+ yikf6ζ ） ≥0； yif（yikf1+ yikf2+ yikf3+ yikf4+ yikf5+ yikf6‑1） ≥0； 其中， S为可选择的箱子种数； numS为初步预测第S种箱子将会使用的数量； F为； f为箱子编号f=1， 2， …， F； Vf为f箱子的体积； Lf为f箱子的长； Wf为f箱子的宽； Hf为f箱子的高； yf为零一变量， 表示第f个箱子是否被使用； yif为零一变量， 表示第i个货物是否被装载到f箱子中； M为无穷大的数； （x1）if为i货物在f箱子中后左下位置的x坐标； （x1）kf为k货物在f箱子中后左下位置的x坐标； （y1）if为i货物在f箱子中后左下位置的y坐标； （y1）kf为k货物在f箱子中后左下位置的y坐标； （z1）if为i货物在f箱子中后左下位置的z坐标； （z1）kf为k货物在f箱子中后左下位置的z坐标； （x2）if为i货物在f箱子中前右上位置的x坐标； （x2）kf为k货物在f箱子中前右上位置的x坐标； （y2）if为i货物在f箱子中前右上位置的y坐标； （y2）kf为k货物在f箱子中前右上位置的y坐标； （z2）if为i货物在f箱子中前右上位置的z坐标； （z2）kf为k货物在f箱子中前右上位置的z坐标； mi为货物的摆放方式， i=1， 2， 3， 4， 5， 6； li为i货物的长；权　利　要　求　书 2/4 页 3 CN 114048926 B 3