雷定猷，洪舒華，張英貴

1.中南大學(xué) 交通運(yùn)輸工程學(xué)院，長沙410075

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

1 引言

集裝箱平衡裝載必須滿足負(fù)載平衡約束，即貨物總重心位置在規(guī)定范圍內(nèi)，裝運(yùn)車輛受均勻載荷[1]。該約束是公路和鐵路等貨物裝運(yùn)實(shí)踐中的基本約束，對于保障裝卸運(yùn)輸中的貨物及設(shè)備安全、提升作業(yè)效率、減少運(yùn)輸成本和能源消耗等各方面都有積極意義，同時(shí)也是實(shí)現(xiàn)貨物機(jī)械裝運(yùn)自動(dòng)化、一體化的關(guān)鍵所在。貨物輕重差別較小時(shí)，無需專門操作往往也可實(shí)現(xiàn)負(fù)載平衡。但隨著集裝箱應(yīng)用領(lǐng)域不斷拓展，運(yùn)輸范圍不斷延伸，以及裝運(yùn)貨物不斷增多，在實(shí)際裝貨過程中，常把重量較大的貨物與重量較小的貨物混合裝載，這種情況下若無特殊處理，負(fù)載平衡約束難以滿足[2]。本文將這類把輕重差異較大的貨物混合裝入同一集裝箱的問題稱為集裝箱輕重貨物混合平衡裝載問題，它是集裝箱裝載布局問題的一個(gè)子類，是NP-hard問題。

近年來，在集裝箱布局空間表示方面，Moura 和Oliveira[3]證明最大覆蓋法在求解時(shí)間和解的質(zhì)量上比分割法更有優(yōu)勢；姜義東等人[4]則利用三叉樹結(jié)構(gòu)表示空間的分解狀態(tài)。在待裝貨物處理方面，F(xiàn)anslau 和Bortfeldt[5]提出將多種不同貨物組合成貨物單元，并驗(yàn)證用貨物單元裝載比用單個(gè)貨物更高效；朱向等人[6]針對集重貨物提出構(gòu)建塔型貨物單元；Araya等人[7]提出一個(gè)有效的貨物單元評估函數(shù)；Zhu 等人[8]將集裝箱裝載布局問題歸納為6個(gè)要素，并提出了簡潔高效的二步前瞻檢索策略；雷定猷等人[9]結(jié)合裝運(yùn)實(shí)際，提出中心骨架思想。在負(fù)載平衡約束研究方面，Costa 和Captivo[10]，Trivella 和Pisinger[11]都將其劃分為縱向、橫向和豎直方向三個(gè)子約束；Teresa等人[12]在處理負(fù)載平衡約束時(shí)，要求貨物總重心盡可能靠近集裝箱幾何中心；Moon 和Nguyen[1]將負(fù)載平衡約束表示為一個(gè)可行區(qū)域；Ramos等人[2]通過負(fù)載分析，將負(fù)載平衡約束轉(zhuǎn)換為負(fù)載分布圖。目前針對輕重貨物混合平衡裝載的研究較少，且多將負(fù)載平衡約束簡化處理或僅作為解的評價(jià)指標(biāo)，沒有結(jié)合實(shí)際裝運(yùn)車輛進(jìn)行分析[2]，難以在保持較高集裝箱利用率的同時(shí)實(shí)現(xiàn)符合實(shí)際情況的負(fù)載平衡。

本文結(jié)合集裝箱裝運(yùn)車輛，將負(fù)載平衡約束量化為負(fù)載平衡函數(shù)，建立輕重貨物混合平衡裝載模型；通過對布局空間和待裝貨物進(jìn)行分析，把貨物組合成輕重貨物單元，用啟發(fā)式算法進(jìn)行分類處理，提出輕重貨物混合平衡裝載算法；最后利用標(biāo)準(zhǔn)算例和輕重貨物算例進(jìn)行測試并與其他算法比較，驗(yàn)證算法可行性和實(shí)用性。

