阳名钢,陈梦烦,杨双远,张德富

(厦门大学 信息学院,福建 厦门 361005)

二维带形装箱问题是指将一组矩形小物品装入一个具有给定宽度、但是高度无限的矩形箱子中,这些矩形只能按照固定方向放置,不能相互重叠,且必须完全装入箱子中.问题的目标是使得使用的高度尽可能的低.

二维装箱问题是经典的组合优化问题,在各行各业中都有着非常广泛的应用.如在石材切割中,物品是小块的石材,箱子则对应待切割的完整石板,目标是使石材的利用率更高.由于装箱问题广泛地存在于各个领域,高效的求解算法有助于公司节省材料和减少资源浪费,提高生产和工作效率,帮助更合理利用有限的资源.多年来,二维带形装箱问题(2DSPP)被众多国内外学者研究以获得更快更优的解决方案.与其他组合优化问题一样,2DSPP 可通过精确算法、近似算法(启发式和元启发式)或者混合算法等来求解[1].

精确算法可以找到问题的最佳解决方案,但在较大的问题实例上通常需要花费大量的时间.Hifi[2]基于分支定界过程提出了一种精确算法用于解决带状切割和包装问题,该算法在可接受的执行时间内解决一些中小规模问题实例.Martello 等人[3]提出了一种新的松弛方法,该方法可产生良好的下界,基于此下界构造出较好的启发式算法.Kenmochi 等人[4]设计了一个基于分支规则和边界操作的分支定界算法.Côté 等人[5]提出了一种基于Bender 分解的精确算法,该方法可以在有限的……