易向陽， 潘衛(wèi)平， 張俊暉

(1. 廣西大學計算機與電子信息學院，廣西 南寧 530004；2. 四川信息職業(yè)技術(shù)學院，四川 廣元 628017)

基于五塊模式的單一矩形件排樣算法

易向陽1， 潘衛(wèi)平1， 張俊暉2

(1. 廣西大學計算機與電子信息學院，廣西 南寧 530004；2. 四川信息職業(yè)技術(shù)學院，四川 廣元 628017)

如何在一個大矩形里排入盡可能多的單一規(guī)格小矩形件是廣泛出現(xiàn)在制造業(yè)領域的板材分割、物流業(yè)領域的集裝箱裝載中的問題。采用五塊模式將大矩形劃分為五個塊，求解每個塊里面矩形件的排樣方式。首先，采用動態(tài)規(guī)劃算法一次性生成所有塊中矩形件排樣方式，然后，采用隱式枚舉法考慮所有可能的五塊組合，選擇包含矩形件個數(shù)最多的五塊組合作為最終的排樣方案。使用算例對算法進行了測試，并與另外4種單一排樣算法進行了比較。實驗結(jié)果表明，該算法在排樣利用率和切割工藝兩方面都有效，而且計算時間合理。

矩形排樣問題；動態(tài)規(guī)劃算法；隱枚舉；五塊模式

本文討論單一矩形件排樣問題[1]：在尺寸為(L：長，W：寬)的大矩形中排入尺寸為(l，w)的小矩形件，優(yōu)化目標是使得排入的矩形件個數(shù)最多。該問題有2個主要的應用領域[2-4]：①下料領域，將矩形板材分割成最大數(shù)量的同種矩形件，提高材料利用率；②物流領域，用來確定托盤裝載、貨運裝載、

集裝箱裝船方案，充分利用裝載區(qū)域。為了敘述方便，本文主要采用下料領域的術(shù)語。該問題看似簡單，其實不然，文獻[5]認為該問題是高計算復雜度的NP難問題。目前國內(nèi)外已有一些學者分別提出了近似算法來解決此問題。其中最著名的當屬Agrawal單一排樣算法[6]，該算法能生成最優(yōu)剪切排樣方案。由分析可知，當使用氣焰分割技術(shù)分割板材時，排樣方案并不需要滿足剪切工藝要求，另外物流領域的托盤裝載方案顯然不需要滿足剪切工藝要求。鑒于此，本文對Agrawal單一布局算法進行擴展，使其能夠生成排樣利用率更高的非剪切排樣方案。

本文提出了基于五塊模式的單一矩形件排樣算法。采用動態(tài)規(guī)劃和隱式枚舉法相結(jié)合來求解排樣方案，并通過實驗驗證該算法的有效性。

1 相關(guān)概念

1.1 規(guī)范多級方式

定義 1. 條帶和級。若干個矩形件排列在一起組成條帶[7]，條帶分X向條帶(圖1(a))和Y向條帶(圖1(b))兩種類型。條帶的寬度等于矩形件的寬度，長度等于矩形件個數(shù)與矩形件長度之積。若干根方向相同的條帶組成級，級的方向由其中的條帶方向決定，包含X向條帶的級為X向級(圖2(a))，包含Y向條帶的級為Y向級(圖2(b))。

圖1 條帶

圖2 級

定義2. 規(guī)范多級方式。圖3所示為規(guī)范多級方式圖，每個級按照剪切時被切下的先后順序進行編號。其中，所有奇數(shù)級具有相同的方向，所有偶數(shù)級具有相同的方向，且奇數(shù)級與偶數(shù)級方向垂直[8]。崔耀東和周儒榮[9]已證明任何可以剪切下料的排樣方式都可以在矩形件個數(shù)不減少和級數(shù)不增加的情況下等價轉(zhuǎn)換為規(guī)范多級方式。

圖3 規(guī)范多級方式

1.2 五塊模式

五塊模式由5個塊組成，每個塊里面的矩形件都按照規(guī)范多級方式進行排放。塊的劃分見圖4，其中板材長為 L，寬為 W。從圖中可以看出：塊1(x1,y1)(長為 x1，寬為 y1)、塊 2(x2,y2)、塊塊其中x1,y1均大于0，。需要指出的是：本文的五塊模式和文獻[10]五塊方式是不同的，文獻[10]中每個塊里面是由若干排水平矩形件和若干排豎直矩形件的簡單組合。而本文每個塊里面矩形件是按照規(guī)范多級方式排放的，規(guī)范多級排樣方式是前者的超集。

圖4 五塊模式圖

如圖5所示，塊1中包含一個Y向級，塊2中包含一個Y向級，塊3中包含一個X向級和一個Y向級，塊4中包含一個X向級，塊5中為空。

圖5 單一矩形件五塊排樣方案

2 算法原理及其實現(xiàn)

