二维一刀切装箱问题的两阶段启发式算法

Two-stage heuristic algorithm for two-dimensional guillotine bin packing problem

对用于二维带排样问题的Heuristic Recursive算法进行了调整,给出同一层中两个相邻浪费区域在满足一刀切约束下是否可合并的判定定理。构造了二维带排样问题的多递归层算法,并将它与一维装箱问题的最优匹配递减算法相结合,提出适应二维一刀切非旋转装箱问题的两阶段算法。在500组标准测试案例的基础上,与多种算法进行了比较。实验结果表明,所提算法在绝大多数测试案例上能够获得更好的排样布局。

The Heuristic Reeursive（HR）algorithm for two-dimensional strip packing problem was adjusted, and a judgment theorem which was used to determine whether two neighbor wasted spaces in same layer could be combine or not was presented. A multi-recursive algorithm for two-dimensional strip packing problem（2D-SPP）was constructed, and a Two-Stage Approach （TSA）for two-dimensional oriented guillotine bin packing problem was proposed by combining the algorithm with Best-Fit Decreasing（BFD）algorithm of one-dimensional bin packing problem. On the basis of 500 group benchmark problems, the approach was compared with multiple algorithms, the experiments showed that the proposed approach could obtain better results for almost all test instances.