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

(1. 中南大學 交通運輸工程學院，湖南 長沙 410075； 2. 中南大學 智慧交通湖南省重點實驗室，湖南 長沙 410075)

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

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

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

1 模型建立

(1)

圖1 集裝箱三維坐標系示意

(2)

(3)

(4)

圖2 一個集裝箱裝車位置示意

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

(5)

(6)

(7)

至此有負載平衡表達式為

(8)

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

圖3 兩個相同集裝箱裝車位置示意

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

(9)

(10)

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

(11)

(12)

(13)

把式(11)～式(13)代入式(5)～式(7)即可得到對應的表達式。

綜合以上分析，構建模型

(14)

s.t.

式(8)

(15)

(16)

(17)

(18)

2 算法設計

分別對布局空間和裝箱貨物兩個主體進行分析，設計求解算法。

2.1 空間劃分、選擇與更新過程

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

圖4 最大覆蓋法示意

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

圖5 集裝箱與空間位置關系示意

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

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

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

(1)貨物分類

貨物對總重心位置的影響與其重量和密度成正比，按照貨物的重量和密度進行兩次排序分類，以待裝貨物重量的λ倍作為重貨重量，確定重貨集合。λ為重貨占比系數(shù)，其值與待裝貨物標準差成正比，通過算例測試，可知貨物重量標準差與重貨占比系數(shù)的對應關系如表1所示時，重貨能夠較有效地構建中心骨架。

表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排列候選貨物。將候選貨物按照類重量由大到小的順序排列，在類重量相等的情況下，將貨物數(shù)量相對少的類排列在前；取前a1=0.5n+1類，繼而按照類密度由大到小順序排列，在密度相等的情況下，貨物數(shù)量少的排列在前。設該排列為C1,C2,…,Ca1。

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

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

(2)貨物單元構造

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

算法 2

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

輸出：重貨單元集合B。

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

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

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

Step4得到重貨單元集合B。

(3)重貨單元處理

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

算法 3

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

qb≥0.8QB

(19)

0.4QB≤qb≤0.5QB

(20)

0.2QB≤qb≤0.3QB

(21)

圖6 中心骨架構建示意

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

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

圖7 中心骨架移動示意

(4)輕貨單元處理

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

(22)

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

算法 4

輸出：輕貨單元b0。

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

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

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

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

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

算法 5

輸出：裝載方案sbest。

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

Step3構建中心骨架。進行判斷SK=Φ，如果是，轉step7；否則取一個cp，同時R′←R，C′←C，用cp在R′中構建貨物單元的中心骨架。

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

Step8返回sbest。

3 算例分析

通過對國際標準算例及輕重貨物算例進行仿真測試，驗證本文算法的有效性。

3.1 標準算例

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

3.2 輕重貨物算例

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

表2 標準算例測試結果

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

表3 輕重貨物算例測試結果

4 結論

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

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

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