賈春玉，樸惠淑，溫 良

(1. 廣東培正學院 管理學院, 廣州510830 2. 大連海事大學 交通運輸工程學院， 遼寧 大連116026) 3. 長春大學 管理學院，長春 130022)

一、主要問題

圓柱形貨物平面擺放方式有對齊擺放方式、緊湊壓縫擺放方式和松散擺放方式等形式。三維分層裝箱(擺放)也有對齊擺放方式、緊湊壓縫擺放方式和松散擺放方式等形式。組合擺放比條塊狀貨物擺放得多且復雜，因此圓柱形貨物三維裝箱問題是比條塊狀貨物裝箱問題更為復雜的難題。貨物裝箱下料問題的研究成果眾多[1-2]，但針對圓柱形貨物裝箱問題的研究成果非常少，而針對圓柱形貨物三維裝箱問題的研究成果就更少，幾乎查不到相關的文獻，能查到的相關文獻多數(shù)為圓形貨物二維下料問題[3-4]，且多數(shù)為遞歸智能解法。雖然裝箱與下料問題互為反問題，有些方法可以互用，但還是有明顯區(qū)別的，其主要區(qū)別是下料問題具有最大毛坯排數(shù)限制、切割寬度損耗等，在許多情況下不能直接互用，因此有必要研究圓柱形貨物裝箱問題。傳統(tǒng)的方法是人們憑經驗裝箱或下料，存在優(yōu)化程度低、成本高等弊端。為了解決這些問題，學者們提出了多種解法，如動態(tài)規(guī)劃算法[5-6]、啟發(fā)式遞歸解法[7-8]等。這些方法雖然可以解決這類問題，但通常需要建立較為復雜的數(shù)學模型和編制求解軟件進行求解，不易掌握。為了更好地解決這一問題，本文提出新的線性規(guī)劃解法，該方法簡單、易于掌握、優(yōu)化程度高。因為緊湊壓縫擺放方式優(yōu)化程度通常較高、貨垛穩(wěn)定、擺放規(guī)律性強、擺放效率高，所以這里只針對這種擺放方式提出新的簡便解法。

(一)豎立擺放時三維裝箱解法

貨物有時要求必須豎立擺放，尤其是圓柱形容器裝滿貨物時更是如此。在這種情況下，三維裝箱相對比擺放無約束時簡單，只需按要求優(yōu)化求解出按貨箱高度方向豎立擺放一層的優(yōu)化數(shù)量，再乘以貨箱按高度方向能擺放的層數(shù)即可。因此，首先是求解出平面二維優(yōu)化擺放數(shù)量，然后計算出能擺幾層，最后根據兩者乘積得出總的擺放數(shù)量。

單一圓柱形貨物平面放的三種擺放方式在一定條件下均可能是最佳擺放方式。在擺放方式的組合上，可以是單一一種擺放方式，也可以是兩種或兩種以上擺放方式的組合，垛高方向可以是與貨箱長度方向相同，也可以是與貨箱寬尺寸方向相同，擇優(yōu)作為最終優(yōu)化方案，獲得平面擺放近似最優(yōu)解，據此獲得三維擺放近似最優(yōu)解。

(二)擺放無約束時三維裝箱解法求解思路

