面向不規(guī)則集裝箱的貨物裝載優(yōu)化問題研究

張長(zhǎng)勇 翟一鳴

(中國(guó)民航大學(xué)電子信息與自動(dòng)化學(xué)院 天津 300300)

0 引 言

隨著現(xiàn)代物流的飛速發(fā)展，航空貨運(yùn)已進(jìn)入蓬勃發(fā)展的階段。集裝箱裝載是航空貨物運(yùn)輸中的重要環(huán)節(jié)，然而由于飛機(jī)機(jī)艙的特殊形狀，除了用于大型飛機(jī)的貨艙中的標(biāo)準(zhǔn)集裝箱之外，通常要使用尺寸、體積和形狀不同的非標(biāo)準(zhǔn)集裝箱。目前常用的航空集裝箱主要有AMF、AKE、AAU集裝箱，它們都是非長(zhǎng)方體的集裝箱。因此，研究實(shí)用且高效的不規(guī)則集裝箱的裝載優(yōu)化算法是非常必要的。

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

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

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

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

1 問題描述

雖然本文出發(fā)點(diǎn)是為不規(guī)則的航空集裝箱提供裝載布局方案，但目前航空集裝箱類型較多，規(guī)格也不同，難以建立一套通用模型以適合所有不規(guī)則集裝箱。針對(duì)目前廣泛應(yīng)用于航空運(yùn)輸?shù)腁KE集裝箱展開研究，適載機(jī)型有747、777等。外形尺寸如圖1所示。

圖1 AKE集裝箱外形尺寸

1.1 約束條件

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

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

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

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

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

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

1.2 假設(shè)條件

由于實(shí)際裝載過程中貨物裝箱問題的復(fù)雜性，為便于進(jìn)行研究，做以下假設(shè)：

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

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

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

(4) 貨物因擠壓產(chǎn)生的變形可忽略不計(jì)。

2 數(shù)學(xué)模型

2.1 符號(hào)說明

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

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

α是 0,1 之間的變量，以載重利用率最大為目標(biāo)時(shí)α=0，以空間利用率最大為目標(biāo)時(shí)α=1。

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

wi、hi、di、vi、mi、[gxi,gyi,gzi]是貨物i的長(zhǎng)、寬、高、體積、質(zhì)量及其重心坐標(biāo)。

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

Bi、Ci是貨物的順序號(hào)、碼放序號(hào)。

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

2.2 模型建立

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

Bi=Ci

(5)

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

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

圖2 算法裝載流程

3.1 基于擬人的構(gòu)造性裝箱算法

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

(a) 可放置點(diǎn)

(b) 水平參考線

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

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

式中：Q0是可放置點(diǎn)總數(shù)；qi是根據(jù)此規(guī)則i在總數(shù)中的排序個(gè)數(shù)；0.3μ為正則化項(xiàng)；r為每個(gè)可放置點(diǎn)的評(píng)價(jià)值，根據(jù)r值對(duì)可放置點(diǎn)進(jìn)行排序。每次完成當(dāng)前貨物裝載，同步更新可放置點(diǎn)序列和剩余貨物信息。

表1 規(guī)則及權(quán)重

擬人算法步驟如下：

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

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

Step3根據(jù)所設(shè)定規(guī)則對(duì)可放置點(diǎn)排序，按照排好序的可放置點(diǎn)依次檢測(cè)貨物。

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

Step5在所有的可放置點(diǎn)都不滿足裝載條件時(shí)，提高參考線。若Lx

Step6更新可放置點(diǎn)序列及剩余貨物信息。

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

3.2 改進(jìn)的遺傳算法

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

3.2.1編碼與解碼

編碼時(shí)，貨物的每種裝箱方案對(duì)應(yīng)符號(hào)串S=(S1,S2,…,Si,…,Sn)，其長(zhǎng)度為n，S1-Sn代表貨物放置狀態(tài)，每個(gè)貨物有6種放置狀態(tài)，分別用整數(shù)1、2、3、4、5、6表示；解碼時(shí)，第i個(gè)待碼放的貨物按照基因Si代表的狀態(tài)進(jìn)行放置。

3.2.2適應(yīng)度尺度變換與罰函數(shù)

適應(yīng)度用來評(píng)價(jià)各裝箱方案的好壞。把目標(biāo)函數(shù)設(shè)為適應(yīng)度函數(shù)，為提高個(gè)體間的競(jìng)爭(zhēng)性，防止算法過早收斂，對(duì)適應(yīng)度進(jìn)行線性尺度變換。式(10)為原適應(yīng)度函數(shù)，式(11)為變換后的適應(yīng)度函數(shù)。

F1=aF+b

(11)

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

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

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

H9=Beari-BLi

(15)

3.2.3遺傳操作過程

對(duì)個(gè)體進(jìn)行遺傳操作，包括選擇、交叉與變異。

選擇：基于對(duì)個(gè)體適應(yīng)度的評(píng)估，利用輪盤賭對(duì)個(gè)體進(jìn)行選擇。

交叉：決定了算法的全局搜索力，采用雙點(diǎn)交叉法，通過隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)進(jìn)行基因交換。

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

因?yàn)樯鲜龅牟僮饔泻艽蟮碾S機(jī)性，可能會(huì)破壞適應(yīng)度較好的個(gè)體。為使較好的個(gè)體盡可能多地遺傳到下一代，采用最優(yōu)解保存策略。即在每一代的進(jìn)化中，前10%的個(gè)體被保留而不進(jìn)行交叉、變異，并被直接復(fù)制到下一代種群中。

4 實(shí)例驗(yàn)證

在型號(hào)為Intel(R) Core(TM) i5- 7200U CPU 2.50 GHz的計(jì)算機(jī)上進(jìn)行實(shí)驗(yàn)，運(yùn)行環(huán)境Visual Studio 2010。

遺傳算法的參數(shù)為：

{種群規(guī)模,交叉,變異概率,終止條件,測(cè)試次數(shù)}=

{50，0.6，0.1，200，10}

AKE集裝箱參數(shù)如下：

{W1,W2H,D,M}=

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

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

表2 航空貨物信息

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

表3 兩種算法對(duì)比結(jié)果

圖4 優(yōu)化性能比較

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

(a) 第一組

(b) 第二組

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

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

(a) 輸入界面

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

5 結(jié) 語

針對(duì)不規(guī)則集裝箱的貨物裝載優(yōu)化問題，在考慮實(shí)際裝載過程中體積、質(zhì)量、重心、不重疊等約束的前提下，提出一種將擬人算法與改進(jìn)的遺傳相結(jié)合的混合遺傳算法?；诙嘟M不同批次航空貨物數(shù)據(jù)的結(jié)果分析比較，證明了混合遺傳算法對(duì)強(qiáng)異構(gòu)型貨物有著較好的裝載布局效果，能夠?qū)⒇浳锇凑掌溲b載順序合理地裝載至集裝箱中，并提高集裝箱的空間利用率和載重利用率，縮短程序的運(yùn)行時(shí)間，為研究不規(guī)則集裝箱裝載優(yōu)化問題提供了解決思路。同時(shí)，設(shè)計(jì)一款裝箱軟件，以證實(shí)算法的實(shí)用性與有效性。