基于兩段排樣方式的矩形件優(yōu)化下料算法

扈少華，武書彥，潘立武

?

基于兩段排樣方式的矩形件優(yōu)化下料算法

扈少華，武書彥，潘立武

(河南牧業(yè)經(jīng)濟學(xué)院軟件學(xué)院，河南 鄭州 450011)

針對矩形件下料問題，提出一種基于兩段排樣方式的優(yōu)化下料算法。首先構(gòu)造一種約束排樣算法，生成矩形件在板材上的兩段排樣方式。然后采用列生成算法依據(jù)矩形件剩余需求量迭代調(diào)用上述約束排樣算法生成一個虛擬下料方案，按照不產(chǎn)生多余矩形件原則選取虛擬下料方案中的部分排樣方式加入到實際下料方案中，更新矩形件剩余需求量；重復(fù)上述步驟直到矩形件剩余需求量為零。采用文獻中基準例題將該算法與2種文獻算法進行比較，數(shù)值實驗結(jié)果表明該算法下料利用率比2種文獻算法分別高1.61%和0.78%。

下料問題；兩段排樣方式；列生成算法；約束排樣；矩形件

在機械制造業(yè)的生產(chǎn)過程中經(jīng)常會遇到矩形件下料(rectangular items cutting stock，RCS)問題:用長為、寬為的板材切割出種不同規(guī)格的矩形件，其中第種矩形件的長為l、寬為w、需求量為d，=1,2,···,；優(yōu)化目標為板材使用張數(shù)最少。RCS問題的解是一個下料方案，由多個不同的排樣方式組成，每個排樣方式對應(yīng)單張板材上矩形件的具體排列方式[1]。

針對RCS問題，目前常見的求解方法有整數(shù)規(guī)劃、線性規(guī)劃和順序啟發(fā)式算法。

文獻[2]提出了基于兩階段排樣方式的整數(shù)規(guī)劃模型，研究了RCS問題的線性松弛下界。文獻[3]提出了基于三階段排樣方式的整數(shù)規(guī)劃模型，該模型具有多項式個數(shù)的變量和約束條件；構(gòu)造了該模型的分支定價和集合覆蓋求解算法。文獻[4]通過擴展一維下料問題的數(shù)學(xué)模型構(gòu)造了RCS問題基于兩階段和三階段排樣方式的整數(shù)規(guī)劃模型，其中決策變量對應(yīng)板材各階段的切割線位置。以上文獻方法只能求解規(guī)模較小的RCS問題，對于中大規(guī)模的RCS問題，耗費的計算時間讓人無法忍容。

文獻[5-6]采用線性規(guī)劃方法對RCS問題進行了探討。研究表明，線性規(guī)劃方法的求解速度快于整數(shù)規(guī)劃方法。但線性規(guī)劃方法求得的下料方案解(各個排樣方式的頻數(shù))為小數(shù)，并非RCS問題的實際可行解。文獻中通過對線性規(guī)劃解進行向上取整操作得到RCS問題的實際可行解。但向上取整會增加下料方案的板材使用張數(shù)，浪費板材資源。

順序啟發(fā)式算法通過逐個生成排樣方式來構(gòu)造下料方案，每個排樣方式滿足部分矩形件需求量，當所有矩形件需求量均得到滿足時，算法終止。文獻[7]提出了求解一維下料問題的順序啟發(fā)式算法，該算法能在較短的時間內(nèi)得到近似最優(yōu)解。文獻[8]提出了1.5維下料問題的迭代順序啟發(fā)式算法，其可通過改變參數(shù)得到不同的排樣方式。文獻[9]提出了RCS問題基于價值修正策略的順序啟發(fā)式算法，并通過不斷修正矩形件的價值使排樣方式更趨于合理。文獻[10]提出了一種以排樣方式為導(dǎo)向的啟發(fā)式下料算法，迭代構(gòu)造多個排樣方式，每次選取排樣價值最大的一個排樣方式加入到下料方案中。文獻[11]構(gòu)造了3種啟發(fā)式排樣規(guī)則：首次適應(yīng)插入、最佳適應(yīng)插入和關(guān)鍵適應(yīng)插入，并提出了一種新穎的適應(yīng)度計算公式。

