一種求解二維矩形Packing問題的擬人型全局優化算法

鄧見凱，王 磊，尹愛華

(1.武漢科技大學計算機科學與技術學院,湖北 武漢 430065;2.智能信息處理與實時工業系統湖北省重點實驗室，湖北 武漢 430065;3.江西財經大學軟件與通信工程學院，江西 南昌 330013)

1 引言

二維矩形Packing問題是指：在二維歐氏空間中，給定1個矩形容器和n個矩形塊。矩形容器和矩形塊的長、寬為已知的正實數。在滿足三個約束條件的前提下，要求將這些矩形塊放入矩形容器內，使得矩形容器的面積利用率最大化。約束條件為：第一，小矩形塊須完全在矩形容器內。第二，矩形塊的每條邊均和矩形容器的某條邊平行或重合。第三，每兩個小矩形塊相互不重疊。三個約束條件可簡稱為：“不出界、不傾斜、不重疊”。

W和H表示矩形容器的長度和寬度。wi和hi表示矩形塊Ri的長度和寬度。(xli,yli)和(xri,yri)分別表示矩形塊Ri被放入矩形容器后，其左下角和右上角的坐標。若矩形塊Ri已被放入矩形容器中，則邏輯變元pi值為1；否則pi值為0。矩形容器位于第一象限，并且其左下角位于坐標原點(如圖1所示)。二維矩形Packing問題的形式化描述如下：

subject to