假定板材尺寸和矩形件尺寸都為整數(shù)。對于規(guī)格為(L, W)的板材，假設L ≥ W。

2.1 確定塊的規(guī)范多級方式

對于塊(x,y)，x≤L，y≤W。規(guī)范多級方式的排樣過程可看作是一系列的條帶拼接過程，如圖6所示每次總是沿著當前方式的水平邊或豎直邊拼接上一根條帶，最終形成整塊上的排樣方式。設F(x,y)為塊(x,y)中所能排放的矩形件個數(shù)。則有如下遞推公式：

采用如下的動態(tài)規(guī)劃算法[8]生成所有塊的規(guī)范多級方式：

圖6 條帶的兩種拼接方式

2.2 塊的規(guī)范尺寸

規(guī)范尺寸概念已經(jīng)被許多學者使用在排樣問題中[11]，使用規(guī)范尺寸可以減少算法中不必要的計算開銷。設a為規(guī)范尺寸，則：a= n1l+ n2w, 0 ≤ a ≤ L，n1,n2均為非負整數(shù) (2)

令A為規(guī)范尺寸集合，n為集合A的元素個數(shù)。規(guī)范尺寸有如下性質(zhì)：假設 A(x)為不大于x的最大規(guī)范尺寸，則有 F(x,y)=F(A(x),A(y ))。

2.3 確定五塊排樣方案

設五塊排樣方案排放的矩形件個數(shù)為M。則有如下公式：

其中，x1、y1、x2、y2如圖 4所示，且均在集合 A中取值。該算法時間復雜度為 O(n4)。由于n遠遠小于L，故運用規(guī)范尺寸概念可以明顯地降低算法時間復雜度，減少計算時間開銷。

2.4 最優(yōu)五塊排樣算法

步驟 1. 輸入板材和矩形件尺寸數(shù)據(jù)；

步驟 2. 根據(jù) 2.1節(jié)所述算法確定所有可能尺寸的塊的規(guī)范多級排樣方式和排入的矩形件個數(shù)；

步驟 3. 根據(jù)式(2)確定集合A；

步驟 4. 根據(jù)式(3)用隱式枚舉法確定 x1、y1、x2、y2，并得到最終的五塊排樣方案。

3 實驗計算

目前尚沒見到有關(guān)于單一矩形件五塊排樣算

法的報道。實驗通過4組測題將本文排樣算法分別與Agrawal單一排樣算法、文獻[8]單一排樣算法、文獻[12]二劃分排樣算法、文獻[2]啟發(fā)式排樣算法進行比較，其中前3種算法屬于剪切排樣算法，第4種算法屬于非剪切排樣算法。用C++語言實現(xiàn)本文算法，在VC6.0平臺上進行實驗。實驗所用計算機為Inter(R) Pentium(R) CPU G630，主頻2.7 GHz，內(nèi)存2 GB。

3.1 與Agrawal單一排樣算法比較

隨機生成100道排樣例題，每道例題使用不同的板材和矩形件尺寸，表1所示為各變量均勻分布的范圍。表2為計算結(jié)果總結(jié)。從表2可以看出，本文算法在計算時間合理的前提下，平均排樣利用率比Agrawal算法提高了1.58%。圖7為其中一道例題在兩種算法下的排樣方案，板材長為200 cm，寬為100 cm，矩形件長為17 cm，寬為7 cm，Agrawal算法生成的排樣方案板材能排入165個矩形件，本文算法生成的排樣方案板材能排入168個矩形件。

表1 實驗數(shù)據(jù)分布范圍(cm)

表2 計算結(jié)果

圖7 兩種算法生成的排樣方案

3.2 與文獻[8]單一排樣算法比較

采用文獻[13]數(shù)據(jù)，含10道測題。矩形件尺寸均為(長320 mm，寬180 mm)，板材長寬尺寸的取值范圍均為(800～3 000 mm)。表3為10道測題的計算結(jié)果。記文獻[8]算法生成的排樣方案包含的矩形件個數(shù)為N1，參見文獻[13]的表1。記本文算法生成的排樣方案包含矩形件個數(shù)為N2。圖8為測題4在兩種算法下的排樣方案。

表3 10道測題的實驗結(jié)果

3.3 與文獻[12]二劃分排樣算法對比

采用文獻[12]例題2數(shù)據(jù)，板材長為3 000 mm，寬為2 000 mm；矩形件長為166 mm，寬為91 mm。文獻[12]二劃分裝盤遞歸算法生成的排樣方案可排入394個矩形件，本文算法生成的排樣方案如圖9所示，可排入396個矩形件。

3.4 與文獻[2]啟發(fā)式排樣算法對比例題：如何用長為300 cm，寬為200 cm的板材切割出最多數(shù)目的長為21 cm，寬為19 cm的矩形件？本文算法生成的排樣方案如圖 10所示，包含149個矩形件。文獻[2]算法生成的排樣方案也包含149個矩形件。但兩種排樣方案相比，本文排樣方案顯著簡化了切割工藝。