2 模型建立

集裝箱幾何中心被一致認(rèn)為是貨物總重心的理想位置[2]，可用貨物總重心偏離集裝箱幾何中心的距離表示負(fù)載平衡約束。在包含了負(fù)載平衡約束的傳統(tǒng)模型中，一般是在縱向、橫向和豎直方向三個(gè)維度上分別給定貨物總重心位置的容許偏移量，偏移過量則視為負(fù)載失衡。這種方法對于有明確統(tǒng)一標(biāo)準(zhǔn)的鐵路運(yùn)輸來說是可行的，但對于公路運(yùn)輸有較大局限性，因?yàn)椴煌牡貐^(qū)、路面、車輛和貨物等都有著不同標(biāo)準(zhǔn)，缺乏統(tǒng)一的量化方法。為解決這一問題，嘗試通過力學(xué)分析構(gòu)造負(fù)載平衡函數(shù)。

2.1 負(fù)載平衡函數(shù)

負(fù)載平衡函數(shù)將負(fù)載平衡約束精確地描述為貨物總重心位置與貨物最大容許重量之間的關(guān)系，利用它可以得知當(dāng)貨物總重心位于某一點(diǎn)時(shí)，車輛能夠安全承載的貨物總重上限。由于輕重貨物混合裝載時(shí)，優(yōu)先裝載重貨，在車輛載重限定內(nèi)極少出現(xiàn)重心在豎直方向上偏移過量的情況，因此主要考慮縱向和橫向負(fù)載平衡函數(shù)。具體構(gòu)造過程如下。

圖1 所示是一輛板架式三軸集裝箱卡車縱向和橫向示意圖，假設(shè)車輛左右兩邊對稱，整車重量集中于點(diǎn)CG ，每個(gè)車輪代表一個(gè)軸，車輪上力的作用點(diǎn)位于其軸心。由于車軸超過兩個(gè)，系統(tǒng)是超靜定結(jié)構(gòu)，為便于計(jì)算，將軸劃分為前軸和后軸，使用前后軸的理論中心線位置進(jìn)行計(jì)算[2]。

圖1 集裝箱卡車縱橫示意及負(fù)載平衡函數(shù)曲線

構(gòu)造縱向負(fù)載平衡函數(shù)需知空車重量(U=19 t,g取10 N/kg)、空車重心位置(CG)、前軸最大容許載重量(FAmax=12 t)、前軸最小轉(zhuǎn)向載重比(%FAmin=0.30)、后軸最大容許載重量(RAmax=19 t)、后軸最小驅(qū)動(dòng)載重比(%RAmin=0.44)、車輛最大容許載重量(Pmax=9 t)、前后軸中心線位置(FC,RC) 、前后軸中心線距離(D3=5.425 m)、前軸與空車重心位置距離(D2=2.426 m)以及前軸與集裝箱靠近車頭端內(nèi)壁的距離(D1=1.698 m)。

構(gòu)造橫向負(fù)載平衡函數(shù)需知車輛行駛軌跡寬度(D4=1.750 m)、集裝箱內(nèi)尺寸寬度(D5=2.330 m)以及貨物的橫向偏移量（一般為車輛行駛軌跡寬度的給定百分比），但該值會(huì)隨胎壓、懸掛彈簧撓度等機(jī)械特性而改變，因此使用負(fù)載轉(zhuǎn)移比進(jìn)行計(jì)算。負(fù)載轉(zhuǎn)移比LMR量化了從車輛一側(cè)到另一側(cè)的負(fù)載轉(zhuǎn)移[12]，如式（1）所示可用單側(cè)支撐載荷Tl和Tr求得，當(dāng)負(fù)載均勻分布時(shí)等于0。為防止側(cè)翻，車輛在出廠時(shí)就設(shè)定了該值的極值，對于本文所述車輛，LMR=±0.055。