pi=0∨(0≤xli

(1)

pi=0∨(xri-xli=wi∧yri-yli=hi)∨(xri-xli=hi∧yri-yli=wi)

(2)

pi=0∨pj=0∨(xli≥xrj∨xlj≥xri∨yli≥yrj∨ylj≥yri)

(3)

pi∈{0,1}

(4)

其中，i,j=1,2,…,n，并且i≠j。公式(1)表示每個小矩形塊須完全在容器內。公式(2)表示小矩形塊的每條邊均和矩形容器的某條邊平行或重合。公式(3)表示每兩個小矩形塊相互不重疊[1]。

二維矩形Packing問題已被證明為NP難度問題。工商業、運輸、物流領域的諸多問題可歸結為二維矩形Packing問題。例如，在板材切割加工過程中，需要合理布局以提高材料利用率；在集成電路設計中如何布置以提高布局空間利用率[2]。

算法可分為完整算法和啟發式算法兩類。完整算法能保證找到最優布局，但是所花時間太長，僅可用于計算較小規模的問題實例[3]。啟發式算法又可分為非隨機型算法和隨機型算法。

非隨機型算法著力于提出選擇放置動作的優先序，并在其基礎上進行樹搜索，包括底部左齊擇優匹配算法[4]、分支限界[5]、擬人算法[6-10]。文獻[6]提出基于動作空間的基本算法和增強算法。動作空間定義的引入便于計算出合理的占角動作?；舅惴ㄔ诙鄠€占角動作中選擇時，優先選取與當前動作空間相貼邊多、對剩余空間損害小、與其它已放入塊關系更緊密的動作。增強算法在每一步考察優先序中排名前N名的占角動作，通過向前看并回溯的方法選擇一個動作。

隨機型算法以矩形塊優先序作為高維空間中的點，設計各種鄰域結構，結合了各種緊密放置矩形塊的策略以及搜索策略，包括貪心隨機適應搜索算法[11]、模擬退火和貪心局部搜索算法[12]、禁忌搜索算法[13]、隨機局部搜索[14,15]、變鄰域搜索[16]。

為實現全局優化，本文中的算法主要采用兩種方法。第一是采用三階段優化，結合了目前文獻中非隨機型和隨機型算法的優點。第二是提出跳坑策略將搜索引向有希望的區域。

2 擬人算法策略

2.1 基本定義

定義1(格局) 矩形容器內已放入一些矩形塊，每個矩形塊的位置、方向已知，容器外尚有矩形塊待放，這稱為一個格局。初始格局中，所有矩形塊均在容器外。終止格局中，所有矩形塊均在容器內，或者雖有塊在容器外但已經不可能再放入。圖1為一個格局[17]。

Figure 1 Configuration and corner areas圖1 格局及角區

定義2(角區) 矩形容器中由塊或者矩形容器本身形成的直角形狀的空白區域被稱為角區。分為90°角區和270°角區。圖1中有10個角區，其中角區1、3、5、6、7、8、10為90°，角區2、4、9為270°。角區的定義來自于人們裝箱的實際經驗。將物體放在角區，在格局中腹部留出大片相對完整的空白區域，有利于后續矩形塊的布局。本文與文獻[17]中的角區定義有所不同。本文中的角區全部為“實角”。也就是說，角區的頂點一定是某個小矩形塊(或矩形容器)的頂點。這樣設計的優點是布局更為緊密。

定義3(占角動作) 在滿足三個約束條件的前提下，將一個矩形塊按照指定方向(站或躺)放在指定的位置(用塊左下角坐標表明)，使得矩形塊的一角正好與90°角區的角重合。這稱為一個占角動作。圖2中A、B、C、D、E、F、G均為占角動作。

Figure 2 Corner-occupying action圖2 占角動作

定義4(動作空間) 在當前格局下，若往矩形容器內放入一個虛擬的矩形塊(滿足三個約束條件)，使得該塊的上下左右四條邊均與其它已放入的塊或容器的邊相貼(重合的長度大于0)，則該虛擬塊所占的空間稱為當前格局下的一個動作空間[9,11]。初始格局下，恰有一個動作空間，當放入一個矩形以后，形成兩個動作空間，如圖3所示。動作空間的定義有助于計算矩形塊的合理動作。

Figure 3 Action space圖3 動作空間

定義5(剩余空間平整度) 平整度計算公式為e4-m，其中m為剩余空間的角區數(包括90°和270°角區)。剩余空間的角區數越少，其平整度越高，有利于放置后續矩形塊。圖4a中，將矩形塊放在位置A，剩余空間m值為8。圖4b中，將同一個矩形塊放在位置B，則剩余空間m值為10。因此,圖4a中的剩余空間平整度較高。本文對文獻[6]中的平整度定義作了簡化。

Figure 4 Degree of planeness圖4 剩余空間平整度

定義6(占角動作的重疊度) 一個占角動作所對應的矩形塊與其所在動作空間的貼邊數，稱為其重疊度。重疊度高的動作，與所在動作空間貼合較好，對剩余空間損害較小，有利于放置后續矩形塊[7]。圖5a和圖5b中動作重疊度分別為3和2。

Figure 5 Degree of overlapping of the corner-occupying action圖5 占角動作重疊度

Figure 6 Degree of cave of the corner-occupying action圖6 占角動作穴度

定義8(占角動作面積利用率) 占角動作面積利用率的計算公式為(wihi)/(WjHj)(參見圖6)。

定義9(占角動作的浪費度) 當一個占角動作做完后，在其占據的動作空間中最多可能生成兩個新的動作空間(參見圖7)。若一個新的動作空間過小，放不下矩形容器外的任何一個小矩形塊，則稱其為被浪費的動作空間。占角動作做完后新生成的被浪費的動作空間的數量，稱為此占角動作的浪費度。觀察圖7a和圖7b中的兩個新生成的動作空間。若兩個動作空間均為被浪費的動作空間，則占角動作的浪費度為2；若其中恰有一個動作空間被浪費，則占角動作的浪費度為1；否則占角動作的浪費度為0。

Figure 7 Degree of waste of the corner-occupying action圖7 占角動作浪費度

定義10(矩形塊優先級) 假定n個矩形塊分為k種形狀大小兩兩不等的類型，矩形塊的優先級是1～k的正整數。對于形狀大小相同的矩形塊，其優先級相等。不妨令k級為最高優先級，1級為最低優先級。w(Ri)表示矩形塊Ri的優先級，1≤w(Ri)≤k。

定義11矩形塊排序的3項指標：(1) 矩形塊的周長，大優先；(2) 矩形塊的長邊長，大優先；(3)矩形塊的序號，小優先。對矩形塊排序后，在查找時可利用折半查找，提高速度。

定義12占角動作排序的9項指標：(1) 動作做完后，矩形容器內剩余空間的平整度，大優先；(2) 動作的重疊度，大優先；(3) 矩形塊的優先級，大優先；(4) 動作的穴度，大優先；(5) 動作的浪費度，小優先； (6) 矩形塊的序號，小優先；(7) 矩形塊左下頂點的y坐標，小優先；(8) 矩形塊左下頂點的x坐標，小優先；(9) 矩形塊的方向，躺優先。

定義13動作空間排序的4項指標：(1) 動作空間左下角的x坐標，小優先；(2) 動作空間左下角的y坐標，小優先；(3)動作空間的長度，小優先；(4)動作空間的寬度，小優先。

如果某個動作空間放不下任何一個容器外的矩形塊，則在動作空間序列中刪去此動作空間。對動作空間排序后，為節省計算時間，本文僅考慮排序前M位的動作空間。M取值為200。

2.2 基本算法

基本算法命名為A1算法。其步驟如下：

Step1初始格局：所有矩形塊均在矩形容器外，矩形容器是空的。依字典序按照矩形塊排序的3項指標(見定義11)對所有矩形塊排序。

Step2在當前格局下，依字典序按9項指標(見定義12)選擇最優先的占角動作來做，動作做完以后，演化到新格局。

Step3對動作空間序列做如下三步操作。第一，更新占角動作所在的動作空間。第二，檢查所放入的矩形塊是否與動作空間序列中其它動作空間重疊。若有重疊，則更新重疊的動作空間。第三，刪去被其它動作空間包含的動作空間。

依此類推，循環做Step 2～Step 3，直到終止格局為止。

2.3 擬人型全局優化算法(A1B1)整體框架

整個擬人型全局優化算法由三個優化階段組成(參見圖8)。擬人型全局優化算法基于基本算法A1和優美度枚舉子程序B1，因此本文將擬人型全局優化算法命名為A1B1算法。

Figure 8 Sketch of the whole algorithm圖8 算法總體框圖

(1)在第一優化階段中生成初始點(2.4節)。初始點記為Q0，它表示所有矩形塊的初始優先級。給定Q0后，從初始格局出發，運用基本算法A1可唯一確定一個終止格局。這個終止格局記為C(A1,Q0)。

(2)在第二優化階段中，交替循環調用鄰域搜索子程序(2.5節)和跳坑策略子程序(2.6節)，針對所有矩形塊的優先級進行優化。調用鄰域搜索子程序。若發現矩形塊已全部進入矩形容器，則成功停機。若搜索遇到局部最優點，則調用跳坑策略子程序跳出局部最優點，得到新的起點。從新起點開始，又循環調用鄰域搜索子程序。如此反復，直到滿足第二階段計算停止條件為止。

第二優化階段結束時，得到一個優化后的所有矩形塊的優先級，記為Q+。根據Q+，從初始格局出發，運用基本算法A1可唯一確定一個終止格局。這個終止格局記為C(A1,Q+)。

(3)在第三優化階段中調用優美度枚舉子程序(2.7節)。優美度枚舉子程序命名為B1算法。B1算法是一種樹搜索程序，針對占角動作的選擇進行優化。從初始格局出發，按照優先級Q+，B1算法可唯一確定一個終止格局。這個終止格局記為C(B1,Q+)。

每個優化階段的計算停止條件均為兩個：第一個條件是當矩形塊已全部進入矩形容器，則輸出布局，成功停機。第二個條件是計算達到本階段的計算時間上限，則停止，轉入下一個優化階段。本文中三個優化階段的時間上限相等。

若三個優化階段結束，仍未將所有矩形塊放入矩形容器，則輸出計算歷史上所生成的最優布局，停機。

小規模實例(矩形塊數小于或等于200)、中規模實例(矩形塊數大于200且小于或等于500)、大規模實例(矩形塊數大于500且小于或等于10 000)、對超大規模實例(矩形塊數大于10 000)的計算時間上限分別為360 s、600 s、1 200 s和15 000 s。

2.4 初始點的生成

所謂生成初始點，是指對所有矩形塊指派優先級。本文按照大矩形塊優先的策略指派優先級，有“周長大者優先”“面積大者優先”“長邊長大者優先”三種具體做法。第一種做法：首先按照定義11對所有矩形塊排序，然后依次指派優先級，這是“周長，大優先”的做法。第二種做法：將定義11中的第1項指標改為“矩形塊的面積，大優先”。第三種做法：刪去定義11中的第1項指標，這是“長邊長，大優先”的做法。三種做法各有其優缺點，本文在其中均勻地隨機取一種，生成初始點。

2.5 鄰域搜索子程序

Q=(q(R1),q(R2),…,q(Ri),…,q(Rn))表示所有矩形塊的優先級。用Q表示n維空間中的一個點。只要指定Q值，從初始格局出發，運用基本算法A1可唯一確定一個終止格局。這個終止格局記為C(A1,Q)。

以A1算法為基礎進行適當的鄰域搜索(屬于局部搜索)，期望尋找更優的矩形塊的優先級。本文提出兩種鄰域結構，一定程度上避免單一型鄰域結構的局限性。

定義14(交換式鄰域) 任意給定所有矩形塊的優先級Q，不妨將矩形塊按照優先級從高到低的順序排列。考慮優先級為k1和k2的矩形塊，將它們的優先級互換，保持其余矩形塊的優先級不變。從而得到一個新優先級Q′,Q′的集合構成Q的交換式鄰域。其中1≤k1

定義15(插入式鄰域) 任意給定所有矩形塊的優先級Q，將矩形塊按照優先級從高到低的順序排列?？紤]所有優先級大于或等于k1并且小于或等于k2的矩形塊，插入式鄰域有兩種方式：第一種是將原優先級為k2的矩形塊降為k1級，然后將原優先級嚴格小于k2并且大于或等于k1的矩形塊均升1級。第二種是將原優先級為k1的矩形塊升為k2級，然后將原優先級嚴格大于k1并且小于或等于k2的矩形塊均降1級。其余矩形塊的優先級不變。

