賈春玉，樸惠淑

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

條塊狀貨物裝箱問題研究成果眾多[1-2]，但圓形貨物裝箱問題研究成果非常少，多數(shù)為圓形貨物下料問題[3-4]。裝箱與下料問題雖然互為反問題，有些方法可以互用，但還是有明顯區(qū)別的，許多情況下不能直接互用。在生產(chǎn)實踐中，經(jīng)常遇到的同尺寸圓柱形貨物裝箱(或稱下料)問題，傳統(tǒng)方法是憑經(jīng)驗裝箱或下料，優(yōu)化程度低、成本高。為了解決這類問題，人們提出了多種解法。如動態(tài)規(guī)劃算法[5-6]、遞歸解法[7-9]和啟發(fā)式算法[10]等。這些方法雖然可解決這類問題，但通常需要建立較為復雜的數(shù)學模型、編制求解軟件進行求解，不易掌握；有些方法求解時間過長，影響實際運用。圓柱形貨物壓縫式擺放通常比對齊擺放方式的優(yōu)化程度高，且易于計算擺放數(shù)量，求解時間很短，但有時的優(yōu)化程度不高。雖然有人為此提出了“三塊法[6]”和“四塊法[11-13]”等，但它們的具體解法主要還是動態(tài)規(guī)劃算法、遞歸解法和啟發(fā)式算法等。

公式計算法雖然略微繁瑣，但與其他方法相比(如規(guī)劃求解法)，更容易理解，易于掌握，且運用Excel軟件可快速求解，獲得滿意近似最優(yōu)解。為此，有必要針對原有公式計算法進行研究，改進與完善公式計算法。

1 圓柱形貨物擺放的方式

圓柱形貨物擺放方式多種多樣，常用的有5類。第一類是上下對齊式擺放(在下料排樣中稱為并排)，簡稱對齊式(圖1)。第二類是緊湊壓縫式擺放(在下料排樣中稱為品排)，簡稱緊湊式。它又可分為2種擺放方式。其中，橫排緊湊壓縫式擺放簡稱橫排緊湊式(圖2)，即貨箱長度L方向?qū)浳飻[放高度方向，貨箱寬度K方向為橫向；豎排緊湊壓縫式擺放簡稱豎排緊湊式(圖3)，即貨箱寬度K方向?qū)浳飻[放高度方向，貨箱長度L方向為橫向。第三類是緊湊式和對齊式相結(jié)合擺放。它又可分為下列2種擺放方式：一是在橫排緊湊式基礎上進行對齊擺放(圖4)；二是在豎排緊湊式基礎上進行對齊擺放(圖5)。第四類是橫排和豎排相結(jié)合的擺放方式。它又可分為下列4種方式：一是橫著將貨箱分割成兩部分，讓兩部分分別按緊湊式擺放；二是在橫著分割貨箱的基礎上，緊湊式加對齊式擺放(橫著分割貨箱的擺放方式如圖6所示)；三是豎著將貨箱分割成兩部分，讓兩部分分別按緊湊式擺放；四是在豎著分割貨箱的基礎上，緊湊式加對齊式擺放。豎著分割貨箱的擺放方式如圖7所示。

圖1 上下對齊式擺放(對齊式)

圖2 橫排緊湊式

圖 3 豎排緊湊式

圖4 橫排緊湊式基礎上的對齊擺放

圖5 豎排緊湊式基礎上的對齊擺放

圖6 橫著分割貨箱的擺放方式

圖7 豎著分割貨箱的擺放方式

2 圓柱形貨物擺放的計算公式

2.1 對齊式符號設定及擺放貨物數(shù)量計算

設貨箱長為L，寬為K，圓柱形貨物半徑為R，貨物在L方向擺放數(shù)量為NL，在K方向上擺放數(shù)量為NK，可擺放貨物總數(shù)為NQ，則

(1)

式中，符號[ ]1代表向下取整。

2.2 緊湊式符號設定及擺放貨物數(shù)量計算

設H為緊湊式擺放貨物的高度，Hn為n層貨物擺放的高度，n為高度方向擺放貨物總層數(shù)。

以貨箱長L為擺放高度 (橫排緊湊式擺放)時，擺放數(shù)量為NJL，對齊擺放層數(shù)為DNL，壓縫擺放層數(shù)為YNL，剩余高度為SHL；以貨箱K為擺放高度(豎排緊湊式擺放)時，擺放數(shù)量為NJK，對齊擺放層數(shù)為DNK，壓縫擺放層數(shù)為YNK，剩余高度為SHK，則根據(jù)幾何知識，有

緊湊式擺放的每層貨物高度為：

H=30.5R

(2)

以緊湊式擺放貨物時，每層貨物節(jié)約的高度為：

G=2R-30.5R

(3)

以貨箱長L為擺放高度時，高度方向擺放貨物總層數(shù)為：

n≤ [(L-2R)/(30.5R)+1]1

(4)

擺放總高度為：

Hn=(n-1)×30.5R+2R

(5)

垛高方向(即貨箱長L方向)剩余高度為：

SHL=L-[(n-1)×30.5R+2R]

(6)

對齊擺放層數(shù)為:

DNL=[n/2]1

(7)

式中，符號[ ]1代表向上取整。

壓縫擺放層數(shù)為：

YNL=[n/2]1

(8)

以貨箱長L為擺放高度時，橫排緊湊式擺放數(shù)量的計算可分下列2種情況：

當K-[K/(2R)]1×2R

NJL=n×[K/(2R)]1-[n/2]1

(9)

當K-[K/(2R)]1×2R≥R時，

NJL=n×[K/(2R)]1

(10)

貨物在L方向的擺放數(shù)量為：

NL=n×[K/(2R)]1-{[K/(2R)]1-[(K-R)/(2R)]1} ×[n/2]1

(11)

以貨箱寬K為擺放高度時，計算公式與上述以貨箱長L為擺放高度時類似，只需把L和K互換即可，即從橫排緊湊式轉(zhuǎn)換為豎排緊湊式。

圓柱形貨物緊湊式擺放數(shù)量為：

NJ=max(NJL，NJK)

(12)

3 公式計算法的改進

3.1 第一類改進方法

第一類改進方法是剩余垛高空間增加擺放數(shù)量法，即分析剩余垛高是否可通過壓縫式轉(zhuǎn)換成對齊式而多擺貨物。其判斷條件為：K-[K/(2R)]1

對應于式(3)和式(6)，剩余高度可把緊湊壓縫式擺放層數(shù)轉(zhuǎn)變?yōu)閷R式擺放的層數(shù)為：