總體求解思路是分別按貨箱長J1、寬J2和高J3三個維度優(yōu)化擺放，將三個維度優(yōu)化方案擇優(yōu)為最終優(yōu)化方案，獲得滿意近似最優(yōu)解。每個維度優(yōu)化時可分為兩個階段，以最終按貨箱高度優(yōu)化為例，求解過程分為兩個階段：第一階段是求出按貨物直徑和高度尺寸每擺一層的優(yōu)化擺放數(shù)量；第二階段是按貨箱高尺寸三維優(yōu)化求解。第一階段的求解步驟為：計算貨物兩個維度的尺寸(直徑和高度)每層擺放數(shù)量，即在貨箱長和寬的二維平面內，先計算按貨物直徑尺寸擺放一層的優(yōu)化擺放數(shù)量，此時的貨物可用尺寸是直徑和高度，暫時把貨物直徑尺寸視為矩形貨物的長(H1)，貨物高度尺寸視為貨物的寬(H2)，貨箱可用尺寸是貨箱的長和寬，選用一種或幾種優(yōu)化擺放方式進行優(yōu)化求解，擇優(yōu)得出按貨物直徑尺寸擺放一層的數(shù)量；再計算按貨物高度(如桶高)擺放一層的優(yōu)化擺放數(shù)量，此時的貨物可用尺寸是直徑，貨箱可用尺寸是貨箱的長和寬，選用一種或幾種優(yōu)化擺放方式進行優(yōu)化求解，擇優(yōu)得出一層貨物高的擺放數(shù)量。第二階段的求解步驟為：按貨物直徑擺放一層和按貨物高度擺放一層的優(yōu)化擺放數(shù)量，再按貨箱高度進行三維立體優(yōu)化擺放，優(yōu)化求解各擺多少層，使總的擺放數(shù)量最多，得出近似最優(yōu)解。其他兩個維度(按貨箱的長和寬)優(yōu)化類似，三個維度優(yōu)化結果擇優(yōu)作為最終優(yōu)化結果。

(三)求解過程

以按貨箱高度三維立體優(yōu)化為例，詳細介紹求解過程。其他兩個維度優(yōu)化與高度優(yōu)化類似，所以只作概略介紹，只介紹第二階段求解的數(shù)學模型。

1.按貨箱高度三維優(yōu)化求解過程

(1)第一階段求解過程及數(shù)學模型。擺放方式有單一緊湊擺放方式、組合緊湊擺放方式、單一松散擺放方式和組合松散擺放方式；優(yōu)化方法有數(shù)量優(yōu)化方法[9]、邊長優(yōu)化方法[9]、5塊法[10]、線性規(guī)劃解法和非線性規(guī)劃解法等。這里只介紹最簡單、擺放效率最高的單一緊湊擺放方式，雖然該方法優(yōu)化程度略低，但簡單、實用、裝箱效率高。

首先，按貨箱長二維優(yōu)化時規(guī)劃求解數(shù)學模型。

單一緊湊擺放方式是指貨物在平面內只有一種擺放方式，如壓縫擺放方式1(按貨箱長J1優(yōu)化擺放，即垛高為貨箱長J1方向)；壓縫擺放方式2(按貨箱寬J2優(yōu)化擺放，即垛高為貨箱寬J2方向)，列出優(yōu)化數(shù)學模型求解，兩種擺放方式優(yōu)化程度擇優(yōu)作為優(yōu)化結果。

模型1：按貨箱長二維優(yōu)化時按貨物直徑尺寸擺一層的數(shù)學模型

設貨物“長”為(直徑)H1=2R，“寬”(貨物高)為H2；貨物“長”對貨箱長擺放個數(shù)為N11，對貨箱寬擺放個數(shù)為N12；貨物“寬”對貨箱長擺放個數(shù)為N21，對貨箱寬擺放個數(shù)為N22。X11為貨物“長”擺放的列數(shù)(按貨箱長方向擺放個數(shù))，X21為貨物“寬”擺放的列數(shù)(按貨箱長度方向擺放個數(shù))，總的擺放數(shù)量為ZQ1。為了簡化問題，暫不考慮剩余空間可擺放數(shù)量(計算例題中考慮了)，則數(shù)學模型如下[9]。

目標函數(shù)：MaxZQ1=X11×N22+X21×N12

約束條件:X11×H1+X21×H2≤J1

X11、X21為正整數(shù)。

在符號Nij中，i代表貨物維度，1代表貨物的“長”，2代表貨物的“寬”; j代表貨箱維度，1代表貨箱長，2代表貨箱寬。則有如下計算公式：

Nij=[Jj/Hi]1

符號“[ ]1”代表向下取整。

