面向不規則集裝箱的貨物裝載優化問題研究

張長勇 翟一鳴

(中國民航大學電子信息與自動化學院 天津 300300)

0 引 言

隨著現代物流的飛速發展，航空貨運已進入蓬勃發展的階段。集裝箱裝載是航空貨物運輸中的重要環節，然而由于飛機機艙的特殊形狀，除了用于大型飛機的貨艙中的標準集裝箱之外，通常要使用尺寸、體積和形狀不同的非標準集裝箱。目前常用的航空集裝箱主要有AMF、AKE、AAU集裝箱，它們都是非長方體的集裝箱。因此，研究實用且高效的不規則集裝箱的裝載優化算法是非常必要的。

航空貨物裝箱問題本質上屬于三維裝箱問題，是NP問題。求解算法可以分為構造性算法和鄰域搜索算法。

構造性算法用來生成初始裝載布局方案，主要方法有極點法、砌墻法、中心骨架法、組合塊、優條與優層、穴度法、三空間分割法。Crainic等[1]通過定義橫縱交叉點生成關鍵點來放置貨物；George等[2]首次提出了砌墻法，將三維裝箱問題簡化為一維問題進行求解；雷定猷等[3]根據實際裝載經驗，提出了先碼放核心貨物以構造骨架，再放置其他非核心的貨物的中心骨架法；張德富等[4]將貨物組合形成復合塊，根據塊選擇算法確定每一步使用的塊，再以固定方式裝載塊；劉勝等[5]采用箱子、優條、優層的順序得到裝載方案；何琨等[6]提出了每步選擇一個貨物將其放在箱子的某個位置，使其占用空間最小的穴度算法；張鈞等[7]采用三叉樹結構來表示空間的布局情況，通過空間搜索、分割與合并對貨物進行裝載。

裝箱問題的計算結果是不可量化的，利用鄰域搜索算法求解問題的近似最優解，主要有蟻群[8]、遺傳[9-10]、樹搜索[11-14]、模擬退火[15]、粒子群[16]、多元優化法[17]。利用構造性算法形成初始裝載布局方案，用鄰域搜索算法從多個可行解中選出目標函數最優的方案作為最終方案。為提高算法的全局搜索能力，可以兩兩相結合或者是對算法做出一些改進。構造性算法在結合鄰域搜索算法后，其性能可得到些許的改進。

目前國內外學者研究的大多是規則的長方體箱子，而航空集裝箱大都是不規則、非長方體的集裝箱，為此需根據實際工程要求建立數學模型，研究相應算法來完成貨物裝載。本文研究航空貨運背景下不規則集裝箱的貨物裝載問題，在滿足實際裝載約束的條件下，提出一種將擬人與改進的遺傳相結合的混合遺傳算法。首先由擬人算法得到初始裝載方案，然后通過改進的遺傳算法從多組可行性方案中找到最優裝箱方案。基于真實航空貨物數據的結果分析比較，驗證了該算法在空間利用率、載重利用率及求解時間上均優于傳統遺傳算法。最后，利用GUI設計了裝箱軟件，以方便指導實際應用中的裝箱操作。

1 問題描述

雖然本文出發點是為不規則的航空集裝箱提供裝載布局方案，但目前航空集裝箱類型較多，規格也不同，難以建立一套通用模型以適合所有不規則集裝箱。針對目前廣泛應用于航空運輸的AKE集裝箱展開研究，適載機型有747、777等。外形尺寸如圖1所示。

圖1 AKE集裝箱外形尺寸

1.1 約束條件

不規則集裝箱的貨物裝載問題可以描述為：給定AKE集裝箱和一定數量的待裝載航空貨物B={b1,b2,…,bn}，在滿足實際裝載約束的前提下，得到使AKE箱空間利用率或者載重利用率最大的裝載布局方案。考慮航空貨物裝載過程中的現實約束如下：

(1) 裝載順序約束：考慮航空貨物裝箱過程中的順序裝載，以適應實時裝箱。

(2) 體積、質量約束：貨物的總體積、質量不超過集裝箱的最大裝載體積、最大承載力。

(3) 重心約束：為保證垛形的穩定性，集裝箱重心需要在合理的范圍內。

(4) 不重疊約束：貨物之間不能重疊。

(5) 承重約束：裝載過程中，有必要充分考慮貨物的載重能力，以免因過度擠壓而損壞貨物。

1.2 假設條件

由于實際裝載過程中貨物裝箱問題的復雜性，為便于進行研究，做以下假設：

(1) 航空貨物形狀各異，考慮到大多復雜形狀可拆分成幾個小的長方體，故簡化貨物均為長方體。

(2) 貨物密度均勻，其重心即為幾何中心。

(3) 集裝箱中貨物的碼放位置不受區域的限制。

(4) 貨物因擠壓產生的變形可忽略不計。

2 數學模型

2.1 符號說明

空間坐標系是通過將AKE集裝箱的底面作為xy平面，垂直底面向上作為z軸，以其左、后、下角為原點建立的。以下是符號說明：

ηi為0/1變量，若貨物i裝入集裝箱中則ηi=1，若未裝入則ηi=0。

