基于梯形和平行四邊形的圓片剪沖下料算法設計與實現

陳 燕， 劉 詠， 謝琪琦， 崔耀東

(1. 廣西大學計算機與電子信息學院，廣西 南寧 530004；2. 華南理工大學工商管理學院，廣東 廣州 510640)

基于梯形和平行四邊形的圓片剪沖下料算法設計與實現

陳 燕1,2， 劉 詠1， 謝琪琦1， 崔耀東1

(1. 廣西大學計算機與電子信息學院，廣西 南寧 530004；2. 華南理工大學工商管理學院，廣東 廣州 510640)

提出一種在矩形板材上引入梯形條帶來進行排樣的方法，首先用兩條平行的分界線將板材分為兩個大小一致的直角梯形段和一個平行四邊形段，分別采用遞歸算法和動態規劃算法確定梯形段和平行四邊形段中條帶的最優組合，從而確定最優排樣方式；再結合線性規劃算法解決圓片下料問題，使得整個下料方案的材料利用率最大化。最后采用大量隨機生成的例題進行實驗，實驗結果表明該算法能有效提高材料利用率。

圓片排樣；剪沖下料；平行四邊形條帶；梯形條帶

隨著資源和能源危機的出現，要求各企業不斷提高原材料利用率、減少切割能源消耗，于是研究下料利用率高且切割工藝簡單的布局優化算法，切割與裝填布局(cutting and packing, C&P)[1]問題越來越受到各制造企業的關注。特別地，圓片下料問題廣泛存在機械制造、電機、船舶、航空航天等行業中，例如：電機定子和轉子鐵心是用硅鋼圓片制作而成；家居的鍋、壺、盆是用不

銹鋼圓片制作的，等等。這些行業每年消耗的金屬板材量達千萬噸，且原材料費用占生產成本的60%以上，因此提高材料利用率能夠為企業帶來非常可觀的經濟效益。將圓片下料技術應用于企業生產實踐，能有效地提高下料利用率、節省原材料、提高企業在同行中的競爭力[2]。

近年來，針對圓片條帶剪沖下料問題的方法研究，主要有矩形條帶進行排樣的方法[3-8]和采用平行四邊形條帶進行排樣的方法[9]等。文獻中有關矩形條帶進行排樣的方式也各有不同，其中：文獻[3]采用動態規劃算法在精確算法的基礎上，選取規范長度和規范寬度的子集進行計算，解決剪切階段的無約束排樣問題。文獻[4]利用動態規劃算法生成T形排樣的方式；文獻[5]采用動態規劃算法生成多段排樣的方式；文獻[6]采用動態規劃算法與枚舉法結合生成三塊結構的排樣方式。文獻[7] 和[8]均采用生成四塊結構的排樣方式，文獻[7]的算法是先求解一維背包問題生成塊里面的條帶最優布局，然后用隱式枚舉三條分界線位置得到所有可能的四塊組合，選擇排樣價值最大的四塊組合生成最優的四塊排樣方式；而文獻[8]同時使用條帶直切排樣方式和 T型排樣方式，先采用動態規劃技術生成排樣方式，然后采用基于列生成的線性規劃技術迭代調用排樣方式生成下料方案。文獻[9]基于卷材首次采用平行四邊形條帶進行排樣，通過不斷地重復最優的x段和y段，使排樣達到全局最優，同時驗證了相對于矩形條帶排樣平行四邊形條帶排樣可以獲得更高的材料利用率。卷材的特點是材料長度不受限，根據對多家企業包括寶鋼、武鋼的板材加工配送中心調查研究，目前實際生產剪裁下料中各企業使用的材料絕大部分是相對固定大小的板材[10]。

