基于勻質(zhì)條帶的矩形件最優(yōu)三塊布局算法

潘衛(wèi)平， 陳秋蓮， 崔耀東， 陳怡丹

(廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧530004)

基于勻質(zhì)條帶的矩形件最優(yōu)三塊布局算法

潘衛(wèi)平， 陳秋蓮， 崔耀東， 陳怡丹

(廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧530004)

為解決大規(guī)模矩形件布局問(wèn)題，提出一種動(dòng)態(tài)規(guī)劃算法生成基于勻質(zhì)條帶的矩形件最優(yōu)三塊布局方式。這種算法將板材分為三個(gè)塊，同一塊中只包含方向和長(zhǎng)度均相同的勻質(zhì)條帶。通過(guò)求解背包模型生成塊中的條帶最優(yōu)布局，隱枚舉的討論所有可能尺寸的塊，確定所有三塊組合的布局價(jià)值，選擇布局價(jià)值最大的一個(gè)組合作為最優(yōu)解。通過(guò)文獻(xiàn)中的測(cè)題，將該算法與經(jīng)典兩段布局算法和啟發(fā)式布局算法 TABU500進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明：該算法在計(jì)算時(shí)間和材料利用率兩方面都有效，且生成的布局方式簡(jiǎn)化了下料切割工藝。

下料；三塊布局方式；勻質(zhì)條帶；背包模型

切割與裝填布局(cutting and packing, C&P)[1]問(wèn)題是一個(gè)古老的著名問(wèn)題，廣泛存在于計(jì)算機(jī)科學(xué)、工業(yè)工程、邏輯學(xué)、制造業(yè)等領(lǐng)域。從數(shù)學(xué)和計(jì)算復(fù)雜性理論上看C&P是一類(lèi)典型的NP難度問(wèn)題[2-4]，至今人們尚無(wú)法給出既完整、精確又快速、高效的求解方法。針對(duì)不同領(lǐng)域的應(yīng)用需要，眾多學(xué)者提出了相應(yīng)的模型和算法[4-7]。特別是在制造業(yè)領(lǐng)域，隨著資源和能源危機(jī)的出現(xiàn)，要求各企業(yè)提高原材料利用率、減少切割能源消耗，于是迫切需要人們研制出下料利用率高且切割工藝簡(jiǎn)單的布局優(yōu)化算法。

本文討論二維無(wú)約束剪切布局(unconstrained two-dimensional cutting packing, UTDCP)問(wèn)題：將大板材L×W切割成m種小矩形件毛坯，第i種毛坯尺寸為 li×wi，價(jià)值為 ci(i=1,2,…,m)。對(duì)每種毛坯在板材中出現(xiàn)的次數(shù)無(wú)約束，布局目標(biāo)是使得布局價(jià)值(板材中所含毛坯的總價(jià)值)最大。令R為一個(gè)布局方式，zi為此布局方式包含第i種毛坯的個(gè)數(shù)。優(yōu)化模型為：

s.t. R滿(mǎn)足剪切工藝要求。

與 UTDCP問(wèn)題緊密相關(guān)的是二維剪切下料(two-dimensional cutting stock, TDCS)問(wèn)題：將庫(kù)存板材剪切出一定數(shù)量的若干種不同尺寸的矩形毛坯，優(yōu)化目標(biāo)是使得消耗的板材總面積最小。下料問(wèn)題的解是由一組布局方式組成，每種布局方式由相應(yīng)的UTDCP算法生成。經(jīng)常采用線(xiàn)性規(guī)劃(linear programming, LP)法求解TDCS問(wèn)題。LP法通過(guò)反復(fù)迭代求解，每次迭代都需調(diào)用UTDCP算法生成一個(gè)新的布局方式。通常在LP法找到最優(yōu)解之前，需要求解出幾千個(gè) UTDCP問(wèn)題，一個(gè)UTDCP問(wèn)題耗時(shí)一秒，求解TDCS問(wèn)題需耗時(shí)幾千秒[8]。因此UTDCP算法不僅要求布局價(jià)值較大，而且耗時(shí)短。

針對(duì)UTDCP問(wèn)題的算法可以分為三類(lèi)：①生成普通布局方式的精確算法[9]；②生成普通布局方式的啟發(fā)式算法，比如TABU500[10]；③生成特定布局方式的確定性算法，比如兩段布局算法[11]。

精確算法可生成最優(yōu)普通布局方式，但其解決問(wèn)題所耗費(fèi)的時(shí)間是人們所不能容忍的[12]。啟發(fā)式算法速度總體上比精確算法要快，但是其收斂速度未知，且無(wú)法保證解的質(zhì)量。確定性算法是對(duì)生成的布局方式做一些特定限制，從而能在確定的較短時(shí)間內(nèi)得到切割工藝簡(jiǎn)單、布局價(jià)值較高的布局方式。本文主要研究確定性布局算法。

