尚正阳,黄秋妍,康正阳,俞俊.一刀切约束下的二维装箱问题高效求解算法[J].包装工程,2021,42(7):231-238.
SHANG Zheng-yang,HUANG Qiu-yan,KANG Zheng-yang,YU Jun.Efficient Heuristic Algorithm for the Two-Dimensional Guillotine Rectangular Bin Packing Problem[J].Packaging Engineering,2021,42(7):231-238. |
| 一刀切约束下的二维装箱问题高效求解算法 |
| Efficient Heuristic Algorithm for the Two-Dimensional Guillotine Rectangular Bin Packing Problem |
| 投稿时间：2020-07-10 |
| DOI：10.19554/j.cnki.1001-3563.2021.07.032 |
| 中文关键词: 二维装箱问题 一刀切约束 启发式算法 递归求解 |
| 英文关键词: two-dimensional packing problem guillotine constraint heuristic algorithm recursive |
| 基金项目:安徽高校自然科学研究项目(KJ2019A0148) |
|
| 摘要点击次数: |
| 全文下载次数: |
| 中文摘要: |
| 目的 为实现大规模物料的快速剪裁切割，对考虑一刀切约束的二维装箱问题进行研究，并构建相应的改进优先度算法IPH (Improved Priority Algorithm，IPH)。方法 IPH能够在不需要任何迭代搜索下，直接进行剩余空间分割与填充。为此，发展PH算法中的优先度放置规则，并以最大化生成大空间面积和最小化生成小空间面积为基础，设计改进砌砖式空间分割策略。结果 针对标准数据集的对比实验表明，IPH能够在较短时间内完成大规模算例的高效求解，并首次获得了多个算例的最优填装效果。结论 基于概率较优的启发式求解方法，能够实现无迭代优选下的一刀切二维装箱问题直接求解，且运算效果令人满意。 |
| 英文摘要: |
| Given the two-dimensional bin packing problem under the guillotine constraint, an improved priority heuristic (IPH) algorithm with rapid solving ability is proposed. IPH can directly divide and fill the residual space without any iterative searching. For this reason, the priority placement method in PH algorithm is developed, and an improved bricklaying space division rule based on maximization of newly-formed large-space area and minimization of small-space area is designed. Based on the heuristic strategy that can obtain a better solution with higher probability, the rule designed is favorable for placement of large rectangles and less likely to form wasted space. Comparative experiments with standard datasets shows that IPH can effectively solve large-scale cases within very short time and produce the optimal filling effects of many cases for the first time. The new algorithm achieves the 2D-GRPP optimization allocation under the direct operation mode and offers some technical reference for relevant research on GRPP. |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |
渝公网安备 50010702501716号