本文基于平行四邊形排樣以獲取更高的材料利用率，同時可避免在矩形板材上切割平行四邊而產生直角三角形的廢料，創新性地引入了梯形條帶排樣方式。首先在固定大小的矩形板材上用兩條平行的分界線將板材切割成兩個大小一致的直角梯形段和一個平行四邊形段，然后應用平行四邊形條帶及梯形條帶組合排樣的三段排樣方式。本文算法能保證在整板上切割兩刀即可產生最優的平行四邊形條帶和梯形條帶，從而對降低總的生產成本、減少板材大面積損耗概率提供保障。首先分別采用遞歸算法和動態規劃算法確定梯形條帶和平行四邊形段中條帶的最優組合，從而確定當前的最優排樣方式；然后應用線性規劃(linear programming, LP)方法求解圓片剪沖下料問題 (cutting stock problem of circular blanks, CSPCB)，使得整個下料方案的材料利用率接近最優；最后通過與其他采用固定大小板材進行排樣的算法實驗說明本文算法對板材利用率的提高，同時分析條帶中排入毛坯行數對材料利用率的影響，還分析了算法的時間復雜度和計算產生最優排樣方案所消耗的時間。實驗數據表明，本文算法是有效性的、計算時間是可接受的。

1 排樣方式算法原理及其實現

1.1 相關概念

1.1.1 毛坯在條帶上的排列、條帶方向和長度

本文算法在矩形板材上同時應用平行四邊形條帶和直角梯形條帶進行排樣，平行四邊形條帶可以是X向或Y向，梯形條帶只允許X向條帶。如圖1(a)中的箭頭方向表示該條帶是X向，圖1(b)中的箭頭方向表示該條帶是Y向，X向條帶中毛坯是從左至右依次排放；Y向條帶中毛坯是從下至上依次排放。平行四邊形Y向條帶可由平行四邊形X向條帶旋轉60°得到。

圖1 條帶方向及毛坯排列

每根條帶包含一排或者多排直徑相同的圓片，如圖2所示，d為圓片直徑，相鄰圓片邊界距離為w，即為工藝余量，圓片離條帶邊界的距離為w/2，相鄰兩排圓片間的距離為，平行四邊形條帶和梯形條帶的底角均為60°。

圖2 雙排條帶

圖3(a)為平行四邊形條帶排列示意圖，sh為平行四邊形中與條帶方向垂直的高度，ps為平行四邊形中不與條帶方向平行的底邊長度。圖3(b)所示為梯形條帶排列示意圖，其中bt表示梯形條帶下底邊的長度，ut表示上底邊的長度，ts表示條帶的高，毛坯在條帶中的排列是從斜邊底部開始，依次向直角邊進行排放。

圖3 平行四邊形條帶及梯形條帶

1.1.2 條帶寬度和價值

平行四邊形條帶的寬度是與條帶底邊方向成60°的的長度，即圖3(a)中ps邊長；梯形條帶的寬度是梯形的高，即圖3(b)中ts邊長。記gi(若無說明i取值范圍均為1≤i≤k，k為需求毛坯種數)為第i種毛坯的條帶中允許的最大排數，其中第j(若無說明j取值范圍均為1≤j≤gi)種條帶包含有j排毛坯。

(1) 平行四邊形條帶的價值計算。由圖 2及圖3(a)可得，則平行四邊形條帶寬度：，記vi為第i種毛坯的單個毛坯價值，條帶的價值即是條帶中所有毛坯的價值總和。如圖4所示，pd是平行四邊形條帶能包含至少一個毛坯的條帶長度。當第 i種毛坯的條帶長度為x時，若其中包含有j排毛坯，根據以下步驟計算平行四邊形條帶價值：

圖4 平行四邊形條帶初始長度

由幾何規則可知

條帶中第m排毛坯的個數

若x＜td，條帶中毛坯個數n=0；若x≥td，條帶中毛坯個數，所以梯形條帶價值為tt=nvi。

圖5 梯形條帶初始長度