文獻(xiàn)[13]和[11]采用遞歸算法分別生成T型布局方式和兩段布局方式。以上兩種布局方式都是先將板材分成兩段，然后在段上進(jìn)行條帶布局，各段的長(zhǎng)寬固定了一個(gè)尺寸，其數(shù)值為板材的長(zhǎng)或?qū)挕６纬叽绻潭艘粋€(gè)指標(biāo)勢(shì)必降低了段的靈活度，制約了布局價(jià)值的提高。對(duì)文獻(xiàn)[11]布局方式進(jìn)行擴(kuò)展，用兩根互相垂直的分界線(xiàn)將板材劃分成可以任意取值的三塊。分析以上三種布局方式的幾何性質(zhì)可以得出：T型布局方式?兩段布局方式?三塊布局方式。故最優(yōu)三塊布局方式的價(jià)值在理論上大于等于最優(yōu)兩段布局方式的價(jià)值是確定的。

本文提出動(dòng)態(tài)規(guī)劃思想的確定性布局算法來(lái)生成新的布局方式——?jiǎng)蛸|(zhì)條帶三塊布局方式(homogeneous three block strip, HTBS)，并通過(guò)實(shí)驗(yàn)驗(yàn)證該布局算法(HTBSA)的有效性。

1 基本概念

1.1 條帶

假定毛坯的方向固定。此假定并不影響本文算法的通用性，若允許毛坯轉(zhuǎn)向，則可把毛坯 li×wi看作規(guī)格為li× wi和wi× li的兩種毛坯。

一個(gè)或多個(gè)毛坯排成一行(列)，稱(chēng)作條帶。條帶有普通條帶和勻質(zhì)條帶兩種類(lèi)型，如圖1所示，數(shù)字表示毛坯編號(hào)。普通條帶可含多種毛坯，勻質(zhì)條帶只含一種毛坯。勻質(zhì)條帶利用率比普通條帶利用率稍低，但切割工藝比較簡(jiǎn)單。

圖1 條帶

1.2 勻質(zhì)條帶三塊布局方式

三塊布局方式首先用一條主分界線(xiàn)將板材分為兩個(gè)塊，然后用一條輔分界線(xiàn)將其中的一塊再劃分為兩個(gè)塊。如圖 2所示，當(dāng)主分界線(xiàn)是豎直線(xiàn)時(shí)，稱(chēng)為X向三塊布局方式；當(dāng)主分界線(xiàn)是水平線(xiàn)時(shí)，稱(chēng)為Y向三塊布局方式。每個(gè)塊里面只包含方向和長(zhǎng)度均相同的勻質(zhì)條帶。塊的方向由塊中條帶的方向決定，當(dāng)條帶方向是水平時(shí)稱(chēng)為X向塊；當(dāng)條帶方向是豎直時(shí)稱(chēng)為Y向塊。圖3是一個(gè)X向三塊布局方式圖(布局同圖2(a))，A塊里面包含1號(hào)、7號(hào)、19號(hào)三條水平條帶；B塊包含一條22號(hào)水平條帶；C塊里面包含兩條24號(hào)、一條26號(hào)、一條30號(hào)豎直條帶。

圖2 三塊布局方式的類(lèi)型

圖3 三塊布局方式圖

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

假設(shè)板材的尺寸和毛坯的尺寸都為整數(shù)，毛坯不允許轉(zhuǎn)向。對(duì)于規(guī)格為L(zhǎng) W× 的板材，假定L W≥ ?，F(xiàn)介紹生成最優(yōu)HTBS布局方式的方法，包含以下步驟：①求解條帶的價(jià)值；②確定條帶在塊中的最優(yōu)布局；③確定最優(yōu)三塊布局方式。

2.1 求解條帶的價(jià)值

令 n(i,x) i x為水平條帶ix w× (長(zhǎng)：x，寬：iw)中所含毛坯的個(gè)數(shù)， s(i,x)為條帶的價(jià)值，則有如下公式：

對(duì)于豎直條帶可以類(lèi)似的確定其價(jià)值 s( i, y)。

2.2 確定塊中條帶的最優(yōu)布局

對(duì)于塊x × y(長(zhǎng)：x，寬：y)，記 f( x, y)為塊的價(jià)值，x ≤ L，y ≤ W。對(duì)X向塊，令 zX(i, x)為塊中包含水平條帶 x × wi的個(gè)數(shù)， fX(x, y)為塊價(jià)值；對(duì)Y向塊，令 zY(i, y)為塊中包含豎直條帶 y ×li的個(gè)數(shù)， fY(x, y)為塊價(jià)值。則有如下公式：