例1已知6個矩形塊的優先級：q(R2)=4,q(R4)=3,q(R5)=3,q(R3)=2,q(R1)=1,q(R6)=1。首先討論交換式鄰域。例如考慮優先級為1和3的矩形塊，互換其優先級。q(R1)=3,q(R6)=3,q(R4)=1,q(R5)=1，其余矩形塊的優先級不變。

然后討論插入式鄰域。例如考慮優先級從2到4的矩形塊。可將優先級為4的矩形塊降為2級，然后優先級為3和2的矩形塊均升1級。新的優先級為：q(R4)=4,q(R5)=4，q(R3)=3,q(R2)=2。也可以將優先級為2的矩形塊升為4級，然后優先級為4和3的矩形塊均降1級。新的優先級為：q(R3)=4,q(R2)=3,q(R4)=2,q(R5)=2。其余矩形塊的優先級不變。

進行鄰域搜索時采用“見好就收”的策略以節約計算時間。迭代的一步為：依次考慮當前點Q的全部鄰點，對于鄰點按照基本算法A1計算出對應的布局。一旦發現某個鄰點所對應的布局面積利用率更高，立刻用此鄰點取代當前點,一步迭代完成。若所有鄰點對應的布局的面積利用率均不高于當前點對應的布局，則當前點為局部最優點，停止本次鄰域搜索子程序的運行。