例如:N12= [J2/H1]1，代表貨物“長”在貨箱“寬”方向上最多可擺放的個數(shù)。

模型2：按貨箱長二維優(yōu)化時按貨物高擺一層的數(shù)學模型

圓柱形貨物半徑R，對齊擺放一層高度為2R(參見圖1，參見圖2和圖3，帶方格線部分)、壓縫單數(shù)和雙數(shù)層一層高度為H(參見圖2和圖3，帶底色為壓縫單數(shù)層，無底色、無方格線為雙數(shù)層)，對齊擺放、壓縫單數(shù)擺放和壓縫雙數(shù)擺放層對應3個變量。設按貨箱長度J1優(yōu)化時(壓縫擺放方式1)圓柱形貨物對齊擺放、壓縫單數(shù)層、壓縫雙數(shù)層3個變量分別為X11、X21、X31, 按貨箱寬尺寸方向貨物對齊、壓縫單數(shù)層、壓縫雙數(shù)層每層擺放個數(shù)(已知數(shù))分別為N11、N21、N31, 總的擺放數(shù)量為GQ1，則數(shù)學模型如下。

圖1 上下對齊擺放方式

圖2 壓縫擺放方式1

圖 3 壓縫擺放方式2

目標函數(shù)：MaxGQ1=X11×N11+X21×N21+X31×N31

S．T．X11×2R+X21×H+X31×H≤J1

X21≥X31

X21-X31≤1

X11≥1

變量為非負整數(shù)。

其中，H=30.5R，N11= N31=[J2/2R]1,N21=[(J2-R)/2R]1; 變量Xij和Nij中的下角標i代表第i個變量(i=1，2，3)，1、2、3分別代表對齊、壓縫單數(shù)、壓縫雙數(shù)層；j代表貨箱維度(j=1，2)，1和2分別代表按貨箱長度J1和寬度J2優(yōu)化時的對應變量或擺放個數(shù)。以下類似符號代表意義相同。

其次，按貨箱寬二維優(yōu)化時規(guī)劃求解數(shù)學模型。

模型1：按貨箱寬二維優(yōu)化時按貨物直徑擺一層的數(shù)學模型

設X12為貨物“長”擺放的列數(shù)(按貨箱寬尺寸方向擺放個數(shù))，X22為貨物“寬”擺放的列數(shù)(按貨箱寬尺寸方向擺放個數(shù))，總的擺放數(shù)量為ZQ2。為了簡化問題，暫不考慮剩余空間可擺放數(shù)量(計算例題中考慮了)，則數(shù)學模型如下[9]。

目標函數(shù)：MaxZQ2=X12×N21+X22×N11

約束條件:X12×H1+X22×H2≤J2

X12、X22為正整數(shù)。

模型2：按貨箱寬二維優(yōu)化時按貨物高擺一層的數(shù)學模型

設按貨箱寬J2優(yōu)化時(壓縫擺放方式2), 圓柱形貨物對齊擺放、壓縫單數(shù)層個數(shù)、壓縫雙數(shù)層個數(shù)3個變量分別為X12、X22、X32，按貨箱長度方向貨物對齊、壓縫單數(shù)層、壓縫雙數(shù)層每層擺放個數(shù)(已知數(shù))分別為N12、N22、N32，總的擺放數(shù)量為GQ2，則數(shù)學模型如下。

目標函數(shù)：MaxGQ2=X12×N12+X22×N22+X32×N32

S．T．X12×2R+X22×H+X32×H≤J2

X22≥X32

X22-X32≤1

X12≥1

變量為非負整數(shù)。

其中，H=30.5R，N12= N32=[J1/2R]1、N22=[ (J1-R)/2R]1，符號“[ ]1”為向下取整。

最后，最終二維優(yōu)化結果。

按貨物高擺一層最終優(yōu)化結果(GQ3)：

GQ3=Max(GQ1，GQ2)

按貨物直徑擺一層最終優(yōu)化結果(ZQ3)：