如圖6所示，兩條與底邊成60°的切割線將板材分為 3個部分，兩個梯形段大小一致，中間部分是平行四邊形段。切割起點距板材寬的距離為y的切割線，且稱之為分隔線y。每個段中的條帶方向都是一致的，梯形段中的條帶都是 X向，平行四邊形段中的條帶是X向或Y向。記排入梯形段中所有毛坯價值總和的最大值為 ZT(bl,W )，其中W 是板材的寬度，bl為梯形段底邊的長度，可由計算得出。記排入平行四邊形段中所有毛坯價值總和的最大值為 ZP(pl,p w)，其中，同時稱相對應的平行四邊形為pl×pw。由幾何規則可知y的取值范圍為。若排入平行四邊形段的條帶方向是 X向，則此時該段的最大價值為Zx(pl,p w)；若排入的條帶方向是y向，此時該段的最大價值為 Zy(pl, pw)，因此平行四邊形段的最大價值。整個板材中毛坯的最大價值 z(y) =2 ZT(bl,W)+ ZP(pl, pw)，若對于所有的y，都有 z(y0)≥ z(y)，則記y0為最優分割線。

圖6 板材切割示意圖

1.2.1 梯形排樣算法

設遞歸函數Rec(bl,W)返回下底長為bl高為W的梯形段的最大價值，其步驟如下：

步驟1. 如果Ft(x,h)≥0，轉向步驟6；否則轉步驟2。

步驟2. 令Ft(x,h)=0，i=1，得到當前梯形條帶當前價值向量TT。

步驟3. 如果 h＜tsi，轉步驟5；否則，令ut= q(x,t si)，令 V =tti+ Rec(ut,h -tsi)。

步驟 4. 如果 V≤Ft(x,h)，轉步驟 5；否則令Ft(x,h)=V。

步驟5. 令i=i+1。如果i≤M，轉步驟3；否則轉步驟6。

步驟6. 返回Ft(x,h)。

1.2.2 平行四邊形排樣算法

在圖6的平行四邊形段pl×pw中，假定條帶方向和pl方向一致，根據1.1可分別計算出平行四邊形中的條帶寬度向量PS和價值向量PT，平行四邊形段的最大價值由以下數學模型求解

其中，ni為正整數，i=1,2,··,M

該模型是一個背包問題，可通過下面的背包函數求得問題的解

同理可求得 Zy(pl,pw) ，令 ZP(pl,p w)= max{Zx(p l,p w),Zy(p l,p w) }。

1.2.3 板材最優排樣方式生成算法

步驟1. 根據板材大小L×W得到ymax及pw的值，初始化PS、TS，令i=0。

步驟2. 根據i得到bl、pl的值，得到PT。

步驟3. 根據1.2.1得到梯形段最大價值ZT(bl,W)。

步驟4. 根據1.2.2得到平行四邊形段最大價值ZP(pl, pw)。

步驟6. 令i=i+1，若 i≤ymax，轉步驟2；否則輸出y0、z0及當前排樣P。

2 下料方案生成算法

2.1 圓片下料問題的線性規劃模型

圓片剪沖下料問題CSPCB可描述為：對庫存板材進行剪沖下料，以滿足k種圓片毛坯的需求，其中第i種毛坯的需求量為bi，i=1,2,··,k。問題求解要求確定一種最優下料方案，使得在滿足所有毛坯需求的前提下，所消耗的板材張數最少。

采用LP方法求解該問題的數學模型為

其中，C為板材的價值向量，C=[c1,c2,··,cn]，n為排樣方案包含排樣方式的個數，若下料時只用到單一規格的矩形板材，則cj=L×W(j=1,2,··,n)，L和W分別為矩形板材的長度和寬度；X=[x1,x2,··,xn]T，xj(j=1,2,··,n)為下料方案中應用每種排樣方式的次數；z為其中一種下料方案所消耗的板材的總價值；B=[b1,b2,··,bk]為毛坯的需求數量的列向量；A 為k行n列的記錄各種排樣方式的矩陣，其元素aij(i=1,2,··,k，j=1,2,··,n)表示第 j種排樣方式中包含第i種毛坯的個數。矩陣中每一個列向量即記錄一種排樣方式中用到的各毛坯的數量。