與現有求解矩形Packing問題的文獻中的鄰域搜索程序[16]相比，本文增加了插入式鄰域，使得搜索范圍擴大，有利于找到更優布局。

2.6 跳坑策略子程序

當鄰域搜索遇到局部最優點時，調用跳坑策略子程序跳出局部最優點，得到新的起點。從新的起點出發繼續進行鄰域搜索。如此反復，有望找到更優布局?，F有文獻主要采用模擬退火、禁忌搜索等方法跳出局部最優。本文采用的是擬人途徑跳出局部最優陷阱。

起跳點的選擇有兩種方式：第一種是回到歷史最好點。在第二優化階段所發現的歷史最好點(對應的布局面積利用率最高)的信息可以利用。為避免搜索總是圍繞在歷史最好點附近，第二種起跳方式是從當前點起跳。本文在兩種起跳方式中均勻地隨機選擇一種。

跳坑方法是對起跳點進行隨機擾動。具體做法為R步迭代，每一步迭代是在起跳點的所有鄰點中均勻地隨機選取1個鄰點，將此點作為新的起跳點，從而完成1步迭代。在第4節的實驗中，R是在[10,20]內均勻分布的隨機整數。

2.7 優美度枚舉子程序

定義16(占角動作優美度) 在當前格局下，定義占角動作的優美度：占角動作做完后，按照基本算法計算到終止格局，終止格局中矩形塊的面積之和稱為此占角動作的優美度。