ZQ3=Max(ZQ1，ZQ2)

(2)第二階段求解過程及數(shù)學模型。設按貨箱高尺寸三維優(yōu)化時貨物直徑尺寸擺X1層，貨物高尺寸擺X2層，優(yōu)化擺放數(shù)量為Q3，則按貨箱高尺寸三維優(yōu)化時數(shù)學模型如下[9]。

目標函數(shù)：MaxQ3=X1×ZQ3+X2×GQ3

約束條件:X1×H1+X2×H2≤J3

H1=2R

X1、X2為正整數(shù)。

2.按貨箱寬尺寸優(yōu)化求解過程

按貨箱寬尺寸優(yōu)化求解過程與按貨箱高尺寸優(yōu)化求解過程類似，只需把平面二維優(yōu)化時的貨箱尺寸換成貨箱長和高的尺寸，再按貨箱寬尺寸進行三維優(yōu)化，優(yōu)化結果為Q2，設ZQ2和GQ2分別為按貨箱寬尺寸三維優(yōu)化時按貨物直徑和高度尺寸平面優(yōu)化擺放數(shù)量。為了節(jié)省篇幅，第一階段求解過程及數(shù)學模型從略，設按貨箱寬尺寸三維優(yōu)化時貨物直徑尺寸擺X1層、貨物高尺寸擺X2層，則按貨箱寬尺寸三維優(yōu)化時的數(shù)學模型如下[9]。

目標函數(shù)：MaxQ2=X1×ZQ2+X2×GQ2

約束條件:X1×H1+X2×H2≤J2

H1=2R

X1、X2為正整數(shù)。

3.按貨箱長尺寸優(yōu)化求解過程

按貨箱長尺寸優(yōu)化求解過程與按貨箱高尺寸優(yōu)化求解過程類似，只需把平面二維優(yōu)化時的貨箱尺寸換成貨箱寬和高的尺寸，再按貨箱長尺寸進行三維優(yōu)化，優(yōu)化結果為Q1，設ZQ1和GQ1分別為按貨箱長三維優(yōu)化時按貨物直徑和高度尺寸平面優(yōu)化擺放數(shù)量。為了節(jié)省篇幅，第一階段求解過程及數(shù)學模型從略，設按貨箱長尺寸三維優(yōu)化時貨物直徑尺寸擺X1層，貨物高尺寸擺X2層，則按貨箱長尺寸三維優(yōu)化時的數(shù)學模型如下[9]。

目標函數(shù)：MaxQ1=X1×ZQ1+X2×GQ1

約束條件:X1×H1+X2×H2≤J1

H1=2R

X1、X2為正整數(shù)。

4.最終三維優(yōu)化結果

取按貨箱三維優(yōu)化結果最好的作為最終優(yōu)化結果ZQ。

ZQ=Max(Q1，Q2，Q3)

最優(yōu)解下限LQ=[(J1×J2×J3)/(3.14159×R2×H2)]1

優(yōu)化程度=(ZQ/LQ) ×100%

二、求解實例

實例1: 貨箱長(J1)1200cm，寬(J2)234cm，高(J3)269cm,貨物為半徑(R)21cm的圓柱形，圓柱高(H2)31cm，問圓柱形貨物擺放無約束情況下最多能擺多少貨物？

解：最優(yōu)解下限LQ=[(1200×234×269)/(3.14159×212×31)]1=1758, 經計算得知，在三維立體優(yōu)化中按貨箱寬尺寸三維優(yōu)化最好，所以二維優(yōu)化時只用到貨箱長和高的尺寸。在貨箱長和高的二維優(yōu)化中，用數(shù)量優(yōu)化方法按貨物直徑尺寸擺放一層時按貨箱高尺寸優(yōu)化擺放最多，按貨物直徑每一列可擺38個，優(yōu)化擺4列；按貨物高尺寸每一列可擺28個，優(yōu)化擺3列，兩種擺放方式優(yōu)化組合一共擺236個。按貨物高尺寸擺放一層時，按貨箱高尺寸優(yōu)化擺放最多，在二維擺放中對齊層每層擺放28個，優(yōu)化擺放2層；單數(shù)層每層擺放28個，優(yōu)化擺放3層；雙數(shù)層每層擺放28個，優(yōu)化擺放2層，按貨物高尺寸擺一層時優(yōu)化組合共可擺196個。

