姚汝林，尹石軍，郭蘊(yùn)華

(1.上海交通大學(xué) 船舶海洋與建筑工程學(xué)院，上海 200240; 2.招商局重工(江蘇)有限公司，江蘇 海門 226116；3.武漢理工大學(xué) 能源與動(dòng)力工程學(xué)院，湖北 武漢 430063)

0 引言

管材切割是船舶建造過程中的一個(gè)重要的生產(chǎn)步驟，新近研究將船廠管材切割問題描述為一維下料問題(One-dimensional cutting stock problem，1D-CSP)[1]。但是，由于船舶建造的復(fù)雜性，某些場(chǎng)合零件管和原料管都具有隨機(jī)長(zhǎng)度。在此情況下，應(yīng)將船舶建造的管材切割問題描述為變尺寸裝箱問題(Variable-sized bin packing problem，VSBPP)，而非1D-CSP[2]。對(duì)于VSBPP問題，研究人員先后提出了近似算法[3]、分支定界算法[4]、分組遺傳算法(Grouped genetic algorithm, GGA)[5]、迭代遞減首次適合算法(Iterative first-fit decreasing, IFFD)[6]、迭代MBS啟發(fā)式算法(Iterative minimal bin slack, IMBS)[7]、可變鄰域搜索(Variable neighborhood search,VNS)方法[8]和基于動(dòng)態(tài)規(guī)劃的啟發(fā)式方法[9]進(jìn)行求解。

上述方法在優(yōu)化計(jì)算花費(fèi)和剩余長(zhǎng)度等方面都取得了一些進(jìn)展。但是，船舶建造的管材切割化問題是VSBPP的特殊變體，其VSBPP問題(VSBPP of pipe-cutting in ship-building，VSBPP_PS)與經(jīng)典VSBPP有所不同。第一，上述大多數(shù)算法都假定箱子的長(zhǎng)度類型是有限的，而每種類型的供應(yīng)都是無限的。這些假設(shè)與船舶建造中的一些管材切割實(shí)例恰好相反。在船舶建造的實(shí)際生產(chǎn)情況中，經(jīng)常遇到的情形是箱子(原料管)和物品(零件管)的長(zhǎng)度是隨機(jī)的。第二，很多文獻(xiàn)都涉及基于動(dòng)態(tài)規(guī)劃來解決背包問題的方法。動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度為O(l·n)[10]，其中：l為箱子的長(zhǎng)度，n為物品數(shù)。然而造船廠的切割精度為“mm”，即使對(duì)于6 m的原料管，l也等于6 000 mm。對(duì)于動(dòng)態(tài)規(guī)劃而言，船廠的大多數(shù)原料管都是“超長(zhǎng)”的。更為不利的是每根原料管的長(zhǎng)度都不同，需要對(duì)所有原料管執(zhí)行動(dòng)態(tài)規(guī)劃進(jìn)行試算。由此可見，如果將純動(dòng)態(tài)規(guī)劃的方法直接用于求解船廠的管材切割問題，其計(jì)算成本是難以忍受的。

針對(duì)上述船舶建造中VSBPP_PS問題在實(shí)際應(yīng)用方面的困難，本文提出一種迭代貪婪/動(dòng)態(tài)規(guī)劃算法(Iterative greedy/dynamic programming，IGDP)對(duì)其求解。通過貪婪/動(dòng)態(tài)規(guī)劃組合解法求解子集和問題(Subset sum problem，SSP)，并應(yīng)用這一方法實(shí)現(xiàn)對(duì)整個(gè)VSBPP_PS問題的構(gòu)造啟發(fā)式求解。為了進(jìn)一步提高求解質(zhì)量，采用迭代的“拆箱/再分配”方法實(shí)現(xiàn)局部搜索。

1 問題描述

令I(lǐng)=(1,2,…,n)和J=(1,2,…,m)分別表示零件管集合和原料管集合，且零件管i和原料管j的長(zhǎng)度為vi和lj。定義決策變量y=(y1,y2,…,ym)，?j∈J，若原料管j被選中則yj=1，否則yj=0。定義決策變量xij，?i∈I，?j∈J，若零件管i從原料管j上切割，則xij=1，否則xij=0。于是，VSBPP_PS可以描述為

