二维Strip Packing问题的嵌套启发式算法

Nested Heuristic Algorithm for Two-dimensional Strip Packing Problem

二维Strip Packing问题(2SP)是二维装箱问题中的经典NP-Complete问题。采用两层嵌套迭代算法:第一层采用遗传算法决定矩形排放次序;第二层提出水平线择优匹配算法(LSBF),算法是基于底部左齐择优匹配算法(LLABF)和快速启发式法(FH)的改进算法,决定矩形排放规则。包含特殊结构的benchmark和新的随机算例等的排样结果表明算法的有效性。

Two-dimensional rectangular strip packing problem is a classic NP-Complete problem. A hybrid heuristic algorithm consisting of two-nested-stage approach is adopted to solve problem. In the outer layer, GA is used to determine the sequence and in the inner layer Lowest Skyline Best-Fit （LSBF） heuristic algorithm based on Lowest-Level Left Align Best-Fit （LLABF） and Fast Heuristic （FH） is proposed to describe how this sequence is allocated onto the strip. The computational results on special benchmark problems and new random problem have shown the efficient of this algorithm.