SNL=[SHL/G]1

(13)

因為剩余高度小于H，即SNL

[SHL/G]1≤[30.5R/(2R-30.5R)]1=6

(14)

即在剩余空間內(nèi)最多可把緊湊壓縫式擺放轉(zhuǎn)變?yōu)?層的對齊式擺放。緊湊式包括奇數(shù)層和偶數(shù)層。其中，奇數(shù)層每層擺放個數(shù)與對齊式相同；偶數(shù)層在K-[K/(2R)]1

當DNL=YNL即[n/2]1=[n/2]1時，最頂層為壓縫式擺放(偶數(shù)層)，擺放數(shù)量比對齊式擺放(奇數(shù)層)少1個。此時，由壓縫式轉(zhuǎn)變?yōu)閷R式擺放貨物增加的層數(shù)為：

SDNL=[SNL/2]1

(15)

當DNL>YNL即[n/2]1>[n/2]1時，最頂層為對齊式擺放(單數(shù)層)，由壓縫式轉(zhuǎn)變?yōu)閷R式擺放貨物增加的層數(shù)為：

SDNL=[SNL/2]1

(16)

對于緊湊式擺放，當K-[K/(2R)]1×2R≥R時，式(12)成立；當K-[K/(2R)]1×2R

NJ=max(NJL+SDNL，NJK+SDNK)

(17)

式中：SDNK為豎排緊湊式下，由壓縫式轉(zhuǎn)變?yōu)閷R式擺放時增加的貨物層數(shù)。

3.2 第二類改進方法

第二類改進方法是橫切法,即按貨箱長度方向橫著分割貨箱(分割線與貨箱寬度邊緣平行)。其分割方式有下列2種：一是以2R+H為長度劃分割線，分割后對剩余部分L-(2R+H)采用壓縫式擺放的公式計算法，計算橫、豎2種擺放方式下總的擺放數(shù)量，擇優(yōu)作為優(yōu)化結(jié)果；二是以2R+2H為長度劃分割線，分割后對剩余部分L-(2R+2H)采用壓縫式擺放的公式計算法，計算橫、豎2種擺放方式下總的擺放數(shù)量，擇優(yōu)作為優(yōu)化結(jié)果。