α是 0,1 之間的變量，以載重利用率最大為目標時α=0，以空間利用率最大為目標時α=1。

W1、W2、H、D、V、M是AKE集裝箱的長(最大)、長(最小)、寬、高、體積及其最大載重量。

wi、hi、di、vi、mi、[gxi,gyi,gzi]是貨物i的長、寬、高、體積、質量及其重心坐標。

Beari、BLi分別是貨物所承受的重量及其最大承受力。

Bi、Ci是貨物的順序號、碼放序號。

[conx1,conx2]、[cony1,cony2]、[0,conz]分別是x、y、z軸的重心安全區間。

2.2 模型建立

根據上述分析，建立航空貨物堆碼數學模型。式(1)表示優化目標為最大化集裝箱空間利用率、載重利用率；式(2)、式(3)表示貨物的總質量、總體積小于集裝箱的最大承重量、體積；式(4)表示貨物要與集裝箱正交或者平行；式(5)表示貨物需按照當前到來的順序進行裝載；式(6)表示貨物垛形重心在合理的范圍之內；式(7)表示貨物承重約束，即貨物所載全部上層貨物總重量小于它的最大承重量；式(8)表示貨物之間不能重疊。

Bi=Ci

(5)

3 算法設計

求解AKE集裝箱裝載優化問題的混合遺傳算法包括擬人算法和改進的遺傳算法兩部分。利用擬人算法產生初始裝箱方案，然后利用改進的遺傳算法對多組可行方案尋優，得到目標函數最大的裝載布局方案。其流程如圖2所示。

圖2 算法裝載流程

3.1 基于擬人的構造性裝箱算法

面對復雜的不規則集裝箱裝載問題，為使貨物碼放過程更加靈活，采用可放置點構建、規則設定、排序、參考線引入的擬人算法對貨物進行裝載，該算法的優點在于它不需要貨物垛形滿足特定的結構。將貨物bi放置在點(xi,yi,zi)，會新增三個可放置點(xi+wi,yi,zi)、(xi,yi+hi,zi)、(xi,yi,zi+di)，如圖3(a)所示。得到的可放置點通過設定規則并賦予一定的權重，對其進行排序。按照排好序的可放置點去判斷貨物bi是否滿足裝載條件，裝載條件為該貨物bi不能與其他貨物以及集裝箱相交，且滿足x+wi≤Lx，z+di≤Lz，即不超過水平、垂直參考線(參考線如圖3(b)和圖3(c)所示)。

(a) 可放置點

(b) 水平參考線

(c) 垂直參考線圖3 可放置點及參考線

規則及權重設定如表1所示，設定依據如下：規則1使貨物從底層開始進行有序放置；規則2保證貨物之間的接觸率，使得垛形更加穩定；規則3為待裝載貨物提供更大的裝載空間；規則4將放置的貨物盡可能靠邊，以裝入更多的貨物。根據對裝載效果的影響，分別賦予權重0.5、0.2、0.2、0.1。為防止過擬合，添加了正則項以確保規則的合理性。表格規則可簡化為：

式中：Q0是可放置點總數；qi是根據此規則i在總數中的排序個數；0.3μ為正則化項；r為每個可放置點的評價值，根據r值對可放置點進行排序。每次完成當前貨物裝載，同步更新可放置點序列和剩余貨物信息。

表1 規則及權重

擬人算法步驟如下：

Step1輸入AKE集裝箱的尺寸、體積、最大載重量，以及待裝載的貨物序列B=(b1,b2,…,bn)。

Step2設定集裝箱的左后下角為初始可放置點(0,0,0)，初始化水平、垂直參考線Lx=Lz=0。

Step3根據所設定規則對可放置點排序，按照排好序的可放置點依次檢測貨物。

Step4判斷當前可放置點是否滿足裝載條件。若滿足，裝載當前貨物，刪除已用的可放置點；若不滿足，返回Step 3。

Step5在所有的可放置點都不滿足裝載條件時，提高參考線。若Lx

Step6更新可放置點序列及剩余貨物信息。

Step7判斷貨物是否裝載完畢，若是，則輸出裝載布局方案；否則，返回Step 3。

3.2 改進的遺傳算法

遺傳算法在解決NP難題時具有快速隨機的全局搜索能力，但收斂速度和局部搜索效果欠佳。為解決傳統的遺傳算法容易過早收斂的問題，加入適應度尺度變換、罰函數、最優解保存策略來對其進行改進。

3.2.1編碼與解碼

編碼時，貨物的每種裝箱方案對應符號串S=(S1,S2,…,Si,…,Sn)，其長度為n，S1-Sn代表貨物放置狀態，每個貨物有6種放置狀態，分別用整數1、2、3、4、5、6表示；解碼時，第i個待碼放的貨物按照基因Si代表的狀態進行放置。

3.2.2適應度尺度變換與罰函數

適應度用來評價各裝箱方案的好壞。把目標函數設為適應度函數，為提高個體間的競爭性，防止算法過早收斂，對適應度進行線性尺度變換。式(10)為原適應度函數，式(11)為變換后的適應度函數。

F1=aF+b

(11)

