雷定猷，閆紅瑩，洪舒華，張英貴

(1. 中南大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長(zhǎng)沙 410075； 2. 中南大學(xué) 智慧交通湖南省重點(diǎn)實(shí)驗(yàn)室，湖南 長(zhǎng)沙 410075)

高集裝箱利用率是集裝箱運(yùn)輸企業(yè)的不懈追求，但前提是必須符合集裝箱裝運(yùn)的安全規(guī)定，其中非常重要的就是實(shí)現(xiàn)集裝箱平衡裝載。滿(mǎn)足負(fù)載平衡約束是達(dá)到平衡裝載要求的必要條件，即集裝箱內(nèi)所有貨物的總重心落在特定的范圍之內(nèi)，貨物重量在箱子內(nèi)的分布均勻[1]。在陸路運(yùn)輸實(shí)際中，負(fù)載平衡是基本的要求，在確保貨物裝卸和運(yùn)輸安全、降本增效方面有非常重要的實(shí)際意義。如果裝入集裝箱的貨物之間重量差別不明顯，不用特意限制一般也能實(shí)現(xiàn)負(fù)載平衡。然而隨著運(yùn)輸種類(lèi)不斷擴(kuò)展，運(yùn)輸范圍不斷增大，在裝載過(guò)程中常常將質(zhì)量、密度大不相同的不同貨物混合裝載，如果不進(jìn)行一定的操作限制，則難以滿(mǎn)足負(fù)載平衡約束[2]。本文定義質(zhì)量、密度存在較大差距的貨物為輕重貨物，將其在滿(mǎn)足負(fù)載平衡的前提下的裝箱問(wèn)題稱(chēng)為集裝箱輕重貨物混合平衡裝載問(wèn)題。

近年來(lái)，在集裝箱布局空間表示方面，Moura等[3]證實(shí)了在求解質(zhì)量和求解效率上，最大覆蓋法相比較分割法表現(xiàn)更優(yōu)；姜義東等[4]提出三維矩形物體布局狀態(tài)空間分解可以用三叉樹(shù)來(lái)表示。在對(duì)裝箱貨物的處理方式上，F(xiàn)anslau等[5]提出貨物以組合成單元的方式進(jìn)行裝箱，結(jié)果顯示單元裝載相較單個(gè)裝載有更高的效率；朱向等[6]將裝載優(yōu)化建立在將特定類(lèi)型的貨物組合成特殊形狀單元的基礎(chǔ)上；Araya等[7]構(gòu)建了評(píng)估貨物單元的函數(shù)；雷定猷等[8]提出了利用重貨單元構(gòu)建中心骨架來(lái)控制重心位置的思想。在負(fù)載平衡約束方面，Costa等[9]、Trivella等[10]都將約束轉(zhuǎn)換成了縱、橫和豎直三個(gè)方位的限制條件；Alonson等[11]通過(guò)限制總重心位置滿(mǎn)足負(fù)載平衡要求；Moon等[1]將約束轉(zhuǎn)換成限定范圍；Ramos等[2]在統(tǒng)計(jì)測(cè)算負(fù)載后，將其表示為直觀分布圖；楊廣全等[12]基于集裝箱裝運(yùn)車(chē)輛具體的技術(shù)參數(shù)，分析提出了裝車(chē)后車(chē)輛轉(zhuǎn)向架各類(lèi)指標(biāo)的計(jì)算公式。之前對(duì)于輕重貨物混合平衡裝載問(wèn)題的研究不多，而且大多將約束簡(jiǎn)單轉(zhuǎn)化或是作為裝載方案的評(píng)價(jià)指標(biāo)，沒(méi)與實(shí)際裝運(yùn)情況糅合分析[2]，難以確保集裝箱高利用率的同時(shí)達(dá)到平衡裝載需求。

本文結(jié)合負(fù)載平衡約束，基于鐵路集裝箱裝運(yùn)車(chē)輛實(shí)際，針對(duì)輕重貨物，構(gòu)建了集裝箱平衡裝載模型，研究分析布局空間和待裝箱的輕重貨物，將待裝箱貨物細(xì)分并組合成貨物單元，再利用啟發(fā)式算法對(duì)貨物單元進(jìn)行裝箱，以此為基礎(chǔ)設(shè)計(jì)求解算法。最后，對(duì)算法進(jìn)行測(cè)試，并與采用其他算法所得結(jié)果進(jìn)行對(duì)比分析，驗(yàn)證有效性。