優美度枚舉子程序采用了棋類游戲中“向前看并回溯”的思路，其具體步驟如下：

Step1初始格局。所有矩形塊均在矩形容器外。

Step2進行一輪計算：在當前格局下，首先依字典序按照定義12中的9項指標對所有占角動作排序，取排名前N名的占角動作為候選。然后調用A1算法依次計算這N個動作的優美度。最后選擇其中優美度最大的動作。若優美度最大的動作有多個，則按照定義12取其中最優先的動作。動作做完后，演化到新格局。

Step3更新動作空間序列。

循環執行Step 2和Step 3，直到算法停機。

停機條件有兩個：第一，所有矩形塊均已放入矩形容器。第二，優美度枚舉子程序的執行時間已經達到所設定的上限。

2.8 擬人型全局優化算法族

基本算法A1按照定義12中的9項指標來選取排序第一的占角動作。對定義12中的9項指標略作修改，可得到基本算法族。

基本算法A2：從算法A1修改而來。將定義12中的第(4)項指標和第(5)項指標互換。

基本算法A3：從算法A1修改而來。將定義12中的原第(5)項指標改為第(3)項指標，再將原第(3)、第(4)項指標改為第(4)、第(5)項指標。

基本算法A4：從算法A1修改而來。將定義12中的第(7)項指標和第(8)項指標互換。

基本算法A5：從算法A2修改而來。將定義12中的第(7)項指標和第(8)項指標互換。

基本算法A6：從算法A3修改而來。將定義12中的第(7)項指標和第(8)項指標互換。

基本算法A7～A12分別從算法A1～A6修改而來：將“動作的穴度，大優先”這項指標改為“動作的面積利用率，大優先”。

優美度枚舉子程序B1調用基本算法A1進行樹搜索。將優美度枚舉子程序所調用的基本算法分別替換成Ai，可以得到一個優美度枚舉子程序族Bi，其中1≤i≤12。

對于2.3節中的擬人型全局優化算法A1B1來說，它基于基本算法A1和優美度枚舉子程序B1，將A1和B1分別替換成Ai和Bi，可得到一個擬人型全局優化算法族AiBi，其中1≤i≤12。

3 算法優度的理論分析

定義17(布局優度) 布局優度是指在矩形容器內的矩形塊的面積和。

定理1(優度定理1) 優美度枚舉子程序第i+1輪計算所得最優布局的優度高于或等于第i輪計算所得最優布局的優度。