站立于車輛尾部，面對車尾，規(guī)定左手端為集裝箱左端，靠近車頭端為集裝箱內(nèi)端。用x 和y 分別表示貨物總重心距集裝箱內(nèi)端內(nèi)壁和左端內(nèi)壁的距離，即貨物總重心在縱向和橫向上的位置；Px表示貨物總重心縱向位置為x 時(shí)的貨物最大容許重量，Py表示貨物總重心橫向位置為y 時(shí)的貨物最大容許重量。

在縱向列靜態(tài)平衡方程如下：

根據(jù)車輛最大容許載重量有：

將數(shù)據(jù)帶入式（2）～（6）可得縱向函數(shù)：

利用縱向函數(shù)可繪制圖1（a）所示曲線，可行域?yàn)棣竫。

在橫向列靜態(tài)平衡方程如下：

根據(jù)車輛最大容許載重量有：

將數(shù)據(jù)帶入式（8）和（9）可得橫向函數(shù)：

利用橫向函數(shù)可繪制圖1（b）所示曲線，可行域?yàn)棣竬。

2.2 平衡裝載模型

假設(shè)貨物均為長方體或能包裝為長方體，能夠承重且不是危險(xiǎn)品等特殊貨物。在集裝箱內(nèi)部，以其左內(nèi)下角為坐標(biāo)原點(diǎn)（圖1點(diǎn)O）建立三維坐標(biāo)系。L,W,H,V分別表示集裝箱內(nèi)部長、寬、高和體積，集裝箱載重量Q等于車輛最大容許載重量Pmax；集合C={C1,C2,…,Ci,…,Cn}表示n 類待裝貨物，它們的總重量和總體積分別為QT和VT，其中Ci={ci1,ci2,…,cij,…,cim}表示第i 類貨物中有m 個(gè)貨物，類重量和類體積分別為Qi和Vi；li,wi,hi,qi,vi分別表示第i 類貨物的長、寬、高、重量和體積；分別表示第i 類貨物放入集裝箱后，投影在X,Y,Z 軸方向上的尺寸長度；裝載狀態(tài)變量uij=0或1 分別表示貨物cij未放入或已放入集裝箱；(xij,yij,zij)和()分別表示貨物cij放入集裝箱后，cij的左內(nèi)下角（與集裝箱方位規(guī)定一致）頂點(diǎn)坐標(biāo)和重心坐標(biāo)；(CGx,CGy,CGz)表示集裝箱中所有貨物的總重心坐標(biāo)，其中：

CGx對應(yīng)于縱向函數(shù)中的x，CGy對應(yīng)于橫向函數(shù)中的y。

根據(jù)上述分析，采用公路集裝箱車負(fù)載平衡函數(shù)，以集裝箱容積利用率最大為目標(biāo)建立模型：

式（14）和（15）為負(fù)載平衡約束，規(guī)定貨物總重心縱向和橫向坐標(biāo)與貨物總重量關(guān)系滿足相應(yīng)可行域；式（16）規(guī)定任一貨物cij不能超出集裝箱邊界；式（17）要求任意兩貨物cij和cef不能互相重疊，即如果兩者同時(shí)放入集裝箱，它們在X,Y,Z 軸上的三對坐標(biāo)必須有一對滿足坐標(biāo)值較小者與貨物相應(yīng)尺寸之和不能大于坐標(biāo)值較大者，式中假設(shè)cij的三個(gè)坐標(biāo)值均小于cef；式（18）為重量約束；式（19）為旋轉(zhuǎn)約束，表示貨物可經(jīng)旋轉(zhuǎn)實(shí)現(xiàn)的所有可行放置方式，μ1和μ2為0-1 變量，取1 時(shí)分別表示貨物的長和寬能夠垂直于水平面（X-Y 平面），此時(shí)貨物共有6種放置方式。若某類貨物C0頂面必須朝上，即只允許高垂直于水平面，則μ1=μ2=0，其旋轉(zhuǎn)約束可簡化為：

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

