基于兩階段排放算法的矩形件排樣優(yōu)化方法

許繼影 陳仕軍 鄭晴

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

關(guān)鍵詞： 矩形排樣; 排放算法; 兩階段; 鄰域搜索

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 引言

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

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

傳統(tǒng)的BLF算法[2]屬于經(jīng)典的矩形排樣算法，具有復(fù)雜度低和易于實(shí)現(xiàn)的優(yōu)點(diǎn)，應(yīng)用較為廣泛。但BLF算法易出現(xiàn)大矩形左上方區(qū)域浪費(fèi)的情況，因此提出一種改進(jìn)的兩階段排放算法，并結(jié)合鄰域搜索算法，設(shè)計(jì)出新的矩形件排放算法。對文獻(xiàn)中的多個案例進(jìn)行計(jì)算，對所提的改進(jìn)算法進(jìn)行實(shí)驗(yàn)分析與比較，以驗(yàn)證所提算法的有效性。

1 問題描述與數(shù)學(xué)模型

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

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

2 改進(jìn)的兩階段排放算法

傳統(tǒng)的BLF算法[2]步驟如下：先將小矩形件按某種規(guī)則（如按面積從大到?。┡藕庙樞?再依次排放小矩形件，優(yōu)先排放到已放置矩形件的空隙（浪費(fèi)）區(qū)域，如果無法排放，再采用先向下、再向左循環(huán)移動，直到小矩形件無法移動為止。該算法每次考慮優(yōu)先向下排放、再考慮向左排放，容易出現(xiàn)大矩形左上方浪費(fèi)區(qū)域過大的問題。為此，提出一種改進(jìn)的BLF算法，主要采取優(yōu)先向左移動、再考慮向下移動，其算法流程如圖1所示。

改進(jìn)的BLF算法克服了大矩形左上方易出現(xiàn)浪費(fèi)區(qū)域的情形，但直接用該方法也會導(dǎo)致大矩形右下方出現(xiàn)浪費(fèi)區(qū)域的現(xiàn)象。為此，設(shè)計(jì)一個兩階段排放算法：第一階段，利用傳統(tǒng)的BLF算法進(jìn)行排放;第二階段，針對可能出現(xiàn)的左上方浪費(fèi)區(qū)域，利用改進(jìn)的BLF算法排放剩余的小矩形件。

3 基于兩階段排放算法和鄰域搜索相結(jié)合的排樣優(yōu)化算法

利用兩階段排放算法時，矩形件的排放順序?qū)ψ罱K的排樣效果（排樣率）有很大影響，因此需要找到最優(yōu)的矩形件排放順序?；趦牲c(diǎn)交換的鄰域搜索算法是一種常用優(yōu)化算法，其算法復(fù)雜度低并且求解效率高。為此，先將所有小矩形件進(jìn)行編碼（即小矩形件序號的排列），形成排放順序，再利用兩階段排放算法進(jìn)行解碼。根據(jù)經(jīng)驗(yàn)可知，面積大的矩形件優(yōu)先排放時，通常會取得更好效果。初始時，將所有小矩形件按面積從大到小排序，形成初始編碼。鄰域搜索算子采用兩點(diǎn)交換，即隨機(jī)交換編碼中兩個小矩形件的位置，保證了搜索解的多樣性。當(dāng)兩點(diǎn)交換后，若不能改進(jìn)當(dāng)前最優(yōu)解，則將這兩點(diǎn)繼續(xù)交換，即保持原編碼順序?；卩徲蛩阉鞯木匦渭艠觾?yōu)化算法如圖2所示。

4 案例計(jì)算

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

表1中，第2列和第3列分別表示大矩形板材的尺寸和小矩形件的數(shù)量。通過表1的第4列至第6列可以看出，改進(jìn)的兩階段排放算法與傳統(tǒng)的BLF算法相比較，前者的平均排樣率能提高8.8%。其中案例2和案例4，其排樣率沒有得到改進(jìn)，是因?yàn)閼?yīng)用兩階段排放算法時，第一階段左上方?jīng)]有出現(xiàn)大的浪費(fèi)區(qū)域。通過表1的第7列，可以看出在應(yīng)用鄰域搜索算法后，平均排樣率達(dá)到了94.54%，相對于傳統(tǒng)的BLF算法提高了14.17%。因此，鄰域搜索算法表現(xiàn)出較強(qiáng)的全局尋優(yōu)能力。

5 結(jié)束語

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

參考文獻(xiàn)（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].四川大學(xué)學(xué)報（工程科學(xué)版），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] 夏以沖，陳秋蓮，宋仁坤. 基于自適應(yīng)遺傳模擬退火算法的矩形件排樣[J].計(jì)算機(jī)工程與應(yīng)用，2018.54（22）：229-232，245

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

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

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

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

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