賈春玉，樸惠淑

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

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

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

1 圓柱形貨物擺放的方式

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

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

圖2 橫排緊湊式

圖 3 豎排緊湊式

圖4 橫排緊湊式基礎(chǔ)上的對(duì)齊擺放

圖5 豎排緊湊式基礎(chǔ)上的對(duì)齊擺放

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

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

2 圓柱形貨物擺放的計(jì)算公式

2.1 對(duì)齊式符號(hào)設(shè)定及擺放貨物數(shù)量計(jì)算

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

(1)

式中，符號(hào)[ ]1代表向下取整。

2.2 緊湊式符號(hào)設(shè)定及擺放貨物數(shù)量計(jì)算

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

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

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

H=30.5R

(2)

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

G=2R-30.5R

(3)

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

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

(4)

擺放總高度為：

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

(5)

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

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

(6)

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

DNL=[n/2]1

(7)

式中，符號(hào)[ ]1代表向上取整。

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

YNL=[n/2]1

(8)

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

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

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

(9)

當(dāng)K-[K/(2R)]1×2R≥R時(shí)，

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為擺放高度時(shí)，計(jì)算公式與上述以貨箱長(zhǎng)L為擺放高度時(shí)類似，只需把L和K互換即可，即從橫排緊湊式轉(zhuǎn)換為豎排緊湊式。

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

NJ=max(NJL，NJK)

(12)

3 公式計(jì)算法的改進(jìn)

3.1 第一類改進(jìn)方法

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

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

SNL=[SHL/G]1

(13)

因?yàn)槭Ｓ喔叨刃∮贖，即SNL

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

(14)

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

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

SDNL=[SNL/2]1

(15)

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

SDNL=[SNL/2]1

(16)

對(duì)于緊湊式擺放，當(dāng)K-[K/(2R)]1×2R≥R時(shí)，式(12)成立；當(dāng)K-[K/(2R)]1×2R

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

(17)

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

3.2 第二類改進(jìn)方法

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

3.3 第三類改進(jìn)方法

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

4 圓柱形貨物裝箱問題求解實(shí)例

4.1 實(shí)例1

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

4.1.1 采用第一類改進(jìn)方法求解

因?yàn)镽=71.5 cm，所以2R=2×71.5=143(cm)。

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

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

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

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(層)。

因?yàn)镵-[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(個(gè))。

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

因此，SDNL=0。

把貨箱長(zhǎng)L與貨箱寬K對(duì)調(diào)，即運(yùn)用Excel計(jì)算時(shí)，把這2個(gè)數(shù)據(jù)對(duì)換，計(jì)算可得：

NJK=91 個(gè)，SDNK=0。

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

4.1.2 采用第二類改進(jìn)方法求解

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

4.1.3 采用第三類改進(jìn)方法求解

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

4.2 實(shí)例2

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

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

顯然，本文改進(jìn)的公式計(jì)算法好于文獻(xiàn)[9]遞歸解法。

5 幾種方法的比較

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

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

6 結(jié) 論

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

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