圍繞集裝箱布局空間和待裝貨物進(jìn)行討論，通過空間劃分選擇與更新、輕重貨物分組與單元構(gòu)造，以及貨物單元分類處理等操作，設(shè)計(jì)輕重貨物混合平衡裝載算法。

3.1 空間劃分選擇與更新過程

為使集裝箱布局空間每次可接收更多不同的貨物單元，采用最大覆蓋法，貨物放入空間后，用3個(gè)互相重疊的最大長方體表示剩余空間，如圖2中r1,r2,r3所示。

圖2 最大覆蓋法示意

確定劃分方式后開始選擇空間。如圖3所示，空間r 為集裝箱中某一空間，設(shè)其頂點(diǎn)ve1 坐標(biāo)為(x1,y1,z1),與之對應(yīng)的集裝箱頂點(diǎn)VE1 坐標(biāo)為(x2,y2,z2),兩點(diǎn)間曼哈頓距離為 ||x1-x2+ ||y1-y2+ ||z1-z2。類似可得其余7 段曼哈頓距離，將其中最短者稱為錨距，與之對應(yīng)的空間r 的頂點(diǎn)稱為錨角[8]。選擇空間時(shí)，選取擁有最短錨距者，并將貨物放在它的錨角處，這樣布局可使貨物緊靠集裝箱內(nèi)壁，剩余空間會(huì)逐步聚集于集裝箱中部而非分散在各處，有利于剩余空間的合并利用。

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

空間被選中放入貨物后，用最大覆蓋法將其劃分成3個(gè)新空間。若其余空間與放入貨物產(chǎn)生重疊，還需將重疊部分刪去，即用最大覆蓋法重新表示這些空間，至多可劃分為6 個(gè)新空間。此外需檢查現(xiàn)有空間是否已為最大，將被最大空間包含的小空間刪去。

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

考慮輕重貨物對總重心位置的影響程度不同，將其分為重貨和輕貨，分別構(gòu)造貨物單元，用不同的啟發(fā)式方法進(jìn)行處理。

3.2.1 貨物分類

貨物重量和密度越大，對總重心位置的影響越大，因此貨物分類需按貨物重量和密度進(jìn)行兩次排序。

算法1 貨物分類算法

輸入：貨物集合C，重貨占比系數(shù)λ；

輸出：重貨集合K 。

步驟1 確定候選貨物重量和體積。先將待裝貨物按類密度降序排列，設(shè)候選貨物總重量和總體積分別為QK和VK，若VT≤V ，則令VK=VT,QK=QT；否則找到a0使得V1+V2+…+Vi+…+Va0≤V 且V1+V2+…+Vi+…+＞V,令VK=V1+V2+…+Vi+…+Va0,QK=Q1+Q2+…+Qi+…+Qa0。而后與集裝箱載重量比較，令QK=min{Q,QK}。

步驟2 降序排列。把候選貨物按類重量降序排列，若重量相同，類貨物個(gè)數(shù)較少的排前，取前a1=0.5n+1類；再按類密度降序排列，若密度相同，類貨物個(gè)數(shù)較少的排前。設(shè)該排列為C1,C2,…,Ca1。

步驟3 確定重貨。對于上述排列，找到a2使得Q1+Q2+…+Qi+…+Qa2≤λQK且Q1+Q2+…+Qi+…+（λ 常取0.4）。

步驟4 返回重貨集合K={C1,C2,…,Ca2}。

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

構(gòu)造貨物單元可實(shí)現(xiàn)貨物的高效裝載。需注意，同一個(gè)貨物可存在于不同的貨物單元，一旦某貨物單元b被選擇放入集裝箱后，其余包含b 中貨物的所有貨物單元都需刪去，即確保剩余貨物單元能夠由未裝載的貨物組成。貨物單元的旋轉(zhuǎn)約束為其包含的所有貨物旋轉(zhuǎn)約束的交集。