3.3 第三類改進方法

第三類改進方法是豎切法，即按貨箱寬度方向豎著分割貨箱(分割線與貨箱長度邊緣平行)。其分割方式有下列2種：一是以2R+H為長度劃分割線，分割后對剩余部分K-(2R+H)采用壓縫式擺放的公式計算法，計算橫、豎2種擺放方式下總的擺放數(shù)量，擇優(yōu)作為優(yōu)化結(jié)果；二是以2R+2H為長度劃分割線，分割后對剩余部分K-(2R+2H)采用壓縫式擺放的公式計算法，計算橫、豎2種擺放方式下總的擺放數(shù)量，擇優(yōu)作為優(yōu)化結(jié)果。

4 圓柱形貨物裝箱問題求解實例

4.1 實例1

貨箱長(L)2 000 cm、寬(K)1 000 cm，貨物為半徑(R)71.5 cm的圓柱形，需求解貨箱中最多能擺放貨物的數(shù)量。

4.1.1 采用第一類改進方法求解

因為R=71.5 cm，所以2R=2×71.5=143(cm)。

NL=[L/(2R)]1=[2 000/143]1=13(個)，

NK=[K/(2R)]1=[1 000/143]1=6(個)，

NQ=[L/(2R)]1×[K/(2R)]1=13×6=78(個)。

H=30.5R=30.5×71.5≈123.84(cm)，

G=2R-30.5R=143-123.84=19.16(cm)，

n≤[[(L-2R)/(30.5R)]+1]1=[[(2 000-143)/123.84]+1]1=15(層),

Hn=(n-1)×30.5R+2R=(15-1)×123.84+143=1 876.78(cm),

SHL=L-[(n-1)×30.5R+2R]=2 000-1 876.78=123.21(cm),

DNL=[n/2]1=[15/2]1=8(層),

YNL=[n/2]1=[15/2]1=7(層)。

因為K-[K/(2R)]1×2R=1 000-[ 1 000/143]1×143=142>71.5,所以奇數(shù)層和偶數(shù)層擺放數(shù)量相等,有:

NJL=n×[K/(2R)]1=15×[1 000/143]1=15×6=90(個)。

因為奇數(shù)層和偶數(shù)層擺放數(shù)量相等,所以剩余高度無法通過壓縫擺放將奇數(shù)層轉(zhuǎn)變?yōu)閷R擺放層來增加擺放數(shù)量。

因此，SDNL=0。

把貨箱長L與貨箱寬K對調(diào)，即運用Excel計算時，把這2個數(shù)據(jù)對換，計算可得：

NJK=91 個，SDNK=0。

根據(jù)式(17)，NJ=max(90+0,91+0)=91(個)

4.1.2 采用第二類改進方法求解

因篇幅所限，這里不再進行具體計算，而只給出第二類改進方法(橫著分割貨箱)的下列計算結(jié)果：橫切長度為2R+H，即266.842 cm;切掉部分總尺寸為1 000×266.842 cm,可擺放12個;剩余部分總尺寸為1 000×1 733.158 cm，可擺放83個；最終擺放數(shù)量為兩部分擺放數(shù)量之和，即95個。

4.1.3 采用第三類改進方法求解

因篇幅所限，這里不再進行具體計算，而只給出第三類改進方法(豎著分割貨箱)的下列計算結(jié)果：豎切長度為2R+H，即266.842 cm;切掉部分總尺寸為2 000×266.842 cm，可擺放26個;剩余部分總尺寸為2 000×733.158 cm，可擺放71個；最終擺放數(shù)量為兩部分擺放數(shù)量之和，即97個。

4.2 實例2

以文獻[9]下料問題為例。原材料長L為600 mm，寬K為430 mm。下料貨物為半徑(R)15.5 mm的圓形截面毛坯。需求解原材料能下毛坯的最大數(shù)量。

分析可知，文獻[9]下料問題沒有最大下料排數(shù)限制，沒有加工余量要求，與裝箱問題一樣。文獻[9]解法可下282個毛坯。運用公式計算法按貨箱長度優(yōu)化,可擺放286個毛坯；豎切長度為2R+H，即26.86 mm，切下部分尺寸為600 mm×26.85 mm，可擺放37個，剩余部分尺寸為600 mm×372.15 mm，按貨箱長度進行優(yōu)化，可擺放254個，最終擺放數(shù)量為兩部分擺放數(shù)量之和，為291個毛坯(豎著分割貨箱時)。