本文針對RCS問題提出一種基于兩段排樣方式的優(yōu)化下料算法，該算法結(jié)合了線性規(guī)劃和順序啟發(fā)式算法思想。首先構(gòu)造兩段排樣方式的約束排樣算法，然后采用線性規(guī)劃法調(diào)用約束排樣算法生成多個虛擬下料方案，按照不產(chǎn)生多余矩形件原則選取各個虛擬下料方案中的部分排樣方式組合形成實際下料方案。數(shù)值實驗結(jié)果表明本文算法能有效的節(jié)約板材資源。

1 兩段排樣方式及其數(shù)學(xué)模型

1.1 兩段排樣方式

用一條平行于板材邊的分割線將板材劃分為兩個段，同一段中排放方向相同的條帶，這種排樣方式稱為兩段排樣方式[12]。兩段排樣方式有4種類型(圖1)，即HXX型、HXY型、VXY型和VYY型。其中HXY型中的“H”表示兩個段是水平排放，“XY”表示第一個段為向段，第二個段為向段。

圖1 兩段排樣方式的類型

圖2中，箭頭所示的分界線將板材分為水平排放的兩個段；圖2(a)左右兩個段中分別包含3條水平條帶；圖2(b)左邊段中包含3條水平條帶，右邊段中包含2條豎直條帶。

圖2 兩段排樣方式例圖

1.2 數(shù)學(xué)模型

約束兩段排樣問題：采用兩段排樣方式將長為、寬為的板材切割出種不同規(guī)格的矩形件，約束每種矩形件允許切割的數(shù)量不大于其需求量，l、w、c、b分別為第種矩形件的長、寬、價值、需求量，其中=1,2,···,；優(yōu)化目標為使得板材切割出的矩形件總價值最大。令排樣方式中包含y個第種矩形件，即

其中，為自然數(shù)集合。

2 兩段排樣方式生成算法

令板材和矩形件的水平邊為長，豎直邊為寬。假設(shè)板材和矩形件的尺寸均為整數(shù)，此假設(shè)不影響本文算法的通用性，因為當板材或矩形件尺寸不為整數(shù)時，可將板材和矩形件尺寸按比例尺放大到整數(shù)。本節(jié)著重研究HXY型兩段排樣方式的生成算法，同理易得其他3種類型的兩段排樣方式的生成算法。

2.1 條帶的價值

對矩形件按照寬度非遞減順序編號，即1≤2≤····≤w。令(,)為水平條帶′w(長：，寬：w)的價值，其中=1,2,···,，=0,1,···,；(,,)為水平條帶′w中包含矩形件的個數(shù)，則有

2.2 段的價值

記(,,)為向段′(長：、寬：)中包含矩形件的個數(shù)，其中(,,0)=0?？赏ㄟ^動態(tài)規(guī)劃遞推可得段的價值(,)，即

其中，(,0)=0；e表示段中排入水平條帶′w所獲得的價值增量。同理可確定向段′的價值。

2.3 排樣方式生成算法

步驟1. 根據(jù)2.1節(jié)內(nèi)容，生成與向段′主排樣相關(guān)的所有水平條帶′w(=0,1,···,；=1,2,···,)和與向段′主排樣相關(guān)的所有豎直條帶l′。

步驟2. 根據(jù)2.2節(jié)內(nèi)容，生成向段′的主排樣，記兩段排樣方式價值=F(,)。

步驟3. 從1到枚舉分割線位置。

步驟3.1. 確定向段′的主排樣。

步驟3.2. 生成與向段(–)′輔排樣相關(guān)的所有豎直條帶，確定向段(–)′的輔排樣。

步驟3.4. 生成與向段′輔排樣相關(guān)的所有水平條帶，確定向段′的輔排樣。

步驟4. 輸出最優(yōu)兩段排樣方式。

3 下料算法

RCS問題的解即下料方案，其由多個不同的排樣方式組成，其中每個排樣方式的頻數(shù)(使用次數(shù))為非負整數(shù)，RCS問題的整數(shù)規(guī)劃數(shù)學(xué)模型為

式(5)的線性松弛形式為

本文下料算法步驟如下[1]：

步驟1. 初始化實際下料方案為空，即不包含任何排樣方式。

步驟2. 初始化剩余下料問題為原始下料問題，即矩形件的剩余需求量為d。

步驟3. 采用基于列生成的線性規(guī)劃算法[15]迭代調(diào)用2.3節(jié)兩段排樣方式生成算法求解當前剩余下料問題的線性松弛式(6)，得到一個虛擬下料方案(由于每種排樣方式的頻數(shù)可能為小數(shù)，因此并不符合實際)。