圖9 采用文獻[12]例題2數(shù)據(jù)，本文算法生成的排樣方案

圖10 例題用本文算法生成的排樣方案

4 結(jié) 束 語

本文提出了非剪切方式的單一矩形件五塊排樣方案，并采用動態(tài)規(guī)劃和隱式枚舉算法生成該種排樣方案。算法時間復雜度低，設計思路簡單明了，便于編寫相應軟件時應用參考。與剪切方式排樣算法相比，本文算法能夠生成排樣利用率更高的排樣方案。與非剪切排樣算法相比，本文算法生成的排樣方案能夠顯著地簡化切割工藝。將本文算法應用在集裝箱裝運領域，生成的排樣方案能夠較好地提升裝載空間利用率，簡化裝載操作。

[1] Birgin E G, Lobato R D, Morabito R. An effective recursive partitioning approach for the packing of identical rectangles in a rectangle [J]. Journal of the Operational Research Society, 2010, 61(2): 306-320.

[2] Scheithauer G, Terno J. The G4-heuristic for the pallet loading problem [J]. Journal of the Operational Research Society, 1996, 47(4): 511-522.

[3] W?scher G, Hau?ner H, Schumann H. An improved typology of cutting and packing problems [J]. European Journal of Operational Research, 2007, 183(3): 1109-1130.

[4] Lu Yiping, Cha Jianzhong. A fast algorithm for identifying minimum size instances of the equivalence classes of the pallet loading problem [J]. European Journal of Operational Research, 2014, 237(3): 794-801.

[5] Letchford A N, Amaral A. Analysis of upper bounds for the pallet loading problem [J]. European Journal of Operational Research, 2001, 132(3): 582-593.

[6] Agrawal P K. Minimising trim loss in cutting rectangular blanks of a single size from a rectangular sheet using orthogonal guill otine cuts [J]. European Journal of Operational Research, 1993, 64(3): 410-422.

[7] 潘衛(wèi)平, 陳秋蓮, 崔耀東, 等. 基于勻質(zhì)條帶的矩形件最優(yōu)三塊布局算法[J]. 圖學學報, 2015, 36(1): 7-11.

[8] 崔耀東. 計算機排樣技術(shù)及其應用[M]. 北京: 機械工業(yè)出版社, 2004: 94-125.

[9] 崔耀東, 周儒榮. 沖裁件有約束最優(yōu)剪切方式的設計[J]. 數(shù)學的實踐與認識, 2001, 31(2): 177-184.

[10] Bischoff E, Dowsland W B. An application of the micro to product design and distribution [J]. Journal of the Operational Research Society, 1982, 33(3): 271-280.

[11] 季 君, 陸一平, 查建中, 等. 生成矩形毛坯最優(yōu)兩段排樣方式的確定型算法[J]. 計算機學報, 2012, 35(1): 183-191.

[12] 孫 英, 何冬黎, 崔耀東. 生成最優(yōu)二劃分裝盤方案的遞歸算法[J]. 計算機仿真, 2009, 26(9): 160-163.

[13] 楊少杰, 崔耀東. 同尺寸矩形毛坯排樣算法[J]. 桂林理工大學學報, 2012, 32(4): 628-630.

Algorithm for Generating Five Block Mode Cutting Patterns of Single Rectangular Items

Yi Xiangyang1, Pan Weiping1, Zhang Junhui2
(1. Computer and Electronic Information College, Guangxi University, Nanning Guangxi 530004, China; 2. Sichuan Institute of Information Technology, Guangyuan Sichuan 628017, China)

It is widely appears in manufacturing field of plate segmentation and the logistics industry field of pallet loading that how to finding a maximal layout for identical small rectangles on a larger rectangle. The large rectangle is divided into five blocks using five-block mode, then the problem is solved to arrange the identical small rectangular into each blocks. Firstly, the dynamic programming method is used to generate the entire layout of rectangular in blocks in once. Then, the enumeration method is used to consider all of five blocks combination. The combination is selected to generate the final pattern which have the maximal number of rectangular. Several examples are used to test the proposed algorithm, and comparing the algorithm with other 4 kinds of single layout algorithm. The experimental results show that the algorithm is efficient in both the layout utilization rate and the cutting process with a reasonable computing time.

rectangle packing problem; dynamic programming algorithm; implicit enumeration; five block mode

TP 391

A

2095-302X(2015)04-0521-05

2014-10-29；定稿日期：2015-01-21

國家自然科學基金資助項目(61363026，71371058)；廣西高等教育教學改革工程重點資助項目(2013JGZ110)

易向陽(1973–)，男，廣西桂林人，講師，碩士。主要研究方向為優(yōu)化計算技術(shù)與CAD。E-mail：3106868978@qq.com

張俊暉(1983–)，男，四川合川人，講師，本科。主要研究方向為優(yōu)化計算技術(shù)和程序開發(fā)。E-mail：2228462300@qq.com