上述模型是典型的背包問(wèn)題，可用動(dòng)態(tài)規(guī)劃方法求解。因?yàn)閯?dòng)態(tài)規(guī)劃方法具有全容量性，所以當(dāng)求解出 f(L,W) 后，其他的y W≤ 均可得知。

2.3 確定最優(yōu)三塊布局方式

用XV，YV分別表示最優(yōu)X向三塊布局方式與最優(yōu)Y向三塊布局方式的價(jià)值，V為最終的三塊布局方式價(jià)值。則有如下公式：

式(5)中x為主分界線(xiàn)位置，y為輔分界線(xiàn)位置。其中x，y均為整數(shù)。

式(6)中y為主分界線(xiàn)位置，x為輔分界線(xiàn)位置。其中y，x均為整數(shù)。

式(7)說(shuō)明選擇X向三塊方式和Y向三塊方式中價(jià)值較大的作為最終的三塊布局方式。

2.4 三塊布局算法的時(shí)間復(fù)雜度

式(1)求解條帶價(jià)值時(shí)間復(fù)雜度為 O( m L)。式(2)~(4)求解塊價(jià)值時(shí)間復(fù)雜度為 O( m WL)。式(5)~(7)確定最優(yōu)三塊布局方式時(shí)間復(fù)雜度為 O( W L)。

綜上得出：三塊布局算法總的時(shí)間復(fù)雜度為O( mWL)。

3 實(shí)驗(yàn)結(jié)果

用C#語(yǔ)言實(shí)現(xiàn)本文算法，在主頻為2.7 GHz，內(nèi)存為2 GB的計(jì)算機(jī)上進(jìn)行實(shí)驗(yàn)。通過(guò)文獻(xiàn)中的基準(zhǔn)測(cè)題，將本文算法分別與兩段布局算法和啟發(fā)式布局算法TABU500進(jìn)行比較。

3.1 第一組測(cè)題的實(shí)驗(yàn)結(jié)果

采用文獻(xiàn)[11]Table 4的6道測(cè)題，板材規(guī)格均為3 000×1 500，毛坯的價(jià)值等于其面積。對(duì)于每道測(cè)題，文獻(xiàn)[9]中算法可生成最優(yōu)普通布局方式，文獻(xiàn)[11]中算法可生成最優(yōu)勻質(zhì)條帶兩段布局方式，本文算法生成最優(yōu)勻質(zhì)條帶三塊布局方式。設(shè)v1、v2、v3，t1、t2、t3分別為以上三種算法的布局方式價(jià)值和所花的計(jì)算時(shí)間(s)。表 1為測(cè)題的實(shí)驗(yàn)結(jié)果。圖4為本文算法生成的測(cè)題5的布局方式圖。

從表1可以看出在6道測(cè)題中，本文算法優(yōu)化結(jié)果有4道測(cè)題好于兩段布局算法(用“+”標(biāo)記)，其余2道等于兩段布局算法(用“=”標(biāo)記)。本文算法計(jì)算時(shí)間和兩段布局算法相當(dāng)，在實(shí)際應(yīng)用中合理。

表1 第一組測(cè)題的實(shí)驗(yàn)結(jié)果(6道測(cè)題)

圖4 測(cè)題5的布局方式圖

3.2 第二組測(cè)題的實(shí)驗(yàn)結(jié)果

本節(jié)包含20道規(guī)模較大的布局測(cè)題，參考文獻(xiàn)[10]。其中前 10道測(cè)題，毛坯的價(jià)值即為其面積，后10道測(cè)題毛坯的價(jià)值和其面積是獨(dú)立的。設(shè)文獻(xiàn)[9]精確算法得到的布局方式價(jià)值為 v1、文獻(xiàn)[10]啟發(fā)式算法TABU500得到的布局方式價(jià)值為 v2、本文算法得到的布局方式價(jià)值為 v3。表 2為三種布局方式價(jià)值的比較結(jié)果。

在 20道測(cè)題中，本文算法的優(yōu)化結(jié)果有 13道測(cè)題好于 TABU500(用“+”標(biāo)記)，有 4道等于TABU500(用“=”標(biāo)記)，有3道差于TABU500(用“–”標(biāo)記)。本文算法平均布局價(jià)值為 4 426 952，TABU500平均布局價(jià)值為4 413 688。本文算法布局價(jià)值總體上高于TABU500。