式中：a、b為變換系數；Fmin為F的最小值；Favg為F的平均值。

綜合考慮垛形重心約束、不重疊約束、承重約束，對違反條件的個體給予相應的懲罰，使其被遺傳到下一代種群的機會降低。式(12)為加入懲罰項的適應度函數；式(13)為垛形重心罰函數；式(14)為貨物不重疊罰函數；式(15)為貨物承重罰函數。

式中：H為貨物裝載的罰函數；k為懲罰因子。

H9=Beari-BLi

(15)

3.2.3遺傳操作過程

對個體進行遺傳操作，包括選擇、交叉與變異。

選擇：基于對個體適應度的評估，利用輪盤賭對個體進行選擇。

交叉：決定了算法的全局搜索力，采用雙點交叉法，通過隨機產生兩個交叉點進行基因交換。

變異：決定了算法的局部搜索力，利用順序逆轉變異，先在父代選擇兩個變異點，然后以相反的順序在兩個點之間對基因進行重新排列，以維持種群的多樣性。

因為上述的操作有很大的隨機性，可能會破壞適應度較好的個體。為使較好的個體盡可能多地遺傳到下一代，采用最優解保存策略。即在每一代的進化中，前10%的個體被保留而不進行交叉、變異，并被直接復制到下一代種群中。

4 實例驗證

在型號為Intel(R) Core(TM) i5- 7200U CPU 2.50 GHz的計算機上進行實驗，運行環境Visual Studio 2010。

遺傳算法的參數為：

{種群規模,交叉,變異概率,終止條件,測試次數}=

{50，0.6，0.1，200，10}

AKE集裝箱參數如下：

{W1,W2H,D,M}=

{201 cm，156 cm，154 cm，163 cm，1 488 kg}

為驗證混合遺傳算法對不同種類貨物的適應性與有效性，從某航空公司獲取真實貨物數據進行驗證。本次實驗采集了三組不同批次的貨物數據，先后輸入混合遺傳算法中進行實驗。限于篇幅，表2僅列出部分貨物信息。

表2 航空貨物信息

由于研究的是不規則航空集裝箱的貨物裝載問題，且針對的是真實貨物數據，暫未有可以直接使用作為比較的對象，所以本文算法僅與傳統遺傳算法產生的裝載方案進行比較。其中，傳統遺傳算法由擬人結合改進前的遺傳算法得到。兩種算法獨立運行20次，對比結果見表3。可以看出，混合遺傳算法所產生的方案不僅有著較高的空間和載重利用率，貨物碼放更合理科學，而且其求解時間較短。究其根源，混合遺傳算法加入適應度尺度變換、最優解保存策略之后，算法的局部、全局優化能力得以提高。對第三組貨物數據得到的仿真結果做統計，得到適應度函數隨迭代次數發生變化的對比效果圖如圖4所示，混合遺傳算法迭代到77代得到全局最優解，而傳統遺傳算法迭代到149代才能獲得全局最優解，且性能較差。結果表明混合遺傳算法可在較短的時間收斂獲得全局最優解，搜索速度明顯優于傳統遺傳算法，說明混合遺傳算法具有更好的收斂性。

表3 兩種算法對比結果

圖4 優化性能比較

圖5所示為混合遺傳算法得到的裝載效果圖，圖5(a)、圖5(b)、圖5(c)分別為三組貨物數據的裝箱方案。由圖5可見，航空貨物垛形形狀較為規則，滿足不規則集裝箱的空間約束。貨物之間的接觸面積較大，擺放緊湊，滿足了貨物裝載過程中垛形穩定的要求。

(a) 第一組

(b) 第二組

(c) 第三組圖5 裝載效果圖

因為在實際的貨物裝箱過程中，既要給出直觀的裝載效果圖，又要給出待裝載貨物的基本信息、具體碼放位置，才能給人工碼放、機器碼垛提供直接的參考，為實時裝載決策提供基礎。故使用MATLAB 2014中的GUI(圖形用戶界面)設計一個AKE集裝箱裝載布局軟件，在進行裝載前設置算法參數，裝載完畢后得到裝載效果圖和貨物碼放位置表。裝載效果圖能直觀地反映貨物在箱內的碼放位置，評估貨物布局方案的可行性，并據此判斷方案的好壞；貨物碼放位置表給出了貨物在箱內的具體空間位置，反映不同貨物的裝箱情況。軟件的輸入界面、輸出界面如圖6所示。

(a) 輸入界面

(b) 輸出界面圖6 裝載軟件界面

5 結 語

針對不規則集裝箱的貨物裝載優化問題，在考慮實際裝載過程中體積、質量、重心、不重疊等約束的前提下，提出一種將擬人算法與改進的遺傳相結合的混合遺傳算法。基于多組不同批次航空貨物數據的結果分析比較，證明了混合遺傳算法對強異構型貨物有著較好的裝載布局效果，能夠將貨物按照其裝載順序合理地裝載至集裝箱中，并提高集裝箱的空間利用率和載重利用率，縮短程序的運行時間，為研究不規則集裝箱裝載優化問題提供了解決思路。同時，設計一款裝箱軟件，以證實算法的實用性與有效性。