1 模型建立

(1)

圖1 集裝箱三維坐標(biāo)系示意

(2)

(3)

(4)

圖2 一個(gè)集裝箱裝車(chē)位置示意

由此可得箱貨總重心偏離車(chē)輛橫縱中心線距離d1和d2，以及重車(chē)重心高d3為

(5)

(6)

(7)

至此有負(fù)載平衡表達(dá)式為

(8)

裝運(yùn)兩個(gè)及以上集裝箱時(shí)，無(wú)論是單層還是雙層裝運(yùn)，其計(jì)算過(guò)程與上述過(guò)程類(lèi)似，主要區(qū)別在于求箱貨總重心位置時(shí)，需分別在每一個(gè)集裝箱各自坐標(biāo)系中單獨(dú)計(jì)算，確定集裝箱具體裝車(chē)位置以后，再轉(zhuǎn)化至同一坐標(biāo)系求所有集裝箱及貨物的總重心位置。亦可優(yōu)先確定各集裝箱的裝車(chē)位置，建立統(tǒng)一的坐標(biāo)系進(jìn)行貨物裝載和計(jì)算。此處以單層裝運(yùn)兩個(gè)相同集裝箱為例，集裝箱放置于車(chē)上的位置見(jiàn)圖3。

圖3 兩個(gè)相同集裝箱裝車(chē)位置示意

同樣地，于圖3中以鐵路車(chē)地板的左下角在軌面上的投影為坐標(biāo)原點(diǎn)建立三維坐標(biāo)系。P1和P2分別為兩集裝箱內(nèi)貨物總重量。貨物總重心在各自集裝箱內(nèi)坐標(biāo)系中的坐標(biāo)分別為(x1,y1,z1)和(x2,y2,z2)，其在新坐標(biāo)系中可分別表示為

(9)

(10)

由此可得新坐標(biāo)系下兩集裝箱和所有貨物的總重心坐標(biāo)為

(11)

(12)

(13)

把式(11)～式(13)代入式(5)～式(7)即可得到對(duì)應(yīng)的表達(dá)式。

綜合以上分析，構(gòu)建模型

(14)

s.t.

式(8)

(15)

(16)

(17)

(18)

2 算法設(shè)計(jì)

分別對(duì)布局空間和裝箱貨物兩個(gè)主體進(jìn)行分析，設(shè)計(jì)求解算法。

2.1 空間劃分、選擇與更新過(guò)程

采用最大覆蓋法劃分空間，即用如圖4中r1、r2、r3所示的3個(gè)長(zhǎng)方體來(lái)表示剩余空間，此方法可以使布局空間選擇接收更多不同組合的貨物單元。

圖4 最大覆蓋法示意

下面開(kāi)始選擇每一階段的空間，如圖5所示，假設(shè)某一空間r的頂點(diǎn)ve1的坐標(biāo)為(x1,y1,z1)，ve1對(duì)應(yīng)的集裝箱頂點(diǎn)VE1的坐標(biāo)為(x2,y2,z2)，則兩點(diǎn)之間的曼哈頓距離為|x1-x2|+|y1-y2|+|z1-z2|。集裝箱和空間r之間共有8對(duì)相對(duì)應(yīng)的頂點(diǎn)，即存在8段曼哈頓距離，定義最小者為空間r的錨距，定義錨距相對(duì)應(yīng)的空間r的頂點(diǎn)為錨角。將貨物放在擁有最短錨距的空間的錨角處，若多個(gè)空間同時(shí)擁有最短錨距，則選取體積較大者。此方法可使貨物沿著集裝箱內(nèi)壁布局，慢慢將剩余空間匯集在箱體的中間部分，便于剩余空間的再次利用。

圖5 集裝箱與空間位置關(guān)系示意

在貨物放進(jìn)被選擇的空間之后，采用最大覆蓋法劃分出3個(gè)新的剩余空間。如果存在其他的空間與放進(jìn)空間的貨物相互重疊的情況，則需要重新表示這些空間。除外，需要核查現(xiàn)有空間是否已經(jīng)是最大空間，刪去尺寸為零、重復(fù)表示或者已經(jīng)包含在最大空間里的空間。

2.2 輕重貨物單元裝載規(guī)則

先按照重量和密度對(duì)輕重貨物進(jìn)行分類(lèi)，接著分別構(gòu)造重貨和輕貨單元，最后使用不同的啟發(fā)式方法先后處理重貨單元和輕貨單元。

