變尺寸裝箱問題的迭代/貪婪動態規劃算法

姚汝林，尹石軍，郭蘊華

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

0 引言

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

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

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

1 問題描述

令I=(1,2,…,n)和J=(1,2,…,m)分別表示零件管集合和原料管集合，且零件管i和原料管j的長度為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切割后的剩余長度，它可以由下式計算：

(6)

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

2 迭代貪婪/動態規劃算法

為了求解式(1)～式(6)所描述的VSBPP_PS問題，本文提出了一種迭代貪婪/動態規劃算法。該算法首先考慮對SSP問題進行貪婪/動態規劃組合求解，然后對其進行調用實現對整個VSBPP_PS的構造啟發式求解。為了進一步提高求解質量，還采用迭代的“拆箱/再分配”方法實現局部搜索。算法幾個部分的具體描述如下。

2.1 貪婪/動態規劃組合解法

(7)

(8)

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

Step 2 執行貪婪操作：

Ifcj-vi>vminthen

End If

End for

(9)

(10)

(11)

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

2.2 求解VSBPP_PS的構造啟發式方法

基于上述貪婪/動態規劃組合解法，可以對整個VSBPP_PS實現構造啟發式求解，其偽代碼如下：

2.3 拆箱/再分配方法

Rj>Tth

(12)

或者

r

(13)

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

3 實驗結果與分析

3.1 實驗條件

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

8個算例中：零件管數量分別為100、120、140、160、180、200、300和500，原料管數量為零件管數量的50%～60%。零件管長度為100～4 000 mm(對于算例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%)，原料管長度在2 000～6 500 mm之間。為了降低實驗結果對特定算例的敏感性，實驗重復100次，且每一次實驗中的算例隨機生成。

3.2 結果分析

實驗結果見圖1～圖4和表1。其中：圖1和圖2分別給出了8個算例的所有算法的平均剩余長度和平均計算耗時，圖3和圖4分別為算例4和算例8的迭代結果圖，表1給出了所有算法剩余長度的最小值、最大值、平均值和平均計算耗時。

圖1 各算例的平均剩余長度

圖2 各算例的平均計算耗時

圖3 算例4的迭代結果

圖4 算例8的迭代結果

從實驗結果可以看出：

(1)對于所有算例，IGDP得到的平均剩余長度均小于現有算法，且表現十分穩定。此外，隨著零件管數量的增加，IFFD、IMBS/BSH和GGA的優化性能會有所降低，而VNS和IGDP的優化性能受求解規模影響不大。

(2)由圖3和圖4可見，隨著迭代次數的增加，所有算法的性能均有不同程度的提高。IGDP算法在第1代就具有明顯優勢，表明基于貪婪/動態規劃的構造啟發式求解十分有效。并且，隨著拆箱/再分配的迭代次數增加，還能進一步提高求解質量。

表1 實驗結果

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

(4)在GGA、VNS和IGDP這3個算法中，多數算例中GGA的計算耗費最大，但其優化性能最差。對于算例1～4，VNS的計算耗費小于IGDP的計算耗費；而對于算例5～8，IGDP的計算耗費更少。總體而言，IGDP的計算耗費是可以接受的，便于在實際工程中使用。

4 結語

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