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

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

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

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

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

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

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

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

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

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

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

1 相關(guān)概念

1.1 規(guī)范多級(jí)方式

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

圖1 條帶

圖2 級(jí)

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

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

1.2 五塊模式

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

圖4 五塊模式圖

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

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

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

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

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

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

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

圖6 條帶的兩種拼接方式

2.2 塊的規(guī)范尺寸

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

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

2.3 確定五塊排樣方案

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

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

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

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

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

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

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

3 實(shí)驗(yàn)計(jì)算

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

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

3.1 與Agrawal單一排樣算法比較

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

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

表2 計(jì)算結(jié)果

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

3.2 與文獻(xiàn)[8]單一排樣算法比較

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

表3 10道測(cè)題的實(shí)驗(yàn)結(jié)果

3.3 與文獻(xiàn)[12]二劃分排樣算法對(duì)比

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

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

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

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

4 結(jié) 束 語(yǔ)

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

[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]. 圖學(xué)學(xué)報(bào), 2015, 36(1): 7-11.

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

[9] 崔耀東, 周儒榮. 沖裁件有約束最優(yōu)剪切方式的設(shè)計(jì)[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(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]. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(1): 183-191.

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

[13] 楊少杰, 崔耀東. 同尺寸矩形毛坯排樣算法[J]. 桂林理工大學(xué)學(xué)報(bào), 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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61363026，71371058)；廣西高等教育教學(xué)改革工程重點(diǎn)資助項(xiàng)目(2013JGZ110)

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

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