算法2 貨物單元構(gòu)造算法（以輸入重貨進(jìn)行敘述）

輸入：重貨集合K ，生成重貨單元數(shù)NK；

輸出：重貨單元集合B。

步驟1 初始化。將集合K 中重貨放入集合B（即單個(gè)貨物也看作一個(gè)貨物單元）；把集合B 中的重貨單元復(fù)制到集合B′ ，用于遍歷組合；集合SA 賦空集，存放滿足構(gòu)造條件的貨物單元。

步驟2 進(jìn)入循環(huán)。遍歷集合B′ 和B，每次分別取出一個(gè)重貨單元b1和b2，將b2以其旋轉(zhuǎn)約束允許的所有放置方式依次靠在b1的三個(gè)坐標(biāo)軸方向，組成重貨單元b3。若b3中所有貨物的體積與其最小外接長方體體積之比大于0.98，則滿足構(gòu)造條件，將b3放入集合SA。

步驟3 數(shù)量判斷。循環(huán)完畢后，若集合SA 不為空，將集合SA 與集合B 的并集交給集合B，將集合SA交給集合B′ 用于下一次遍歷組合，集合SA 重新賦空集，同時(shí)判斷集合B 中重貨單元數(shù)是否大于NK（常取10 000），是則轉(zhuǎn)步驟4，否則轉(zhuǎn)步驟2；若集合SA 為空，轉(zhuǎn)步驟4。

步驟4 返回規(guī)定數(shù)量的重貨單元集合B。

3.2.3 重貨單元處理

由于重貨對總重心位置影響較大，可優(yōu)先選取若干重貨單元固定總重心位置，即采用中心骨架思想[9]，并提出新的中心骨架構(gòu)建規(guī)則。

算法3 重貨單元組合算法

輸入：貨物集合C，重貨單元集合B；

輸出：中心骨架候選集合SK ，候選集合中各組合對應(yīng)輕貨單元集合的集合

步驟1 搜索重貨單元。設(shè)一個(gè)重貨單元重量為qb，所有重貨單元總重量為QB，搜索集合B，每次取出一個(gè)重貨單元，若其滿足式（21），可單獨(dú)構(gòu)建1 中心骨架；若其滿足式（22），則繼續(xù)搜索一個(gè)同類單元（不包含同一貨物，下同），二者可構(gòu)建2 中心骨架，或搜索兩個(gè)滿足式（24）的單元，三者可構(gòu)建3 中心骨架；若其滿足式（23），則繼續(xù)搜索兩個(gè)同類單元，三者可構(gòu)建3 中心骨架；若其滿足式（24），則繼續(xù)搜索三個(gè)同類單元，四者可構(gòu)建4 中心骨架。搜索到滿足上述中心骨架構(gòu)建條件的重貨單元，則轉(zhuǎn)步驟2；否則轉(zhuǎn)步驟4。

步驟2 構(gòu)成組合。將能夠一同構(gòu)建中心骨架的一個(gè)或若干重貨單元作為組合cp，放入中心骨架候選集合SK 。

步驟3 生成輕貨集合。復(fù)制集合C 到集合C′ ，刪去集合C′ 中包含在cp 內(nèi)的重貨，剩余貨物為輕貨，調(diào)用算法2，輸入集合C′和輕貨單元數(shù)得到輕貨單元集合（每個(gè)組合都存在不同的、與之對應(yīng)的輕貨集合），把集合放入集合，隨后轉(zhuǎn)步驟1。

步驟4 返回中心骨架候選集合SK 和各組合對應(yīng)輕貨單元集合的集合。

中心骨架數(shù)理論上還可繼續(xù)增加，但骨架的不穩(wěn)定性和對空間的分割會(huì)隨骨架數(shù)量的增加而增大，因此文本僅構(gòu)建4 及以下中心骨架。確定中心骨架候選集合后，從中取出重貨單元組合放入集裝箱中構(gòu)建中心骨架。若重貨單元有超過1種放置方式，選擇重心高度最低者。以圖4（b）為例，黑色線框表示集裝箱底面，灰色方塊表示兩個(gè)重貨單元，其重心投影分別位于A1和A2，放置時(shí)需要重貨單元組合的重心投影A′與集裝箱底面幾何中心A0重合。

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