在三維立體優(yōu)化中，按貨箱寬尺寸優(yōu)化，按圓柱直徑尺寸每層可擺236個，優(yōu)化擺1層；按圓柱高尺寸每層可擺196個，優(yōu)化擺6層：兩種方式共可擺1412個，優(yōu)化程度為80.32%。而用其他優(yōu)化方法(如5塊法[10])，在二維平面優(yōu)化中按貨物直徑尺寸擺放一層時，按貨箱高尺寸優(yōu)化擺放最多，可擺239個，比簡便解法多3個；按貨物高尺寸擺放數(shù)量一樣，三維立體優(yōu)化也是按貨箱寬尺寸優(yōu)化最好，可擺1415個，優(yōu)化程度為80.49%，僅多0.17%，差別不大。

實例2: 貨箱長(J1)960cm，寬(J2)234cm，高(J3)242cm,貨物為半徑(R)16cm的圓柱形，圓柱高(H2)40cm，問圓柱形貨物擺放無約束情況下最多能擺多少貨物？

解：最優(yōu)解下限LQ=[(960×234×242)/(3.14159×162×40)]1=1689, 經計算得知，在三維立體優(yōu)化中按貨箱高尺寸三維優(yōu)化最好，所以二維平面優(yōu)化中只用到貨箱長和寬的尺寸。二維優(yōu)化時，用數(shù)量優(yōu)化方法按貨物直徑尺寸擺放一層時按貨箱寬尺寸優(yōu)化擺放最多，按貨物直徑每一列可擺24個，優(yōu)化擺6列；按貨物高度尺寸每一列可擺30個，優(yōu)化擺1列：兩種方式優(yōu)化組合共擺174個。按貨物高尺寸擺放一層時，按貨箱寬尺寸優(yōu)化擺放最多，在二維擺放中對齊層每層擺放30個，優(yōu)化擺放2層；單數(shù)層每層擺放29個，優(yōu)化擺放3層；雙數(shù)層每層擺放30個，優(yōu)化擺放3層，按貨物高尺寸擺一層時優(yōu)化組合共可擺237個。

在三維立體優(yōu)化中，按貨箱高尺寸三維優(yōu)化，按圓柱直徑尺寸每層可擺174個，優(yōu)化擺0層；按圓柱高尺寸每層可擺237個，優(yōu)化擺6層：兩種方式優(yōu)化組合共可擺1422個，優(yōu)化程度為84.19%。而用其他優(yōu)化方法(如5塊法[10])，也是按貨箱高尺寸優(yōu)化最好，可擺1422個，優(yōu)化程度為84.19%，結果一樣。

三、結論

根據圓柱形貨物的特點及緊湊壓縫擺放方式優(yōu)化程度高、貨垛穩(wěn)定、擺放規(guī)律性強、擺放效率高等特點，為了克服現(xiàn)有圓柱形貨物二維裝箱問題解法相對復雜、不易掌握、三維立體裝箱缺乏有效解法困境，提出新的簡便線性規(guī)劃解法。經比較，雖然優(yōu)化程度有時比非線性規(guī)劃解法略低，但結果仍然相當理想，可有效克服非線性規(guī)劃解法求解時間長、經常出現(xiàn)局部最優(yōu)解、求解效率低等弊端。新的線性規(guī)劃解法相對簡單、容易理解、易于掌握、優(yōu)化程度高，求解效率也高，運用Excel軟件就可快速求解，可有效解決圓柱形貨物擺放無約束這類復雜NP難問題。