一刀切约束下的二维装箱问题高效求解算法

• 作者: 尚正阳 黄秋妍 康正阳 俞俊
• 来源期刊: 包装工程
• 关键词: 二维装箱问题 一刀切约束 启发式算法 递归求解
• 年，卷（期）: 2021,（7）
• 所属期刊栏目: 工艺与装备|Process and Equipment
• 页码范围: 231-238
• 页数: 8页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.19554/j.cnki.1001-3563.2021.07.032

摘要

目的 为实现大规模物料的快速剪裁切割,对考虑一刀切约束的二维装箱问题进行研究,并构建相应的改进优先度算法IPH(Improved Priority Algorithm,IPH).方法 IPH能够在不需要任何迭代搜索下,直接进行剩余空间分割与填充.为此,发展PH算法中的优先度放置规则,并以最大化生成大空间面积和最小化生成小空间面积为基础,设计改进砌砖式空间分割策略.结果 针对标准数据集的对比实验表明,IPH能够在较短时间内完成大规模算例的高效求解,并首次获得了多个算例的最优填装效果.结论 基于概率较优的启发式求解方法,能够实现无迭代优选下的一刀切二维装箱问题直接求解,且运算效果令人满意.