可用列延遲生成法解上述模型，具體步驟如下：

(1) 確定初始可行解。初始化A為一個單位矩陣，則初始可行解X=B。

(2) 修改毛坯的當前毛坯價值向量 V，V=CA–1。

(3) 求解使目標函數改善的排樣方式。根據1.2.3得到當前排樣方式P。若LW–VP＜0，則引入P改善矩陣A，用引入的P替換A中的第q列，q可根據單純形法求得，并令cq=LW，轉步驟2。若LW–VP≥0，則當前下料方案已是最優，結束循環。

2.2 圓片下料方案的算法實現

針對用線性規劃模型求解CSPCB問題，本文提出以下算法實現解決方案：

Begin

初始化板材大小、毛坯的各參數及初始可行解X；

確定當前毛坯的價值向量V=CA–；

令value=L×W+1；

調用排樣方式生成算法，value=z0；

記錄當前排樣方式P；

根據單純形法確定q，用P替換A中的第q列；

求解X，重置當前毛坯價值向量V=CA-；

將X中的元素向上取整；

End

3 實驗結果

在Mirosoft visual studio 2013平臺上用C#語言編程實現算法，在主頻為2.60 GHz，內存為8 GB的計算機上進行實驗。

3.1 算法對材料利用率的提高

材料利用率 U=(所需毛坯的總面積/消耗板材的總面積)×100%。本文實驗采用文獻[4]的變量取值范圍，如表1所示。隨機生成500個測試樣例與文獻[4]中的 T形排樣算法作比較，本文算法得到的平均材料利用率為70.81%，而文獻[4]中T形排樣算法得到的平均材料利用率為 68.46%。兩者相比，本文算法的平均材料利用率約高出 2個百分點，說明本文算法更有利于提高生產的經濟效益。

表1 參數取值范圍

3.2 參數對材料利用率的影響

本文還對條帶中允許排入毛坯的最大排數對材料利用率的影響進行了研究。參數的取值范圍參照表 1，其中條帶允許最大排數分別取為 1，2，··，6，取為1時表明一根條帶中只能有一行毛坯，取為 2時表明一根條帶中可以包含一行毛坯也可以包含兩行毛坯，以此類推。分別用這些參數各隨機生成 100個測試樣例，其平均材料利用率的結果如表2所示。

由實驗結果可知，增加條帶中允許的毛坯排數可以提高材料利用率，在排數小于等于 3時，材料利用率的提高較為明顯；當排數大于 3時，材料利用率的提高不明顯，因此本文算法建議允許的條帶排數不超過3。

表2 條帶排數對材料利用率的影響(%)

3.3 求解一個真實的下料案例

板材大小為2000×1000，需求毛坯有8種，其直徑大小分別為362，297，102，153，148，352，198，244，需求數量分別為2 672，532，2 775，1 034，1 216，1 786，1 515，2 522，工藝余量為8。程序求解耗時43.23 s，下料方案如圖7所示，總共消耗了483塊板材，一共有8種排樣方式，材料利用率為73.68%。

圖7 下料方案圖例

3.4 算法時間復雜度分析

算法的效率一般用時間復雜度來衡量，時間復雜度可以描述算法執行基本運算的次數。對于CSPCB問題，基本運算可以看成是一個排樣方式的生成。本文用單純形法求解線性規劃問題，最壞情況下的時間復雜度是指數級別的，所以需用排樣方式生成算法的時間復雜度來判斷算法的優劣性。對于算法1.2.1，T(n)=T(n–1)+O(1)=O(n)，則時間復雜度為O(MW)；對于算法1.2.2，背包體積為L，物品種類個數為M，則動態規劃算法解決該問題的時間復雜度為 O(ML)。則排樣方式生成算法1.2.3的時間復雜度為 O(ML2)。在隨機生成的 500個樣例的實驗中，平均每個問題的計算時間是53.526 s。

