求解矩形条带装箱问题的改进剩余矩形法

作     者：刘志雄 

作者机构：武汉科技大学机械自动化学院 

出 版 物：《计算机集成制造系统》 (Computer Integrated Manufacturing Systems)

年 卷 期：2023年

核心收录：

学科分类：08[工学] 081104[工学-模式识别与智能系统] 0811[工学-控制科学与工程] 

主　　题：矩形条带装箱问题 剩余矩形法 加权匹配 动态放置 后处理 粒子群算法 

摘      要：矩形条带装箱问题是一类具有NP-Complete求解复杂性的组合优化问题，提出一种基于加权匹配函数的改进剩余矩形法用于求解矩形条带装箱问题。设计一种多因素加权匹配函数，采用双向选择策略，在剩余矩形集合和待排放矩形件集合中，选择最合适的剩余矩形和矩形件实现最优匹配。基于加权匹配函数值，采用动态放置策略用于确定矩形件在剩余矩形中的放置位置。为了降低装箱高度，采用了旋转和平移后处理工艺对位于最高位置的矩形件进行调整。不同算例采用动态权重模式，利用粒子群算法用于搜索和确定最优权重值。针对典型算例的实验结果表明，相比传统剩余矩形法，改进剩余矩形法能够有效降低装箱高度。从测试算例装箱高度的平均误差看，计算结果也明显好于BF（Best Fit）算法及其改进算法，仅次于基于评分规则的启发式算法。