當(dāng)所得裝載方案不滿足負(fù)載平衡約束時(shí)，需對重貨單元進(jìn)行移動(dòng)。將所得方案的貨物總重心位置視為重貨單元組合的重心位置，移動(dòng)重貨單元，使其組合重心在集裝箱底面的投影重回集裝箱底面幾何中心。圖5所示為圖4（b）、（c）和（d）各兩種可能的移動(dòng)方式。

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

3.2.4 輕貨單元處理

下面是輕貨單元評估函數(shù)：

式（25）中，Vol(b)表示輕貨單元b 的體積；Cov(b,pl)反映b 放入集裝箱后，集裝箱內(nèi)壁及其他貨物單元，對b的表面覆蓋率，可以是直接接觸覆蓋，或是距離小于pl與pl 所在坐標(biāo)軸方向上集裝箱尺寸乘積的投影覆蓋，覆蓋率越高，說明b 對已選空間的契合度越高；Loss(b,r)為b 放入空間以后造成的空間損失率，具體值為b 放入空間r 后，用剩余的輕貨單元對b 的三個(gè)坐標(biāo)軸方向分別求一維背包問題，得到的剩余無法利用的空間體積與空間r 原本體積之比；Num(b)表示構(gòu)成b 的貨物個(gè)數(shù)，在體積和重量相同的情況下，其值越小，說明構(gòu)成b 的單個(gè)貨物的體積和重量越大；在前人研究基礎(chǔ)上新增Wei(b)表示b 的重量，它將引導(dǎo)輕貨單元中較重者被優(yōu)先選取。經(jīng)控制變量測試可知，當(dāng)pl=0.04,α=0.2,β=0.5,γ=0.2,δ=0.1,ε=0.2 時(shí)，解質(zhì)量較好。

算法4 輕貨單元選擇算法

輸入：搜索系數(shù)ω，當(dāng)前布局空間r ，空間集合R，貨物集合C，輕貨集合

輸出：輕貨單元b0。

步驟1 生成一步解。對于當(dāng)前布局空間r ，根據(jù)評估函數(shù)從集合中選出評估值排名前ω 的輕貨單元（不同放置方式有不同的評估值，若同一貨物單元有兩種放置方式的評估值皆排名前ω，則該貨物單元將被選取兩次），分別放在r 錨角處，得到ω 個(gè)一步解（見圖6），更新集合。

步驟2 生成二步解。從集合R 中選出每個(gè)一步解下一步驟的布局空間r′ ，再次從集合Bˉ中選出評估值排名前ω 的輕貨單元，分別放在r′錨角處，得到ω2個(gè)二步解（見圖6），更新集合。

步驟3 生成完整解。從集合R 中選出每個(gè)二步解下一步驟的布局空間r′ ，僅從集合Bˉ中選出一個(gè)輕貨單元b，若不能找到符合條件的b，則標(biāo)記r′，使之在下次集合更新前不再被選取；若能找到，則將其放在r′ 錨角處，更新集合并刪去所有空間標(biāo)記。隨后檢查空間集合中是否仍有未標(biāo)記的空間，若有則繼續(xù)判斷貨物集合中是否有貨物剩余，是則重復(fù)步驟3，否則均轉(zhuǎn)步驟4。

步驟4 輸出ω2個(gè)完整解，找到其中最優(yōu)者對應(yīng)的一步解，返回實(shí)現(xiàn)該一步解的輕貨單元b0（見圖6），將其作為當(dāng)前階段放入的輕貨單元。

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

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

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

輸入：空間集合R，貨物集合C，計(jì)算時(shí)間Sec；輸出：裝載方案sbest。