(1)貨物分類(lèi)

貨物對(duì)總重心位置的影響與其重量和密度成正比，按照貨物的重量和密度進(jìn)行兩次排序分類(lèi)，以待裝貨物重量的λ倍作為重貨重量，確定重貨集合。λ為重貨占比系數(shù)，其值與待裝貨物標(biāo)準(zhǔn)差成正比，通過(guò)算例測(cè)試，可知貨物重量標(biāo)準(zhǔn)差與重貨占比系數(shù)的對(duì)應(yīng)關(guān)系如表1所示時(shí)，重貨能夠較有效地構(gòu)建中心骨架。

表1 重貨占比系數(shù)取值

算法 1

輸入：待裝箱貨物集合C，重貨占比系數(shù)λ。

輸出：重貨集合K。

Step1確定候選貨物總重量和體積。QK和VK分別候選貨物的總重量和體積。若VT≤V，令VK←VT，QK←QT；否則找到a0使得V1+V2+…+Va0≤V且V1+V2+…+Va0+Va0+1>V，令VK←V1+V2+…+Va0,QK←Q1+Q2+…+Qa0。再與集裝箱載重量比較，QK←min{Q,QK}。

Step2排列候選貨物。將候選貨物按照類(lèi)重量由大到小的順序排列，在類(lèi)重量相等的情況下，將貨物數(shù)量相對(duì)少的類(lèi)排列在前；取前a1=0.5n+1類(lèi)，繼而按照類(lèi)密度由大到小順序排列，在密度相等的情況下，貨物數(shù)量少的排列在前。設(shè)該排列為C1,C2,…,Ca1。

Step3確定重貨。對(duì)于上述排列，找到a2使得Q1+Q2+…+Qa2≤λQK且Q1+Q2+…+Qa2+Qa2+1>λQK。

Step4返回K={C1,C2,…,Ca2}。

(2)貨物單元構(gòu)造

構(gòu)造貨物單元可實(shí)現(xiàn)貨物的高效裝載。貨物單元會(huì)繼承構(gòu)成它的貨物的屬性，例如貨物單元的尺寸和重量通過(guò)累加單個(gè)貨物的尺寸和重量得到，放置方位為貨物單元包含的所有貨物放置方式的交集，位置坐標(biāo)由貨物單元放入集裝箱后其左內(nèi)下角坐標(biāo)確定，重心坐標(biāo)由貨物總重心計(jì)算公式(式(1))得到。應(yīng)該特別注意的是，同一個(gè)貨物可以組合在不同的單元中，所以為了保證剩余的單元是由未裝箱的貨物組合而成，當(dāng)貨物單元b被放入箱中后，包含b中一個(gè)或多個(gè)貨物的其他貨物單元都要?jiǎng)h掉。

算法 2

輸入：重貨集合K，生成重貨單元數(shù)NK(常取10 000[5])，有效體積占比v(常取98%[5])。

輸出：重貨單元集合B。

Step1初始設(shè)置。由于單個(gè)貨物亦可視為一個(gè)單元，因此將B←K；將B′←B以遍歷組合；將SA←φ用于保存符合構(gòu)造要求的單元。

Step2進(jìn)入遍歷組合。對(duì)于B′中所有單元bi∈B′,與B中所有單元bj∈B逐一進(jìn)行組合。將bj分別放置在bi的X、Y、Z方向，構(gòu)成重貨單元bk。如果bk中包含的貨物總體積和bk最小外接長(zhǎng)方體體積的比值大于v，將SA←SA∪{bk}。

Step3生成單元數(shù)判斷。Step2結(jié)束后，如果SA≠φ，將B←SA∪B，將B′←SA，SA≠φ。同時(shí)進(jìn)行判斷，如果B中元素個(gè)數(shù)|B|>NK或者集合SA=φ，轉(zhuǎn)Step4，否則轉(zhuǎn)Step2。

Step4得到重貨單元集合B。

(3)重貨單元處理

重貨在很大程度上決定了總重心位置，因此采用中心骨架策略[9]，通過(guò)重貨單元來(lái)大概確定總重心位置；而后通過(guò)算例測(cè)試，提出新的重貨單元篩選規(guī)則，從而有效提高重貨單元組合的成功率。

算法 3

