基于超启发算法的二维条带装箱优化研究

Research on Two-Dimensional Strip Packing Optimization Based on Super-Heuristic Algorithm

  • 摘要: 针对二维矩形条带装箱问题,旨在最小化固定宽度条带的排放高度,提升制造与物流环节的空间利用率和装载效率。提出一种融合最佳天际线法与自适应多算子的超启发式算法:首先以多种排序策略结合最佳天际线启发式快速生成高质量初始解;继而引入基于Metropolis准则的接受判断,并设计11种全局与局部扰动算子,通过自适应权重动态调度算子,实现全局探索与局部开发的平衡。结果表明:在Hopper C类标准算例中,本文算法在7个算例上取得更优高度,其中C5P3算例装箱高度由对比算法的96降至91。在企业真实数据集中,装箱高度由9 567 mm降至9 445 mm,降低122 mm;在另一组矩形件数据中,算法平均装箱高度为2 666 mm,较对比算法的2 724 mm降低58 mm。研究表明:该方法以超启发式算法框架和高效的算子调度机制,显著地提升了二维条带装箱的求解精度与鲁棒性,为复杂生产环境下的高效、紧凑装载提供了可落地的技术路线和理论支持。

     

    Abstract: For the two-dimensional rectangular strip packing problem, the objective is to minimize the emission height of the fixed-width strip, thereby enhancing the space utilization and loading efficiency in manufacturing and logistics processes. A hyper-heuristic algorithm integrating the best-fit skyline method with adaptive multi-operators is proposed. First, multiple sorting strategies combined with the best-fit skyline heuristic are employed to rapidly generate high-quality initial solutions. Subsequently, an acceptance criterion based on the Metropolis principle is introduced, and eleven global and local perturbation operators are designed. These operators are dynamically scheduled via adaptive weights to achieve a balance between global exploration and local exploitation. The results indicate that in the Hopper C-class benchmark instances, the proposed algorithm achieves superior packing height in seven instances, reducing the packing height of instance C5P3 from 96 to 91 compared to the benchmark algorithms. On the real-world industrial dataset, the packing height is reduced from 9,567 mm to 9,445 mm, with a total decrease of 122 mm. In another dataset of rectangular items, the algorithm achieves an average packing height of 2,666 mm, which is 58 mm lower than the 2,724 mm achieved by the comparison algorithm. The finding suggest that the proposed method significantly improves the solving accuracy and robustness of 2D strip packing with a hyper-heuristic algorithm framework and an efficient operator scheduling mechanism, and provides a practical technical route and theoretical support for efficient and compact loading in complex production environments.

     

/

返回文章
返回