步驟1 貨物分類。調(diào)用算法1，輸入集合C 和重貨占比系數(shù)λ，得到重貨集合K 。

步驟2 初始化。調(diào)用算法2，輸入集合K 和重貨單元數(shù)，得到重貨單元集合B；調(diào)用算法3，輸入集合C 和B，得到中心骨架候選集合SK 和各組合對應(yīng)輕貨單元集合的集合----TB；設(shè)定搜索系數(shù)ω，集合R 中初始布局空間為集裝箱本身。

步驟3 構(gòu)建骨架。判斷集合SK 中是否還有重貨單元組合，是則從中取出一個(gè)組合cp，同時(shí)分別復(fù)制集合R 和C 到集合R′和C′，用組合cp 在集合R′中構(gòu)建中心骨架；否則轉(zhuǎn)步驟6。

步驟4 選擇輕貨單元。中心骨架構(gòu)建完畢后，從集合R′中選出布局空間r，調(diào)用算法4，輸入系數(shù)ω，空間r ，集合R′和C′ ，以及集合中cp 對應(yīng)的輕貨單元集合，搜索當(dāng)前階段放入的輕貨單元b0。若不能找到符合條件的b0，則標(biāo)記r ，使之在下次集合更新前不再被選?。蝗裟苷业?，則將b0放到r 錨角處，更新集合R′,C′和，刪去所有空間標(biāo)記。隨后檢查集合R′中是否仍有未標(biāo)記的空間，是則轉(zhuǎn)步驟5，否則轉(zhuǎn)步驟3。

步驟5 生成裝載方案。判斷集合C′中是否有輕貨剩余，是則轉(zhuǎn)步驟4，否則輸出一個(gè)裝載方案s。檢查s是否滿足負(fù)載平衡約束，是則與至今找到的最好方案進(jìn)行比較，將較好者記為sbest；否則將組合cp 放入負(fù)載失衡方案集合Sˉ中。隨后判斷是否遍歷完所有組合，是則轉(zhuǎn)步驟6，否則轉(zhuǎn)步驟3。

步驟6 時(shí)間判斷。判斷時(shí)間是否剩余，是則令ω=，轉(zhuǎn)步驟3，移動(dòng)重貨單元，重新構(gòu)建集合Sˉ中方案的中心骨架；否則轉(zhuǎn)步驟7。

步驟7 返回規(guī)定時(shí)間內(nèi)最優(yōu)方案sbest。

4 算例分析

測試電腦處理器為Intel?Core i5-7600 CPU，3.5GHz，內(nèi)存8 GB，系統(tǒng)Windows10，代碼以Java實(shí)現(xiàn)，并用Eclipse Neon 3編譯。

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