步驟4. 按照一定規(guī)則選取當前虛擬下料方案中的部分排樣方式加入到實際下料方案中，更新每種矩形件的剩余需求量；若當前所有矩形件的剩余需求量均為0，則轉(zhuǎn)步驟5，否則轉(zhuǎn)步驟3。

步驟5. 輸出實際下料方案。

步驟3~4反復(fù)求解剩余下料問題的線性松弛式直到所有矩形件的需求量均得到滿足。步驟3采用列生成算法迭代調(diào)用第2節(jié)排樣方式生成算法得到虛擬下料方案中的各個排樣方式。

令max為當前虛擬下料方案中排樣方式頻數(shù)的小數(shù)部分的最大值，有0≤max<1，令參數(shù)在區(qū)間[0,1]取值。記為虛擬下料方案中當前正在考察的排樣方式，=[1,2,···,y]，其中y為中包含矩形件的數(shù)量，令為的頻數(shù)。步驟4按照以下規(guī)則選取虛擬下料方案中的排樣方式加入到實際下料方案中：

方案1.對虛擬下料方案中的排樣方式按照其頻數(shù)非遞增順序進行排序。

方案2.按順序逐個考察排樣方式，如果≥max且對任意?{1,2,···,}有y≤d，則將加入到實際下料方案中。

分析可知，方案2每次至少選取了一個排樣方式加入到實際下料方案中，這是因為y≤d對每個排樣方式均滿足且至少存在一個排樣方式其頻數(shù)大于等于max，這保證了下料算法的收斂性。另外可知取值越小，加入到實際下料方案中的排樣方式個數(shù)就越多。

4 數(shù)值實驗計算

用C++語言編程實現(xiàn)本文下料算法，在英特爾奔騰雙核G4400 CPU，主頻3.3 GHz，內(nèi)存4 GB計算機上進行實驗，實驗平臺為Microsoft Visual Studio 2012。采用文獻中基準例題，將本文下料算法與文獻[5]和[6]算法進行比較。

4.1 與文獻[5]算法的比較

用本文下料算法求解文獻[5]的6道例題(ID1-ID6)?？疾?0.65、0.75、0.85、0.95的4種情形。實驗統(tǒng)計結(jié)果見表1，其中、分別為本文下料算法的下料利用率和計算時間。從表1可以看出，本文下料算法的計算時間隨著的增加而增加，下料利用率隨著的增加先增加后減少。這是因為越大，每次加入到實際下料方案的排樣方式越少，矩形件剩余需求量遞減的速度較慢，算法迭代次數(shù)較多；當?shù)娜≈党^某一臨界值后，每次只能加入一個排樣方式到實際下料方案中，算法貪婪性變強，使得下料利用率變低。文獻[5]算法平均下料利用率為97.14%；本文下料算法在=0.85時平均下料利用率最高，比文獻[5]算法高1.61%。本文下料算法的計算時間不超過3 s，計算時間在實際應(yīng)用中比較合理。

表1 實驗統(tǒng)計結(jié)果

4.2 與文獻[6]算法的比較

某電機廠，需要用長為1 000 mm，寬為600 mm的板材切割出10種矩形件，矩形件長寬尺寸在區(qū)間[70 mm,220 mm]分布，需求量在區(qū)間[4000,10000]分布，具體數(shù)據(jù)見文獻[6]中的表3。文獻[6]算法生成的下料方案使用2 285張板材，下料利用率為99.18%；本文算法(取值為0.85)生成下料方案，計算時間為2.67 s，下料方案使用2 267張板材，下料利用率為99.96%；本文算法下料利用率比文獻[6]算法高0.78%。另外本文算法板材下料利用率接近100%，說明該算法在節(jié)省板材資源和提高板材利用率方面是有效的。本文算法在生成下料方案的過程中總共考察了109個排樣方式，平均每個排樣方式耗時0.024 s。圖3為本文算法生成的下料方案，共包含15個排樣方式，其中“圖3(a)方式1：706張”表示按照排樣方式1切割板材706張。

5 結(jié) 論

RCS問題廣泛地存在于機械制造業(yè)的板料成形生產(chǎn)過程中，一個好的優(yōu)化下料算法可減少板材消耗，降低板材切割難度。本文設(shè)計了一種基于動態(tài)規(guī)劃和列生成的順序啟發(fā)式下料算法。首先采用動態(tài)規(guī)劃算法生成對矩形件數(shù)量有約束的兩段排樣方式，然后采用列生成算法迭代調(diào)用動態(tài)規(guī)劃算法依次生成多個虛擬下料方案，按照不產(chǎn)生多余矩形件原則在各個虛擬下料方案中選取若干排樣方式構(gòu)成實際下料方案。數(shù)值實驗結(jié)果表明，本文下料算法可有效地節(jié)省板材資源，且計算時間能滿足實際應(yīng)用需要。