證明從略。

定理2(優度定理2) 第三優化階段所得布局的優度高于或等于第二優化階段所得布局的優度。

證明從略。

4 實驗結果與分析

4.1 二維矩形Strip Packing問題

本文算法是針對二維矩形Packing問題而設計的，也可用于求解二維矩形Strip Packing問題。Strip Packing問題是指：矩形容器的長度W固定，在滿足“不出界、不傾斜、不重疊”三個約束條件的前提下，要求用寬度H盡可能小的矩形容器將所有矩形塊裝入。

除了“不出界、不傾斜、不重疊”以外，很多文獻中還可能考慮另外兩個約束條件：第一個約束條件是“一刀切”約束；第二個約束條件是關于矩形塊的方向：可旋轉90°或者方向固定。根據這兩個約束條件將二維矩形Strip Packing問題分為如下四個子類：第一，RF子類：矩形塊的方向可旋轉90°，不考慮“一刀切”約束。第二，RG子類：矩形塊的方向可旋轉90°，考慮“一刀切”約束。第三，OF子類：矩形塊的方向固定，不考慮“一刀切”約束。第四，OG子類：矩形塊的方向固定，考慮“一刀切”約束。

本文算法用于計算OF子類。算法計算了6組benchmark問題實例：(1)C組(21個實例)，由Hopper和Turton[18]提出；(2)N組(13個實例)，由Burke[19]等人提出；(3)NT組(70個實例)，由Hopper和Turton[18]提出；(4)CX組(7個實例)，由Ferreira和Oliveira[20]提出；(5)2SP組(38個實例)，其中cgcut1-cgcut3由Christofides和Whitlock[21]提出，gcut1-gcut13和ngcut1-ngcut12由Beasley[22]提出，beng1-beng10由Bengtsson[23]提出；(6)ZDF組(16個實例)，由Riff等人[24]、Leung和Zhang[12]提出。

4.2 擬人型全局優化算法族求解Strip Packing問題

本文使用擬人型全局優化算法族來計算二維矩形Strip Packing問題。思路為：首先依次調用AiBi算法族按照跳躍式查找的方式計算，直到將所有矩形塊放入矩形容器為止，然后用折半查找的方式進一步縮小矩形容器的寬度，其中1≤i≤12。

具體計算步驟用偽C語言表示如下。

Step2調用AiBi算法族作跳躍式查找：

for(l=LB； ；l+=d){

finish_flag=0；

將矩形容器的寬度設定為l；

/*循環，依次調用算法族中的12個算法*/

for(i=1；i<=12；i++){

/*循環，依次選取不同的N值*/

for(N=5；N<=205；N+=100){

調用AiBi算法計算；

若矩形塊已全部放入矩形容器，則UB=l,finish_flag=1，break；}

if(finish_flag==1) break；}

if(finish_flag==1) break；}

if(UB==LB) 轉Step 4；

else 轉Step 3；

Step3調用AiBi算法族作折半查找：

head=UB-d+1；tail=UB-1；

while(head<=tail){

finish_flag=0；

mid=(head+tail)/2；

將矩形容器的寬度設定為mid；

for(i=1；i<=12；i++){

for(N=5；N<=205；N+=100){

調用AiBi算法計算；

若矩形塊已全部放入矩形容器，則UB=mid,finish_flag=1，break；}

if(finish_flag==1) break；}

if(finish_flag==1)tail=mid-1；

elsehead=mid+1；

}

Step4輸出UB值以及對應的布局。

對上述算法步驟補充說明：N值是優美度枚舉子程序的重要參數。N值較小時，計算時間較少，但可能漏掉好的占角動作；N值較大時，花時間較多，可能發現更好的布局。本文設定N值從5開始，每次遞增100，到205為止。

4.3 算法計算結果