(1)

s.t.Rj≥0

(2)

(3)

xij∈{0,1},?i∈I,?j∈J

(4)

yj∈{0,1},?j∈J

(5)

式中的Rj為原料管j切割后的剩余長(zhǎng)度，它可以由下式計(jì)算：

(6)

目標(biāo)函數(shù)式(1)的含義為最小化所有被選原料管的總剩余長(zhǎng)度；約束條件式(2)確保所有被選中原料管在切割后的余長(zhǎng)≥0；約束條件式(3)確保每一個(gè)零件管只能從一根原料管上切割；約束式(4)～式(5)表明所有決策變量必須是0或者1。

2 迭代貪婪/動(dòng)態(tài)規(guī)劃算法

為了求解式(1)～式(6)所描述的VSBPP_PS問題，本文提出了一種迭代貪婪/動(dòng)態(tài)規(guī)劃算法。該算法首先考慮對(duì)SSP問題進(jìn)行貪婪/動(dòng)態(tài)規(guī)劃組合求解，然后對(duì)其進(jìn)行調(diào)用實(shí)現(xiàn)對(duì)整個(gè)VSBPP_PS的構(gòu)造啟發(fā)式求解。為了進(jìn)一步提高求解質(zhì)量，還采用迭代的“拆箱/再分配”方法實(shí)現(xiàn)局部搜索。算法幾個(gè)部分的具體描述如下。

2.1 貪婪/動(dòng)態(tài)規(guī)劃組合解法

(7)

(8)

式(7)～式(8)所描述的SSP問題可以通過動(dòng)態(tài)規(guī)劃求得最優(yōu)解[10]。但造船廠的切割精度是“mm”，因此lj是一個(gè)很大的數(shù)。對(duì)于原料管j，經(jīng)典動(dòng)態(tài)規(guī)劃具有時(shí)間復(fù)雜度O(lj·n)。就船廠的實(shí)際應(yīng)用而言，其計(jì)算成本太大。為此，本文提出了貪婪/動(dòng)態(tài)規(guī)劃組合解法。

Step 2 執(zhí)行貪婪操作：

Ifcj-vi>vminthen

End If

End for

(9)

(10)

(11)

xij∈{0,1},?i∈I,?j∈J

2.2 求解VSBPP_PS的構(gòu)造啟發(fā)式方法

基于上述貪婪/動(dòng)態(tài)規(guī)劃組合解法，可以對(duì)整個(gè)VSBPP_PS實(shí)現(xiàn)構(gòu)造啟發(fā)式求解，其偽代碼如下：

2.3 拆箱/再分配方法

Rj>Tth

(12)

或者

r

(13)

在對(duì)當(dāng)前解中部分原料管進(jìn)行拆箱操作之后，執(zhí)行2.2中的Step2～Step5完成再分配。若再分配后得到結(jié)果好于當(dāng)前解則取而代之，否則保留當(dāng)前解。拆箱/再分配可以反復(fù)迭代多次，以提高局部搜索的性能。

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

3.1 實(shí)驗(yàn)條件

通過對(duì)某在建船舶的實(shí)際切管訂單的總結(jié)歸納，設(shè)計(jì)了8個(gè)算例對(duì)所提IGDP算法進(jìn)行了驗(yàn)證，并將其與IFFD[6]、IMBS/BSH[7]、GGA[5]和VNS[8]等現(xiàn)有算法進(jìn)行了對(duì)比分析。現(xiàn)有算法的迭代次數(shù)統(tǒng)一設(shè)置為30。GGA的種群規(guī)模設(shè)置為100。IGDP中，Tth=5 mm，Pa=0.05，拆箱/再分配的次數(shù)為30。所有算法都用C++編程實(shí)現(xiàn)。實(shí)驗(yàn)在Intel i7-6 500U 2.5 GHz筆記本計(jì)算機(jī)上進(jìn)行。