TABU500解決20道測(cè)題耗時(shí)218 s，平均每道測(cè)題計(jì)算時(shí)間為10.9 s。本文算法解決20道測(cè)題總共耗時(shí)0.46 s，平均每道測(cè)題計(jì)算時(shí)間為0.023 s，計(jì)算時(shí)間只有TABU500算法的0.21%。圖6給出了本文算法生成的測(cè)題APT16和APT20的布局方式圖。

表2 第二組測(cè)題三種布局方式價(jià)值比較結(jié)果(20道測(cè)題)

圖5 測(cè)題APT16和APT20的布局方式圖

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

本文討論了矩形件無(wú)約束兩維布局問(wèn)題。提出了一種新型布局方式——HTBS布局方式，并采用HTBSA算法來(lái)生成此種布局方式。該布局方式切割工藝比較簡(jiǎn)單，能夠提高下料效率節(jié)省切割能耗。HTBSA算法其平均布局價(jià)值高于兩段布局算法和TABU500。將本文算法和線(xiàn)性規(guī)劃法相結(jié)合，可以較好地解決TDCS問(wèn)題。

[1]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.

[2]鄭榮杰, 張鵬程, 崔海良, 等. 基于蒙特卡羅方法的矩形布局問(wèn)題研究[J]. 圖學(xué)學(xué)報(bào), 2012, 33(4): 33-36.

[3]王金敏, 王保春, 朱艷華. 求解矩形布局問(wèn)題的自適應(yīng)算法[J]. 圖學(xué)學(xué)報(bào), 2012, 33(3): 29-33.

[4]何 琨, 黃文奇, 金 燕. 基于動(dòng)作空間求解二維矩形Packing問(wèn)題的高效算法[J]. 軟件學(xué)報(bào), 2012, 23(5): 1037-1044.

[5]張德富, 彭 煜, 張麗麗, 等. 求解三維裝箱問(wèn)題的混合模擬退火算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(12): 2553-2561.

[6]Cui Yaodong. Heuristic for the cutting and purchasing decisions of multiple metal coils [J]. Omega, 2014, 46: 117-125.

[7]Furini F, Malaguti E. Models for the two-dimensional two-stage cutting stock problem with multiple stock size [J]. Computers & Operations Research, 2013, 40(8): 1953-1962.

[8]Cui Yaodong. A new dynamic programming procedure for three-staged cutting patterns [J]. Journal of Global Optimization, 2013, 55(2): 349-357.

[9]Wang Z, Li J, Cui Y. Exact and heuristic algorithms for staged cutting problems [J]. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 2005, 219(2): 201-207.

[10]Alvarez-Valdés R, Parajón A, Tamarit J M. A tabu search algorithm for large-scale guillotine (un) constrained two-dimensional cutting problems [J]. Computers & Operations Research, 2002, 29(7): 925-947.

[11]Cui Yaodong, He Dongli, Song Xiaoxia. Generating optimal two-section cutting patterns for rectangular blanks [J]. Computers & Operations Research, 2006, 33(6): 1505-1520.

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

[13]崔耀東. 生成矩形毛坯最優(yōu)T型排樣方式的遞歸算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2006, 18(1): 111-114.

An Algorithm for Generating Optimal Homogeneous Strips Three Block Patterns of Rectangular Blanks

Pan Weiping, Chen Qiulian, Cui Yaodong, Chen Yidan
(Computer and Electronic Information College, Guangxi University, Nanning Guangxi 530004, China)

With the purpose of solve the large scale rectangular blanks packing problem, a dynamic programming algorithm for generating the optimal homogeneous strip three block layouts is presented. The plate is divided into 3 blocks, and every block contains only uniform strips which have the same direction and length. The knapsack model to generate the optimal strip layout on the block is firstly solved, and all possible sizes of blocks through implicit enumeration are discussed. All three block layout value is determined, and a layout of the maximum value is selected as the optimal solution. The algorithm was tested on some problems in the literature, and compared with the two algorithms which are classical two segment layout algorithm and heuristic algorithm of TABU500. The experimental results show that the algorithm not only can improve the utilization rate of material, but also has a reasonable computation time and can simplify the cutting process.

stock packing; three block patterns; homogeneous strip; knapsack model

TH 164；TP 301.6

A

2095-302X(2015)01-0007-05

2014-07-18；定稿日期：2014-09-16

國(guó)家自然科學(xué)基金資助項(xiàng)目(61363026，71371058)；廣西省自然科學(xué)基金資助項(xiàng)目(2014GXNSFAA118357)

潘衛(wèi)平(1989–)，男，湖北武穴人，碩士研究生。主要研究方向?yàn)閮?yōu)化計(jì)算與CAD技術(shù)。E-mail：1102358841@qq.com