本文提出的擬人型全局優化算法族AiBi用C語言實現，在CPU為3.0 GHz的個人電腦上做了測試。計算結果如表1～表5所示所示。

Table 1 Comparison of the computational results on the instances (OF)

AiBi與當前文獻中幾種較先進的算法做了比較。除了QH(Quasi-Human )算法[25]是一種非隨機型算法以外，GRASP(Greedy Randomized Adaptive Search Procedure)[11]、ISA(Intelligent Search Algorithm)[12]、IDBS(Iterative Doubling Binary Search)[13]、SRA(Simple Randomized Algorithm )[14]、HA(Hybrid Algorithm )[16]和AiBi算法均為隨機型算法。對每個問題實例，非隨機型算法只需計算一次，隨機型算法計算10次。

表1～表5中的符號含義列舉如下：對于一個問題實例(Instance)來說，n表示矩形塊數，W表示矩形容器的長度(固定值)，H*表示矩形容器的寬度的最小值或最小值的下界，H表示非隨機型算法所算出的矩形容器寬度，T表示計算時間，單位為s。對于隨機型算法來說，AH和BH分別表示10次計算所得到的矩形容器寬度的算術平均值和最小值。AT則表示10次計算時間的算術平均值。

表1給出了算法計算6組共165個benchmark實例的平均相對誤差，AiBi的平均相對誤差為1.05，在參加比較的7個算法中最小。

表2給出了算法計算C組實例的結果。AiBi的計算時間略長于QH算法，但所生成解的質量較高。除了C19和C21兩個實例以外，對本組其它19個實例均能算出最優解。

表3給出了算法計算N組實例的結果。AiBi算法生成了全部實例的最優解。

表4給出了算法計算CX組實例的結果。AiBi算法所生成布局的優度與QH算法相當。

表5給出了算法計算ZDF組實例的結果。除zdf6和zdf7以外，對本組其它19個實例均能算出最優解。算法對zdf6和zdf7所生成的布局刷新了當前文獻中已報道的記錄。

Table 2 Computational results on the instances C (OF)

Table 3 Computational results on the instances N(OF)

Table 4 Computational results on the instances CX(OF)

Table 5 Computational results on the instances ZDF(OF)

GRASP、ISA、IDBS、SRA、HA算法的每次計算的時間上限均為60 s。

AiBi算法計算所需時間總體上較長，生成布局的質量較高。在對布局質量要求高且計算時間限制較寬松的應用場景有其實用價值。

5 結束語

以占角式基本算法為基礎，本文提出了一種三階段擬人型全局優化算法，由鄰域搜索、跳坑策略、優美度枚舉組成。對benchmark問題實例的測試結果表明，算法生成布局的優度較高。

[1] Huang Wen-qi,Chen Duan-bing,Xu Ru-chu.A new heuristic algorithm for rectangle packing [J].Computers & Operations Research,2007,34(11):3270-3280.

[2] He Kun,Ji Peng-li,Li Chu-min.Dynamic reduction heuristics for the rectangle packing area minimization problem [J].European Journal of Operational Research,2015,241(3):674-685.

[3] Alvarez-Valdes R, Parreno F, Tammrit J M.A branch and bound algorithm for the strip packing problem [J].OR Spectrum,2009,31(2):431-459.

[4] Jiang Xing-bo, Lü Xiao-qing,Liu Cheng-cheng.Lowest-level left align best-fit algorithm for the 2D rectangular strip packing problem[J].Journal of Software,2009,20(6):1528-1538.(in Chinese)

[5] Cui Yao-dong, Yang Yu-li, Cheng Xian,et al.A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem[J].Computers & Operations Research,2008,35(4):1281-1291.

[6] He Kun, Huang Wen-qi,Jin Yan.Efficient algorithm based on action space for solving the 2D rectangular packing problem[J].Journal of Software,2012,23(5):1037-1044.(in Chinese)