[1] 胡鋼, 楊瑞, 潘立武. 基于價值修正的圓片下料順序啟發(fā)式算法[J]. 圖學(xué)學(xué)報, 2016, 37(3): 337-341.

[2] LODI A, MARTELLO S, VIGO D. Models and bounds for two-dimensional level packing problems [J]. Journal of Combinatorial Optimization, 2004, 8(3): 363-379.

[3] PUCHINGER J, RAIDL G R. Models and algorithms for three-stage two-dimensional bin packing [J]. European Journal of Operational Research, 2007, 183(3): 1304-1327.

[4] SILVA E, ALVELOS F, DE CARVALHO J M V. An integer programming model for two-and three-stage two-dimensional cutting stock problems [J]. European Journal of Operational Research, 2010, 205(3): 699-708.

[5] CUI Y. Generating optimal T-shape cutting patterns for rectangular blanks [J]. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 2004, 218(8): 857-866.

[6] 易向陽, 仝青山, 潘衛(wèi)平. 矩形件二維下料問題的一種求解方法[J]. 鍛壓技術(shù), 2015, 40(6): 150-154.

[7] HAESSLER R W. A heuristic programming solution to a nonlinear cutting stock problem [J]. Management Science, 1971, 17(12): B793-B802.

[8] SONG X, CHU C B, NIE Y Y, et al. An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem [J]. European Journal of Operational Research, 2006, 175(3): 1870-1889.

[9] 黃少麗, 楊劍, 侯桂玉,等. 解決二維下料問題的順序啟發(fā)式算法[J]. 計算機工程與應(yīng)用, 2011, 47(13): 234-237.

[10] CHARAMBOUS C, FLESZAR K. A constructive bin-oriented heuristic for the two-dimensional bin packing problem with guillotine cuts [J]. Computers & Operations Research, 2011, 38(10): 1443-1451.

[11] FLESZAR K. Three insertion heuristics and a justification improvement heuristic for two-dimensional bin packing with guillotine cuts [J]. Computers & Operations Research, 2013, 40(1): 463-474.

[12] 潘衛(wèi)平, 陳秋蓮, 崔耀東. 考慮切割刀數(shù)的最優(yōu)兩段排樣算法研究[J]. 廣西大學(xué)學(xué)報: 自然科學(xué)版, 2014, 39(3): 687-692.

[13] KELLERER H, PFERSCHY U, PISINGER D. Knapsack problems [M]. Berlin: Springer, 2004: 56-79.

[14] CUI Y, HUANG B. A heuristic for constrained T-shape cutting patterns of circular items [J]. Engineering Optimization, 2011, 43(8): 867-877.

[15] 車念, 張軍, 潘立武. 沖裁條帶剪切下料問題的一種求解算法[J]. 機械設(shè)計與制造, 2016(2): 37-40.

An Optimization Algorithm for Rectangular Items Cutting Stock Problem Based on Two-Segment Patterns

HU Shaohua, WU Shuyan, PAN Liwu

(Software College, Henan University of Animal Husbandry & Economy, Zhengzhou Henan 450011, China)

For on the rectangular items cutting stock problem, an optimization algorithm based on two-segment patterns is proposed. Firstly, a constrained packing algorithm is constructed to generate the two-segment patterns of rectangular items on the plate. Then, column generation algorithm is used to generate a virtual cutting plan according to the current remaining demand of rectangular items, several patterns are added into actual cutting plan according to the rule that no redundant rectangular item is generated, and the current remaining demand of rectangular items is updated. The above steps are repeated until the remaining demand of rectangular items is zero. Compared the proposed algorithm with two algorithms in the literature through benchmark instances, results of numerical experiments show that material utilization of the proposed algorithm is higher than two literature algorithms about 1.61% and 0.78%, respectively.

cutting stock problem; two-segment patterns; column generation algorithm; constrained packing; rectangular items

TP 391

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

A

2095-302X(2018)01-0091-06

2017-06-08；

2017-06-28

河南省科技廳科技攻關(guān)項目(152102210320)；河南省高等學(xué)校重點科研項目(15B52000)

扈少華(1978–)，男，河南鄭州人，講師，碩士。主要研究方向為CAD、智能制造。E-mail：hshhnmy@163.com