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

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

(廣西大學計算機與電子信息學院，廣西 南寧530004)

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

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

(廣西大學計算機與電子信息學院，廣西 南寧530004)

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

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

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

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

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

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

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

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

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

本文提出動態(tài)規(guī)劃思想的確定性布局算法來生成新的布局方式——勻質條帶三塊布局方式(homogeneous three block strip, HTBS)，并通過實驗驗證該布局算法(HTBSA)的有效性。

1 基本概念

1.1 條帶

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

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

圖1 條帶

1.2 勻質條帶三塊布局方式

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

圖2 三塊布局方式的類型

圖3 三塊布局方式圖

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

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

2.1 求解條帶的價值

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

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

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

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

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

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

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

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

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

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

2.4 三塊布局算法的時間復雜度

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

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

3 實驗結果

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

3.1 第一組測題的實驗結果

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

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

表1 第一組測題的實驗結果(6道測題)

圖4 測題5的布局方式圖

3.2 第二組測題的實驗結果

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

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

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

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

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

4 結 束 語

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

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

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

[5]張德富, 彭 煜, 張麗麗, 等. 求解三維裝箱問題的混合模擬退火算法[J]. 計算機學報, 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]. 計算機學報, 2012, 35(1): 183-189.

[13]崔耀東. 生成矩形毛坯最優(yōu)T型排樣方式的遞歸算法[J]. 計算機輔助設計與圖形學學報, 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

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

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