基于兩階段排放算法的矩形件排樣優化方法

許繼影 陳仕軍 鄭晴

摘? 要： 針對矩形件排樣問題，經典的最下左填充（BLF）算法易于出現區域浪費、原材料利用率低的缺點。對此，提出一種改進的兩階段排放算法。第一階段利用BLF算法，第二階段設計一個改進BLF排放算法以減小區域的浪費。再以矩形件排放順序進行編碼，利用兩階段排放算法解碼，設計鄰域搜索算法尋找最優解。通過已有文獻的多個案例，對改進的算法進行實驗驗證，結果與BLF算法相比，原材料利用率能提高14%，證實了改進算法的有效性。

關鍵詞： 矩形排樣; 排放算法; 兩階段; 鄰域搜索

Abstract： For the rectangle packing problems， the classical bottom-left fill （BLF） algorithm may give rise to the disadvantages of waste area and low utilization of raw materials. Accordingly， an improved packing algorithm with two-stage layout is presented. At the first stage， BLF algorithm is used to pack rectangular pieces. At the second stage， an altered BLF algorithm is presented to fill the left-top corner of the big rectangle. Then the rectangular pieces are encoded in the sequence of placing， the proposed two-stage packing algorithm is used for decoding， and a neighborhood search algorithm is designed to find the optimal solution. Through several cases in the existing literature， the improved algorithm is experimentally verified， and the results show that the utilization rate of raw material can be increased by 14%， by comparing with the BLF algorithm. It confirms the effectiveness of the improved algorithm.

0 引言

矩形件排樣問題（也稱下料問題）廣泛存在于玻璃切割、板材加工、布料裁剪等生產領域，對排樣或下料方案進行優化，是企業實現降低成本、提高材料利用率的重要途徑。傳統的人工制定排樣方案會耗費大量的人力和物力，而且材料利用率不高。因此，研究如何采用運籌和最優化方法，并輔助于計算機設備對排樣方案進行優化，以提高排樣方案的材料利用率，極具重要價值。

矩形件排樣問題是計算領域的NP難問題，目前不存在求最優解的多項式時間算法。經典的數學規劃方法復雜性太高，難以求解大規模問題。針對該問題，有些學者陸續提出一些求近似最優解的快速排放算法，例如Baker等人提出了最下左（bottom-left，BL）算法[1]，具有復雜度低易于實現的優點。但由于BL算法易產生過多的“空白區域”，考慮到排放利用率低的問題，Hopper與Turton提出一種能填充“空白區域”的最下最左填充（bottom-left-filling，BLF）[2]排放算法;賈志欣提出了一種最低水平線排放算法[3]。同時，BLF算法或最低水平線算法在應用時，矩形件的排放順序對排樣效果影響較大，依靠直觀經驗或隨機選取排放順序，但往往難以得到理想的排樣效果。為此，一些智能優化算法如模擬退火算法、遺傳算法、鄰域搜索算法等被用于求解矩形件排樣問題在內的各種優化問題[4]。Hopper與Turton[2]采用BLF排放算法和遺傳算法相結合，求解矩形件排樣問題。夏以沖等[5]提出遺傳算法和模擬退火算法相結合的方法;鄭明月[6]也采用遺傳算法和模擬退火算法相結合的方法，但采用了不同的融合策略;也有學者針對特定的下料場景，提出一些特定的下料方法[7-10]。雖然這些排放方法在一些特定排樣問題上取得了不錯的效果，但方法通用性不夠強，計算效率和排樣率仍然有較大的改進空間。

傳統的BLF算法[2]屬于經典的矩形排樣算法，具有復雜度低和易于實現的優點，應用較為廣泛。但BLF算法易出現大矩形左上方區域浪費的情況，因此提出一種改進的兩階段排放算法，并結合鄰域搜索算法，設計出新的矩形件排放算法。對文獻中的多個案例進行計算，對所提的改進算法進行實驗分析與比較，以驗證所提算法的有效性。

1 問題描述與數學模型

記大矩形原料板材的寬為W，高為H，以（W，H）表示;可排放的n個小矩形件分別為R1，R2，…，Rn。矩形件Ri的寬為wi，高為hi，以（wi，hi）（i=1，2，…，m）表示，所有小矩形件的面積之和大于大矩形件總面積，即。對于大矩形件板材，設置其左下角坐標為（0，0）;對于第i個小矩形件Ri，設其排放后的左下角坐標為（xi1，yi1），右上角坐標為（xi2，yi2），其排放前（沒選擇排放）的右上坐標為（0，0）。若矩形件Ri已排放至大矩形件，記zi=1;否則，zi=0。設M是充分大的正數，則矩形件排樣問題可表述成如下的整數規劃模型：

上述模型中，公式⑴為優化目標，即最大化排樣率;約束⑵與⑶說明小矩形件在板材上，其左下角坐標與右上角坐標的位置關系;約束⑷至⑻，保證板材上任意兩個排放的小矩形件互不重疊;約束⑼與⑽保證排放的矩形件不超過板材的邊界;約束⑿說明矩形件左下角和右上角排放位置的橫坐標與綜坐標均在整數位置，約束⑿表示是否排放矩形件Ri。