Bischoff和Ratcliff[13]提出一套集裝箱裝載算法的測試算例，包含貨物種類由1 到100 共16 組（BR0～15），每組100 個(gè)算例，被公認(rèn)為集裝箱裝載算法的標(biāo)準(zhǔn)算例。由于這套算例中沒有考慮貨物重量，Ramos 等人[2]在標(biāo)準(zhǔn)算例基礎(chǔ)上，設(shè)定貨物密度區(qū)間為(ρmin,ρmax)，其中ρmin=0.5ρc,ρmax=(ρc-ρmin)/E[x]+ρmin(ρc=QT/(g ?VT)，即待裝貨物平均密度，E[x]為貝塔分布期望），并按貝塔分布f(x,2,5) 得到貨物密度。本文利用同樣的數(shù)據(jù)進(jìn)行測試，并與三個(gè)代表性算法進(jìn)行比較，分別是等人[14]提出的最大空間算法（MS），Gon?alves和Resende[15]提出的偏隨機(jī)密鑰遺傳算法（BRK）以及Ramos等人[2]提出的帶靜態(tài)穩(wěn)定的多種群偏隨機(jī)密鑰遺傳算法（MPBRK）。測試集裝箱選用20 英尺通用集裝箱(L=5.870 m,W=2.330 m,H=2.200 m)，為契合混合裝載，去掉貨物種類為1的算例，其余1 500個(gè)算例各計(jì)算100 s，同組100個(gè)算例平均結(jié)果見表1。

“Vol.”表示集裝箱容積利用率，該方面本文算法略低于其他算法，較最優(yōu)者低1.57%。這是因?yàn)楸疚乃惴榱吮ＷC每一次都能選到最合適的貨物單元，以樹形檢索為解空間搜索內(nèi)核，在有限的時(shí)間內(nèi)，與以遺傳算法為搜索內(nèi)核的算法相比搜索能力較弱?！癠nb.”表示負(fù)載失衡的算例數(shù)，該方面本文算法能夠100%實(shí)現(xiàn)測試算例負(fù)載平衡，但其余最優(yōu)者也達(dá)99.33%，差距較小。計(jì)算可知按f(x,2,5)得到的貨物密度期望近似等于ρc，且方差僅為0.026，這樣的貨物產(chǎn)生的負(fù)載相對均勻，稍加處理即可實(shí)現(xiàn)負(fù)載平衡。標(biāo)準(zhǔn)算例結(jié)果可以說明本文算法具有一定的普適性，但不能證明實(shí)現(xiàn)輕重貨物混合平衡裝載的可行性，因此還需使用輕重貨物算例進(jìn)行測試。

4.2 輕重貨物算例

以標(biāo)準(zhǔn)算例為基礎(chǔ)，增大貨物密度區(qū)間，令ρmin=0.05ρc，將密度下限固定在一個(gè)較小值；ρmax=Q/g((n-i0)?m0)（n 即貨物類數(shù)，i0表示已被賦予重量的貨物類數(shù)，m0表示當(dāng)前被賦予重量的貨物個(gè)數(shù)），密度上限保持當(dāng)前載重允許最大值。同時(shí)改貝塔分布為f(x,0.075,0.075)，生成較輕較重貨物期望增大，且方差比標(biāo)準(zhǔn)算例大8.5 倍，圖7 可見兩貝塔分布差異。以此生成15組共1 500個(gè)輕重貨物算例，每個(gè)算例計(jì)算100 s，同組100個(gè)算例平均結(jié)果見表2。

表1 標(biāo)準(zhǔn)算例結(jié)果

從結(jié)果可看出，貨物屬性的改變對裝載結(jié)果產(chǎn)生了巨大的影響。在集裝箱容積利用率方面，各算法均有少量下滑，但表現(xiàn)較穩(wěn)定；在負(fù)載平衡方面變化顯著，本文算法平均滿足率達(dá)96.07%，比其余最優(yōu)者高22.40%。

圖7 貝塔分布概率密度函數(shù)

5 結(jié)束語

（1）用負(fù)載平衡函數(shù)描述貨物總重心位置與貨物最大容許重量之間的關(guān)系，建立集裝箱輕重貨物混合平衡裝載模型；將待裝貨物分類組成輕重貨物單元，用重貨物單元構(gòu)建中心骨架固定總重心位置，用評估函數(shù)選取輕貨單元得到完整裝載方案，設(shè)計(jì)集裝箱輕重貨物混合平衡裝載算法。

表2 輕重貨物算例結(jié)果

（2）算例測試表明，本文模型和算法能夠在保證集裝箱容積平均利用率不低于90%的同時(shí)使負(fù)載平衡約束平均滿足率達(dá)96.07%以上，是目前實(shí)現(xiàn)輕重貨物混合平衡裝載較為有效的方法。

（3）現(xiàn)階段集裝箱裝載類問題的目標(biāo)函數(shù)均為最大化集裝箱容積利用率，未來可結(jié)合裝運(yùn)實(shí)際，將集裝箱載重量利用率等融入其中，或提出新的指標(biāo)作為目標(biāo)函數(shù)。