Step1搜索能夠用于構(gòu)建中心骨架的重貨單元或者單元組合。設(shè)重貨單元總重量為QB，從B中取出一個(gè)重貨單元，重量為qb，如果符合式(19)那么可單獨(dú)構(gòu)建1中心骨架；如果符合式(20)或式(21)，那么繼續(xù)搜索符合相同條件的，且不包含同個(gè)貨物的重貨單元，構(gòu)建2、3或4中心骨架。搜索到滿(mǎn)足條件的重貨單元，則將能夠構(gòu)建中心骨架的單個(gè)重貨單元或者多個(gè)單元組成的組合作為cp，并更新SK←SK∪cp；否則轉(zhuǎn)Step3。

qb≥0.8QB

(19)

0.4QB≤qb≤0.5QB

(20)

0.2QB≤qb≤0.3QB

(21)

圖6 中心骨架構(gòu)建示意

理論上中心骨架數(shù)量可增加，但中心骨架對(duì)布局空間造成的分割及自身的不穩(wěn)定性與其數(shù)量成正比，由此只考慮4及以下的中心骨架。得到候選集合SK后，取出重貨單元組合裝入箱中，如果裝箱方法有多種，那么選取能夠使得集裝箱重心最低的方法進(jìn)行裝箱。圖6中，外部的框線表示的是箱子底面輪廓，灰色的方塊表示的是重心投影在A1、A2、A3、A4的重貨單元，A″為A3和A4重心投影，A?為總重心投影。構(gòu)建中心骨架時(shí),重貨單元組合的重心投影A′要與集裝箱底面幾何中心A0重合，或兩者偏差在規(guī)定范圍內(nèi)。

若所得方案不滿(mǎn)足負(fù)載平衡約束，則對(duì)構(gòu)成中心骨架的重貨單元位置進(jìn)行調(diào)整，使得貨物總重心在底面上的投影落在箱子底面幾何中心附近滿(mǎn)足偏移規(guī)定的區(qū)域。圖7分別給出了圖6(b)、圖6(c)和圖6(d)所構(gòu)建的3種中心骨架各兩種可操作的移動(dòng)方法。

圖7 中心骨架移動(dòng)示意

(4)輕貨單元處理

構(gòu)建好中心骨架后，使用下面啟發(fā)式輕貨單元評(píng)估函數(shù)，從對(duì)應(yīng)輕貨單元集合中擇優(yōu)選擇輕貨單元完成剩余裝載布局。

(22)

式中：Vol(b)為輕貨單元b的體積；Wei(b)為b的重量；Cov(b,pl)為單元b裝箱后，由箱體內(nèi)壁及相鄰近的單元覆蓋的表面積與單元b總表面積的比值。如果鄰近單元bi的面F在單元b的正交投影覆蓋了b表面，并且F和單元b表面之間的正交距離等于或小于pl與pl所在坐標(biāo)軸方向上b的尺寸乘積，則塊b的表面積被塊bi覆蓋；Cov(b,pl)越高，說(shuō)明b和空間匹配度越高；b放入r后的空間損失率用Loss(b,r)表示，基于還沒(méi)有裝箱的輕貨單元，求解剩余不能利用的體積問(wèn)題可轉(zhuǎn)化為對(duì)b的X、Y、Z方向的一維背包問(wèn)題，求得的值與空間r體積的比值即為L(zhǎng)oss(b,r)；體積小的貨物可以用來(lái)填充剩余的小空間，因此，將體積小的貨物放在最后似乎是合理的，然而大的單元可能是由眾多小的貨物構(gòu)成的，Num(b)為單元包含的貨物數(shù)量，Num(b)值越大，代表組成貨物體積越小，反之亦然。最后，生成了如式(22)所示包含由非負(fù)參數(shù)α、β、γ、δ和ε加權(quán)的所有準(zhǔn)則的評(píng)估函數(shù)。

算法 4

輸出：輕貨單元b0。

Step2同理繼續(xù)向下求解。分別選出ω個(gè)解(Step1得到)后一步的r′,r′∈R，然后取出評(píng)估值前ω的單元，逐個(gè)放置于布局空間r′錨角處，由此產(chǎn)生ω2個(gè)解，更新集合。

Step4得到最優(yōu)解。最終得到ω2個(gè)解，判斷得到最優(yōu)解best，以及其對(duì)應(yīng)的輕貨單元b0，b0則為當(dāng)前應(yīng)裝箱的單元。

圖8 輕貨單元選擇示意(ω=2)

2.3 輕重貨物混合平衡裝載算法