2 改進的兩階段排放算法

傳統的BLF算法[2]步驟如下：先將小矩形件按某種規則（如按面積從大到小）排好順序;再依次排放小矩形件，優先排放到已放置矩形件的空隙（浪費）區域，如果無法排放，再采用先向下、再向左循環移動，直到小矩形件無法移動為止。該算法每次考慮優先向下排放、再考慮向左排放，容易出現大矩形左上方浪費區域過大的問題。為此，提出一種改進的BLF算法，主要采取優先向左移動、再考慮向下移動，其算法流程如圖1所示。

改進的BLF算法克服了大矩形左上方易出現浪費區域的情形，但直接用該方法也會導致大矩形右下方出現浪費區域的現象。為此，設計一個兩階段排放算法：第一階段，利用傳統的BLF算法進行排放;第二階段，針對可能出現的左上方浪費區域，利用改進的BLF算法排放剩余的小矩形件。

3 基于兩階段排放算法和鄰域搜索相結合的排樣優化算法

利用兩階段排放算法時，矩形件的排放順序對最終的排樣效果（排樣率）有很大影響，因此需要找到最優的矩形件排放順序。基于兩點交換的鄰域搜索算法是一種常用優化算法，其算法復雜度低并且求解效率高。為此，先將所有小矩形件進行編碼（即小矩形件序號的排列），形成排放順序，再利用兩階段排放算法進行解碼。根據經驗可知，面積大的矩形件優先排放時，通常會取得更好效果。初始時，將所有小矩形件按面積從大到小排序，形成初始編碼。鄰域搜索算子采用兩點交換，即隨機交換編碼中兩個小矩形件的位置，保證了搜索解的多樣性。當兩點交換后，若不能改進當前最優解，則將這兩點繼續交換，即保持原編碼順序。基于鄰域搜索的矩形件排樣優化算法如圖2所示。

4 案例計算

采用Hopper和Turton給出的12組公開案例[2]，進行實驗計算。實驗過程中，以最終排樣率為指標，分別測試傳統BLF算法、改進的兩階段排放算法、基于鄰域搜索的排樣算法。在利用鄰域搜索算法時，迭代1000次尋找最優解。針對每個案例，運行10次鄰域搜索算法，并取10次中的最優解。最終計算的排樣率結果見表1。

表1中，第2列和第3列分別表示大矩形板材的尺寸和小矩形件的數量。通過表1的第4列至第6列可以看出，改進的兩階段排放算法與傳統的BLF算法相比較，前者的平均排樣率能提高8.8%。其中案例2和案例4，其排樣率沒有得到改進，是因為應用兩階段排放算法時，第一階段左上方沒有出現大的浪費區域。通過表1的第7列，可以看出在應用鄰域搜索算法后，平均排樣率達到了94.54%，相對于傳統的BLF算法提高了14.17%。因此，鄰域搜索算法表現出較強的全局尋優能力。

5 結束語

在求解矩形件排樣問題時，經典的BLF算法易出現左上方區域浪費的情況，本文提出了改進的兩階段排放算法，提高了排樣率。再將所提的兩階段排放算法與鄰域搜索算法相結合，設計出了更加高效的矩形件排樣優化算法，通過文獻中的一些案例驗證了算法的有效性。此外，如何進一步分析排樣問題的本質并提取有用的問題特征，以及基于此設計更高效的鄰域搜索算子，還需要進一步深入研究。

參考文獻（References）：

[1] Baker B S， Coffman E G， Rivest R L. Orthogonal Packingsin Two Dimensions[J]. SIAM Journal on Computing，1980.9（4）：846-855

[2] Hopper E， Turton B C H. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem[J]. European Journal of Operational Research，2001.128（1）：34-57

[3] 賈志欣，殷國富，羅陽，徐雷.矩形件排樣的模擬退火算法求解[J].四川大學學報（工程科學版），2001.33（5）：35-38

[4] Jain L， Singh G. A review meta-heuristic approaches forsolving rectangle packing problem[J]. International Journal of Computer Engineering and Technology，2013.4（2）：410-424

[5] 夏以沖，陳秋蓮，宋仁坤. 基于自適應遺傳模擬退火算法的矩形件排樣[J].計算機工程與應用，2018.54（22）：229-232，245

[6] 鄭明月.混合遺傳算法在矩形件帶排樣問題中的應用[D].合肥工業大學，2013.

[7] 扈少華，潘立武.矩形件五級剪切排樣方式的一種生成算法[J].鍛壓技術，2018.43（10）：190-194

[8] 朱強，薛峰，鄭仕勇，管衛利.約束二維排樣問題的一種求解算法[J].鍛壓技術，2016.41（9）：148-152

[9] 沈萍，鄧國斌.矩形件剪切下料問題的一種順序價值修正算法[J].鍛壓技術，2018.43（4）：180-184

[10] 扈少華，武書彥，潘立武.基于兩段排樣方式的矩形件優化下料算法[J].圖學學報，2018.39（1）：91-96