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

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

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

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

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

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

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

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

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

s.t. R滿足剪切工藝要求。

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

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

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

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

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

1 基本概念

1.1 條帶

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

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

圖1 條帶

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

三塊布局方式首先用一條主分界線將板材分為兩個(gè)塊，然后用一條輔分界線將其中的一塊再劃分為兩個(gè)塊。如圖 2所示，當(dāng)主分界線是豎直線時(shí)，稱為X向三塊布局方式；當(dāng)主分界線是水平線時(shí)，稱為Y向三塊布局方式。每個(gè)塊里面只包含方向和長度均相同的勻質(zhì)條帶。塊的方向由塊中條帶的方向決定，當(dāng)條帶方向是水平時(shí)稱為X向塊；當(dāng)條帶方向是豎直時(shí)稱為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 三塊布局方式的類型

圖3 三塊布局方式圖

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

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

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

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

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

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

對(duì)于塊x × y(長：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à)值。則有如下公式：

上述模型是典型的背包問題，可用動(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為主分界線位置，y為輔分界線位置。其中x，y均為整數(shù)。

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

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

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

采用文獻(xiàn)[11]Table 4的6道測題，板材規(guī)格均為3 000×1 500，毛坯的價(jià)值等于其面積。對(duì)于每道測題，文獻(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為測題的實(shí)驗(yàn)結(jié)果。圖4為本文算法生成的測題5的布局方式圖。

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

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

圖4 測題5的布局方式圖

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

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

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

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

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

圖5 測題APT16和APT20的布局方式圖

4 結(jié) 束 語

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

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

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

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

[5]張德富, 彭 煜, 張麗麗, 等. 求解三維裝箱問題的混合模擬退火算法[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

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

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