綜合以上，設(shè)計(jì)求解輕重貨物混合平衡裝載的啟發(fā)式算法。

算法 5

輸出：裝載方案sbest。

Step1貨物分類(lèi)。根據(jù)算法1得到重貨集合K。

Step3構(gòu)建中心骨架。進(jìn)行判斷SK=Φ，如果是，轉(zhuǎn)step7；否則取一個(gè)cp，同時(shí)R′←R，C′←C，用cp在R′中構(gòu)建貨物單元的中心骨架。

Step6循環(huán)判定。判斷所有組合是否已遍歷完，如果是，轉(zhuǎn)Step7，否則轉(zhuǎn)Step3。

Step8返回sbest。

3 算例分析

通過(guò)對(duì)國(guó)際標(biāo)準(zhǔn)算例及輕重貨物算例進(jìn)行仿真測(cè)試，驗(yàn)證本文算法的有效性。

3.1 標(biāo)準(zhǔn)算例

表2中，使用本文算法得到的集裝箱容積利用率(Vol.)略低于其他算法，比最優(yōu)者低1.55%。其原因主要是本文設(shè)計(jì)的算法以樹(shù)形檢索為解空間搜索內(nèi)核，以確保每次選到的貨物單元都是最適合的，搜索能力弱于以遺傳算法為內(nèi)核的算法。算例使用本文算法得到的負(fù)載失衡的算例數(shù)(Unb.)均為0，百分百滿(mǎn)足集裝箱裝載平衡條件，但是其他最好的結(jié)果也可以達(dá)到98.20%，這方面差別微乎其微。通過(guò)計(jì)算直觀清晰看到，基于f(x,2,5)求得的結(jié)果，貨物的負(fù)載均勻，密度期望基本可以看作為ρc，方差非常小，只要簡(jiǎn)單處理就能夠滿(mǎn)足平衡。根據(jù)結(jié)果可知，本文設(shè)計(jì)的算法一定程度上具有普遍適應(yīng)性，但是仍然不足以說(shuō)明其對(duì)混合平衡裝載是有效的，對(duì)此還需要進(jìn)一步的測(cè)試。

3.2 輕重貨物算例

基于標(biāo)準(zhǔn)算例，增大貨物密度區(qū)間，減小密度下限值，密度上限保持當(dāng)前載重允許最大值。令ρmin=0.05ρc，ρmax=Q/[m0(n-i0)]，其中n為貨物種類(lèi)數(shù)目，i0為已經(jīng)給出了重量的貨物的種類(lèi)數(shù)目，m0為已經(jīng)給出了重量的貨物的數(shù)目。與此同時(shí)將貝塔分布改為f(x,0.075 ,0.075 )，基于修改后的參數(shù)重新進(jìn)行測(cè)算，兩貝塔的分布概率密度差異見(jiàn)圖9?；诖酥匦律? 500個(gè)算例，保持其他條件不變，結(jié)果見(jiàn)表3。

表2 標(biāo)準(zhǔn)算例測(cè)試結(jié)果

從上述測(cè)算數(shù)據(jù)可得，裝載貨物屬性一旦改變，對(duì)結(jié)果會(huì)造成非常大的改變。所有算法測(cè)算結(jié)果在集裝箱容積利用率方面都有所下降，但是總體來(lái)說(shuō)保持穩(wěn)定狀態(tài)；但是在負(fù)載平衡方面表現(xiàn)非常明顯，本文所優(yōu)化算法負(fù)載平衡條件平均滿(mǎn)足率相較最高，達(dá)95.20%。

表3 輕重貨物算例測(cè)試結(jié)果

4 結(jié)論

(1)結(jié)合負(fù)載平衡約束，基于鐵路集裝箱裝運(yùn)車(chē)輛，建立輕重貨物混合平衡裝載模型；將等待裝箱的貨物細(xì)分為輕重貨物單元，使用評(píng)估函數(shù)對(duì)輕貨單元進(jìn)行選擇裝載，形成完整的貨物裝載方案，設(shè)計(jì)相應(yīng)求解算法。

(2)構(gòu)建的模型和求解算法有效地實(shí)現(xiàn)了輕重貨物混合平衡裝載，可以確保集裝箱容積平均利用率不低于90%，同時(shí)有95.20%以上的概率滿(mǎn)足負(fù)載平衡約束。

(3)未來(lái)可根據(jù)待裝貨物密度和體積情況，同時(shí)考慮優(yōu)化集裝箱的重量利用率。