[7] Wang Lei, Yin Ai-hua. A beauty degree enumeration algorithm for the 2D rectangular packing problem[J].Scientia Sinica Informationis,2015,45(9):1127-1140.(in Chinese)

[8] Huang Wen-qi,Chen Duan-bing.An efficient heuristic algorithm for rectangle-packing problem[J].Simulation Modelling and Practice Theory,2007,15(10):1356-1365.

[9] He Kun,Huang Wen-qi.An efficient place heuristic for three-dimensional rectangular packing[J].Computers & Operations Research,2011,38(1):227-233.

[10] Huang Wen-qi,He Kun.A pure quasi-human algorithm for solving the cuboid packing problem[J].Science in China Series F:Information Sciences,2009,52(1):52-58.

[11] Alvarez-Valdes R, Parreno F,Tammrit J M.Reactive GRASP for the strip-packing problem[J].Computers & Operations Research,2008,35(4):1065-1083.

[12] Leung S C H, Zhang De-fu.A two-stage intelligent search algorithm for the two-dimensional strip packing problem[J].European Journal of Operational Research,2011,215(1):57-69.

[13] Wei Li-jun,Oon Wee-chong, Zhu Wen-bin, et al. A skyline heuristic for the 2D rectangular packing and strip packing problems[J].European Journal of Operational Research,2011,215(2):337-346.

[14] Yang Shuang-yuan, Han Shui-hua, Ye Wei-guo.A simple randomized algorithm for two-dimensional strip packing[J].Computers & Operations Research,2013,40(1):1-8.

[15] Wei Li-jun, Qin Hu, Cheang B, et al.An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem[J].International Transactions in Operational Research,2016,232(1-2):65-92.

[16] Zhang De-fu,Che Yu-xin,Ye Fu-rong,et al.A hybrid algorithm based on variable neighborhood for the strip packing problem[J].Journal of Combinatorial Optimization,2016,32(2):513-530.

[17] He Kun,Huang Wen-qi,Jin Yan.An efficient deterministic heuristic for two-dimensional rectangular packing[J].Computers & Operations Research,2012,39(7):1355-1363.

[18] Hopper E,Turton B.An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem[J].European Journal of Operational Research,2001,128(1):34-57.

[19] Burke E,Kendall G,Whitwell G.A new placement heuristic for the orthogonal stock-cutting problem[J].Operations Research,2004,52(4):655-671.

[20] Ferreira E P, Oliveira J F.Algorithm based on graphs for the non-guillotinable two-dimensional packing problem[C]∥Proc of the 2nd ESICUP Meeting,2005:131-135.

[21] Christofides N, Whitlock C.An algorithm for two-dimensional cutting problem[J].Operations Research,1977,25(1):30-44.

[22] Beasley J. An exact two-dimensional non-guillotine cutting tree search procedure[J].Operations Research,1985,33(1):49-64.

[23] Bengtsson B E.Packing rectangular pieces-a heuristic approach[J].Computer Journal,1982,25(3):253-257.

[24] Riff M C,Bonnaire X,Neveu B.A revision of recent approaches for two-dimensional strip-packing problems[J].Engineering Applications of Artificial Intelligence,2009,22(4-5):823-827.

[25] Wang Lei,Yin Ai-hua.A quasi-human algorithm for the two dimensional rectangular strip packing problem:in memory of Prof.Wenqi Huang[J].Journal of Combinatorial Optimization,2016,32(2):416-444.

附中文參考文獻：

[4] 蔣興波,呂肖慶,劉成城.二維矩形條帶裝箱問題的底部左齊擇優匹配算法[J].軟件學報,2009,20(6):1528-1538.

[6] 何琨,黃文奇,金燕.基于動作空間求解二維矩形Packing問題的高效算法[J].軟件學報,2012,23(5):1037-1044.

[7] 王磊,尹愛華.求解二維矩形Packing問題的一種優美度枚舉算法[J].中國科學(信息科學),2015,45(9):1127-1140.