CSPCB是一個NP難問題，在有限的時間內只能得到一個接近最優的解。本文算法相對于其他算法在時間上沒有顯著的改善，但是在材料利用率上有較大的提高。實際生產中，一個生產計劃的下料方案在計算出來之后就不會改變，本文算法所消耗的時間在可接受的范圍之內。

4 結 論

本文提出在矩形板材上引入梯形條帶排樣方式，可以利用平行四邊形排樣以獲取更高的材料利用率，同時又可以利用在矩形板材上切割平行四邊產生的直角三角形廢料。實現了梯形排樣和平行四邊形排樣的算法，用于求解實際的板材下料問題。實驗計算結果表明，應用平行四邊形條帶和梯形條帶組合排樣的算法比 T形排樣算法獲得更高的材料利用率；實驗結果還證明了毛坯行數在 3~4行時材料利用率提高得較為明顯，最后通過實驗圖給出一個完整的下料解決方案。

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

[2] 崔耀東. 計算機排樣技術及其應用[M]. 北京: 機械工業出版社, 2004: 82.

[3] 楊 劍, 黃少麗, 侯桂玉, 等. 圓片剪沖下料排樣算法[J]. 計算機工程與設計, 2010, 31(23): 5139-5142.

[4] Cui Y D. Generating optimal T-shape cutting patterns for circular blanks [J]. Computers & Operations Research, 2005, 32(1): 143-152.

[5] Cui Y D. Generating optimal multi-segment cutting patterns for circular blanks in the manufacturing of electric motors [J]. European Journal of Operational Research, 2006, 169(1): 30-40.

[6] 陳 菲, 劉 勇, 劉 睿, 等. 基于3塊方式的圓形片剪沖排樣算法[J]. 計算機工程, 2009, 35(14): 195-197.

[7] 王 巖, 潘衛平, 胡 鋼. 生成圓形片最優四塊排樣方式的確定性算法[J]. 機械設計與制造, 2014, (9): 152-155.

[8] 王 峰, 張 軍, 胡 鋼. 圓形片剪沖下料問題的一種求解算法[J]. 鍛壓技術, 2015, 40(10): 39-44.

[9] Cui Y D, Song X X. Applying parallelgrammic strips for cutting circles from stainless steel rolls [J]. Journal of Materials Processing Technology, 2008, 205: 138-145.

[10] Cui Y D, Chen Y Y, Wu J L. Selecting the best sheet length for the steel stock used in circular blank production [J]. Iie Transactions, 2006, 38(10): 829-836.

An Algorithm for Circle Cutting Stock Problem Based on Trapezoid and Parallelogram

Chen Yan1,2, Liu Yong1, Xie Qiqi1, Cui Yaodong1

(1. Department of Computer and Electronic Information, Guangxi University, Nanning Guangxi 530004, China; 2. School of Business Administration, South China University of Technology, Guangzhou Guangdong 510640, China)

A pattern of circular cutting in rectangle sheet is proposed by introducing trapezoidal stripes. Plate with two parallel dividing lines will be divided into three segments when the nesting, two segments of the same size right angle trapezoid and one parallelogram segment. Respectively recursive algorithm and dynamic programming algorithm are used to determine the optimal combination of stripes in trapezoidal section and parallelogram section, so as to determine the optimal pattern. Then combine with linear programming algorithm to solve the problem of the two-dimensional cutting pattern problem, making material utilization maximum. Finally, experiment results of a large number of randomly generated problems show the effectiveness of improving material utilization of the algorithm.

circular cutting pattern; shearing and punching; parallelogram stripes; trapezoidal stripes

TH 164

10.11996/JG.j.2095-302X.2016050661

A

2095-302X(2016)05-0661-07

2016-01-06；定稿日期：2016-03-20

國家自然科學基金項目(61363026，71371058)

陳 燕(1975–)，女，廣西北流人，教授，博士研究生。主要研究方向為高性能計算、算法優化設計與實現、計算機輔助設計等。

E-mail：gxcy@foxmail.com