求解二维矩形件装箱问题的布谷鸟算法*

冯文健

(柳州铁道职业技术学院， 广西 柳州 545616)

0 引言

二维矩形装箱问题(2D rectangular strip packing problem, 2DRSPP)是将一组长度、宽度不等的矩形互不重叠的装入给定宽度、长度不限的矩形条带箱中，使得箱子被矩形占用的高度最小。该类问题是NP难问题，在工业领域被广泛应用，因此对此类问题的求解有重要的研究价值。目前对2DRSPP的研究主要集中于算法设计，可分为精确算法、启发式算法和混合智能算法，由于精确算法求解时间较长，只适合较小规模算例。而后两者成为求解2DRSPP的主流算法[1-4]。近年来，相关学者提出一些更有效的启发式算法和混合智能算法，尚正阳等[5]设计一种启发式最优剩余空间算法，提出求解二维矩形装箱问题的启发式算法；邓见凯等[6]提出一种求解二维矩形Packing问题的拟人型全局优化算法；罗强等[7]提出求解矩形件排样问题的十进制狼群算法；江林燕[8]提出基于化学反应优化算法的装箱问题研究；车玉馨[9]提出装箱问题的启发式算法研究；高东琛[10]提出二维装箱问题的启发式算法。

本文设计了算法1并结合布谷鸟算法求解二维矩形装箱问题，通过多组测试算例的仿真实验，结果表明本文设计的算法对部分测试算例效果较好，对部分测试算例效果较差。

1 二维矩形装箱问题描述

图1 矩形件装箱示意图

假设第i个小矩形pi的长度和宽度分别表示为wi和hi，排放在宽度为W、高度不限的大矩形带箱strip上，矩形件i排放后左上角的横坐标、纵坐标和宽度分别为xi、yi和wi。排放的过程中矩形件之间不重叠、矩形件不超出strip的边界和矩形件底边与strip边平行3个约束条件。……