顯然，本文改進的公式計算法好于文獻[9]遞歸解法。

5 幾種方法的比較

隨機試驗50個樣本，貨物半徑尺寸區(qū)間為8.5～71.5 cm，貨箱二維尺寸區(qū)間為190～3 000 cm。分別用改進前壓縫擺放方式、第一類改進方法、第二類改進方法(橫切法)和第三類改進方法(豎切法)計算擺放數(shù)量。

改進前壓縫擺放方式的優(yōu)化程度較高，但當貨箱邊緣擺放后剩余尺寸較大時，優(yōu)化程度不理想，在50個隨機樣本中，改進前壓縫擺放方式有35個樣本為擺放數(shù)量最多狀態(tài)，占樣本總數(shù)的70%；第一類改進方法有36個樣本為擺放數(shù)量最多狀態(tài)，占樣本總數(shù)的72%；第二類改進方法中橫切(以2R+H為長度劃分割線)時有13個樣本為擺放數(shù)量最多狀態(tài),占比26%；第三類改進方法中豎切(以2R+H為長度劃分割線)時有14個樣本為擺放數(shù)量最多狀態(tài),占比28%，豎切(以2R+2H為長度劃分割線)時有23個樣本為擺放數(shù)量最多狀態(tài),占比46%。3類改進方法合計比改進前擺放數(shù)量最多狀態(tài)多出現(xiàn)15次,占比30%,可見,有30%的樣本可提高優(yōu)化程度。在這15次中, 第一類改進方法有1次且是與豎切(以2R+2H為長度劃分割線)時共同出現(xiàn)的擺放數(shù)量最多狀態(tài)，占比改進前擺放數(shù)量最多狀態(tài)多出現(xiàn)次數(shù)的6.7%，共有4次比改進前擺放數(shù)量多，占能改進的比例為26.7%。第二類改進方法中橫切(以2R+H為長度劃分割線)時有1次擺放數(shù)量為最多狀態(tài)，占比改進前擺放數(shù)量最多狀態(tài)多出現(xiàn)次數(shù)的6.7%，共有2次比改進前擺放數(shù)量多，占能改進的比例為13.4%。第三類改進方法中豎切(以2R+H為長度劃分割線)時有5次最多、占比改進前擺放數(shù)量最多狀態(tài)多出現(xiàn)次數(shù)的33.3%，共有7次能改進，占能改進的比例為46.7%；豎切(以2R+2H為長度劃分割線)時有9次最多，占比改進前擺放數(shù)量最多狀態(tài)多出現(xiàn)次數(shù)的60%，共有13次能改進，占能改進的比例為86.7%。第三類改進方法擺放數(shù)量最多狀態(tài)合計14次，占比改進前擺放數(shù)量最多狀態(tài)多出現(xiàn)次數(shù)的93.3%，第三類改進方法能改進合計次數(shù)為15次，占能改進的比例為100%?？梢姡@3類改進方法都可以多擺放貨物、提高優(yōu)化程度，但效果不同，第三類改進方法的效果最好。

6 結(jié) 論

壓縫擺放的公式計算法改進前雖然多數(shù)情況(約70%)的優(yōu)化程度較理想，但優(yōu)化程度仍有提升空間。隨機試驗顯示，運用本文3類改進方法時30%可提高優(yōu)化程度，第一類改進方法(即剩余垛高空間增加擺放數(shù)量法，能增加的擺放數(shù)量有限，最大值為3個；第二類改進方法(即橫切法)，約26.7%能提高原有壓縫擺放方式的優(yōu)化程度；第三類改進方法(即豎切法)，約100%能提高原有壓縫擺放方式的優(yōu)化程度，是效果最好的改進方法。

壓縫擺放問題解法較多，各有優(yōu)缺點。非線性規(guī)劃解法雖然數(shù)學模型簡單、明了，但求解時可能會出現(xiàn)局部最優(yōu)解，每次求解結(jié)果不一樣，存在求解時時間過長的缺陷。其他啟發(fā)式智能解法相對復雜、不易掌握、有時求解時間長、優(yōu)化程度不夠理想。公式計算法雖然計算工作量稍大，但容易理解，運用Excel軟件編制計算公式后，只要輸入原始數(shù)據(jù)即可快速得出三大類情況的各種優(yōu)化方案，求解速度較快，優(yōu)化程度較理想，便于實際運用。