8個(gè)算例中：零件管數(shù)量分別為100、120、140、160、180、200、300和500，原料管數(shù)量為零件管數(shù)量的50%～60%。零件管長(zhǎng)度為100～4 000 mm(對(duì)于算例1～4，其中：100～500 mm占15%，500～3 000 mm占70%，3 000～4 000 mm占15%；算例5～8中：100～500 mm占20%，500～3 000 mm占60%，3 000～4 000 mm占20%)，原料管長(zhǎng)度在2 000～6 500 mm之間。為了降低實(shí)驗(yàn)結(jié)果對(duì)特定算例的敏感性，實(shí)驗(yàn)重復(fù)100次，且每一次實(shí)驗(yàn)中的算例隨機(jī)生成。

3.2 結(jié)果分析

實(shí)驗(yàn)結(jié)果見圖1～圖4和表1。其中：圖1和圖2分別給出了8個(gè)算例的所有算法的平均剩余長(zhǎng)度和平均計(jì)算耗時(shí)，圖3和圖4分別為算例4和算例8的迭代結(jié)果圖，表1給出了所有算法剩余長(zhǎng)度的最小值、最大值、平均值和平均計(jì)算耗時(shí)。

圖1 各算例的平均剩余長(zhǎng)度

圖2 各算例的平均計(jì)算耗時(shí)

圖3 算例4的迭代結(jié)果

圖4 算例8的迭代結(jié)果

從實(shí)驗(yàn)結(jié)果可以看出：

(1)對(duì)于所有算例，IGDP得到的平均剩余長(zhǎng)度均小于現(xiàn)有算法，且表現(xiàn)十分穩(wěn)定。此外，隨著零件管數(shù)量的增加，IFFD、IMBS/BSH和GGA的優(yōu)化性能會(huì)有所降低，而VNS和IGDP的優(yōu)化性能受求解規(guī)模影響不大。

(2)由圖3和圖4可見，隨著迭代次數(shù)的增加，所有算法的性能均有不同程度的提高。IGDP算法在第1代就具有明顯優(yōu)勢(shì)，表明基于貪婪/動(dòng)態(tài)規(guī)劃的構(gòu)造啟發(fā)式求解十分有效。并且，隨著拆箱/再分配的迭代次數(shù)增加，還能進(jìn)一步提高求解質(zhì)量。

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

(3)盡管IFFD和IMBS/BSH的計(jì)算成本極低，但與其他3種算法相比，它們只能提供勉強(qiáng)滿意的性能。前者可以在1 ms內(nèi)求解任何算例，而后者可以相對(duì)較大的計(jì)算耗費(fèi)獲得稍好的結(jié)果。

(4)在GGA、VNS和IGDP這3個(gè)算法中，多數(shù)算例中GGA的計(jì)算耗費(fèi)最大，但其優(yōu)化性能最差。對(duì)于算例1～4，VNS的計(jì)算耗費(fèi)小于IGDP的計(jì)算耗費(fèi)；而對(duì)于算例5～8，IGDP的計(jì)算耗費(fèi)更少?？傮w而言，IGDP的計(jì)算耗費(fèi)是可以接受的，便于在實(shí)際工程中使用。

4 結(jié)語

船舶建造的管材切割化問題是VSBPP的特殊變體。考慮到大多數(shù)零件管和原料管具有隨機(jī)長(zhǎng)度，本文提出了IGDP算法。首先，基于貪婪操作和動(dòng)態(tài)規(guī)劃，實(shí)現(xiàn)了對(duì)整個(gè)問題的構(gòu)造啟發(fā)式求解。其次，通過迭代的“拆箱/再分配”操作，改善了算法的局部搜索能力。通過若干計(jì)算實(shí)例的比較實(shí)驗(yàn)，本文提供了充分的證據(jù)，證明所提算法優(yōu)于現(xiàn)有多數(shù)算法，并且具有可接受的計(jì)算耗費(fèi)。后續(xù)工作將推廣本文算法到求解船舶建造中的板材套料、堆場(chǎng)管理等2D-VSBPP或者3D-VSBPP問題，以進(jìn)一步降低造船成本。