李 欣，張 俊,王愛嘉，石紅霞

（軍事交通學(xué)院，天津 300161）

航空物流運輸物資組板堆碼模型生成

李 欣，張 俊,王愛嘉，石紅霞

（軍事交通學(xué)院，天津 300161）

以航空轉(zhuǎn)運物資集裝為背景，針對航空集裝板物資堆碼（組板）問題，運用空間分解與組合思想對堆碼策略進行設(shè)計，利用自適應(yīng)遺傳算法完成堆碼策略的數(shù)學(xué)實現(xiàn)和堆碼模型的生成，并通過實例進行驗證，為航運物資集裝輔助決策系統(tǒng)和自動組板系統(tǒng)的研發(fā)提供技術(shù)支撐。

航空物流；物資組板；堆碼策略；堆碼模型

1 引言

航空物流是以航空運輸為主要運輸形式，借助現(xiàn)代信息技術(shù)，連接供給主體和需求主體，使原材料、產(chǎn)成品及相關(guān)信息從起點至終點有效流動的全過程。它將運輸、倉儲、裝卸、加工、整理、配送、信息等方面進行有機結(jié)合，形成完整的服務(wù)供應(yīng)鏈，為用戶提供多功能、一體化的綜合性服務(wù)［1］。其快速、高效、機動的特點，使其在戰(zhàn)略投送、應(yīng)急物資轉(zhuǎn)運、急件運輸?shù)阮I(lǐng)域得到越來越廣泛的應(yīng)用。

航空貨物運輸主要采用全貨機、客機或客貨機三種運輸工具，使用全貨機和客貨機轉(zhuǎn)運物資時，一般都要使用航空集裝器集裝物資，如何將物資合理地集裝碼放到航空集裝器上，是影響航空物流作業(yè)效率和生產(chǎn)效益的關(guān)鍵要素，也是航空貨運處理的重要作業(yè)環(huán)節(jié)。目前，航運物資集裝主要還是依靠人工經(jīng)驗作業(yè)，物資碼放隨意性較大、工作過程忙亂、勞動強度高，尤其在軍事物流、應(yīng)急物流中轉(zhuǎn)運大批量物資時，這一問題更加突出。本文以航空集裝板物資集裝為例，研究物資堆碼（組板）問題，擬建立物資自動堆碼模型，為航運物資集裝輔助決策系統(tǒng)和自動組板系統(tǒng)的研發(fā)奠定基礎(chǔ)。

2 航運物資組板堆碼問題描述

航運物資組板堆碼問題可簡化描述為：在一定約束條件下，研究待運物資如何在航空集裝板上進行科學(xué)、合理、規(guī)范的堆碼，使航空集裝板空間、載重利用率最大，堆碼物資重心偏移量最小，最終確定所需各類航空集裝板數(shù)量及各航空集裝板上物資的堆碼模型。

2.1 堆碼問題目標(biāo)函數(shù)建立

記符號li、wi、hi、gi、vi分別表示待運物資的長、寬、高、重量和體積；Lj、Wj、hj、Gj、Vj分別表示航空集裝板 j（j=1,2,…,m）的長、寬、高、最大載重和最大裝載容積；xi、yi分別表示待運物資i的重心位置沿航空集裝板長度方向和寬度方向距離航空集裝板中心軸的偏差量。

航空集裝板空間利用率函數(shù)為：

航空集裝板載重利用率函數(shù)為：

航空集裝板重心考察函數(shù)為：

因此，綜合航空集裝板空間利用率函數(shù)（1）、載重利用率函數(shù)（2）以及重心考察函數(shù)（3），根據(jù)多目標(biāo)優(yōu)化的加權(quán)系數(shù)法，定義本問題目標(biāo)函數(shù)為：

式中，λ、β、γ分別為航空集裝板空間利用率、載重利用率以及重心偏移量的權(quán)重系數(shù)，均為0-1變量，且λ+β+γ=1。當(dāng)認(rèn)為上述三者同等重要時，可令λ=β=γ=1/3。目標(biāo)函數(shù)值越大，則堆碼方案越優(yōu)。

2.2 堆碼問題約束條件分析

本問題的約束條件可分為兩大類：第一大類為航空集裝板的屬性約束，是指與航空集裝板裝載空間和最大載重相關(guān)的約束條件，可分為航空集裝板空間約束和載重約束；第二大類為物資堆碼約束，是指為滿足航空運輸要求，物資堆碼過程必須滿足的約束條件，可分為物資碼放位置約束、物資碼放方向約束、物資堆碼順序約束以及物資重心約束。

航空集裝板屬性約束：

（1）航空集裝板空間約束：各塊航空集裝板上物資總?cè)莘e不得大于航空集裝板的最大裝載容積。

（2）航空集裝板載重約束：各塊航空集裝板上物資的總重量不得超過航空集裝板的最大載重。

物資堆碼約束：

（1）物資碼放位置約束：物資邊界不得超過航空集裝板裝載空間限制，并且上層物資懸空部分不得超過其體積的1/3。

（2）物資碼放方向約束：部分物資不可側(cè)放或倒置，必須對這些物資進行碼放方向約束。

（3）物資堆碼順序約束：物資堆碼的順序應(yīng)該遵循從大到小、從重到輕的順序，做到大不壓小，重不壓輕。

（4）物資堆碼重心約束：物資堆碼后，應(yīng)該使整體的重心位于航空集裝板中心或其附近允許的范圍內(nèi)。

3 基于空間分解和組合思想的堆碼策略設(shè)計

為方便起見，將航空集裝板裝載空間近似看作為長方體，以航空集裝板一角為坐標(biāo)原點建立三維直角坐標(biāo)系，以寬度方向作為x軸，以長度方向作為y軸，以高度方向作為z軸，如圖1所示。

圖1 航空集裝板三維裝載空間示意圖

3.1 物資堆碼順序總原則

在航空集裝板裝載空間內(nèi)進行物資堆碼遵循以下原則：（1）依次沿左側(cè)至右側(cè)方向（即y軸方向）放置每一行；（2）然后沿從后往前方向（即x軸方向）放置每一列；（3）最后沿從下到上方向（即z軸方向）放置每一層。

3.2 航空集裝板三維裝載空間分解和組合

待運物資在航空集裝板裝載空間內(nèi)平行于三維直角坐標(biāo)系各軸放置，當(dāng)?shù)谝粋€物資或物資組利用“占角原則”放入航空集裝板裝載空間后，該航空集裝板裝載空間被分解為右空間R、前空間L、上空間M這3個空間（除自身所占用空間外），如圖2所示。被劃分后的空間在子空間隊列中排隊等待，每次去除子空間隊列中的一個元素作為當(dāng)前的填充空間，按照后空間、前空間、上空間的順序進行堆碼作業(yè)，子空間隊列如圖3所示。

同理，每個子空間進行物資堆碼的過程中，在擺放物資后同樣被分解為3個子空間。這時，我們把原先3個子空間從空間隊列中替換掉。對于不能擺放物資的子空間，則將其改命名為間隙。逐層考慮，當(dāng)間隙滿足以下條件，則間隙與同層剩余空間進行組合：

圖2 航空集裝板三維裝載空間分割示意圖

圖3 子空間隊列

（1）間隙與同層剩余空間左右相鄰，且在同一水平面上，間隙X軸方向厚度（長度）小于等于同層剩余空間X軸方向厚度，則該間隙與同層剩余空間組合。

（2）間隙與同層剩余空間前后相鄰，且在同一水平面，間隙Y軸方向厚度小于等于同層剩余空間Y軸方向厚度，則該間隙與同層剩余空間組合。

（3）同一層中多個間隙相鄰，則令這些間隙組合構(gòu)成長條形空間。

3.3 基于“層”空間分解和組合的“同類”物資堆碼策略設(shè)計

這里的“同類”物資指單一品種、規(guī)格、包裝形式的物資。對“同類”物資在航空集裝板上進行堆碼作業(yè)，空間搜索時以“層”為一個基本搜索單位，按照對“層”空間分解和組合展開，如圖4所示。航空集裝板裝載空間按照待運物資類型規(guī)格劃分為若干層，對每一層物資，改變物資擺放方向，通過2.1所給出的堆碼優(yōu)化問題目標(biāo)函數(shù)考量此堆放方案的優(yōu)劣，逐層考慮，直至航空集裝板剩余裝載空間中無法放入新的物資。

3.4 基于“塊”空間分解和組合的“弱異類”物資堆碼策略設(shè)計

“弱異類”物資指不同品種、規(guī)格、包裝形式的物資，且類別不超過5種。由于“弱異類”物資中同樣存在較多相同品類的物資，因此它的堆碼策略可以借鑒“同類”物資堆碼策略，但因其特性實際操作過程中也有一定差異。

“弱異類”物資堆碼前，首次將待運物資分類排序，將同一品類物資分為一組，同時按照體積、重量以及耐壓程度將各組排序，排序越小，越先堆碼。首先，對排序第一的物資組按“同類”物資堆碼策略進行堆碼，完成堆碼作業(yè)后再對剩余空間搜索時以“塊”為一個基本搜索單元，按照對“塊”空間分解和組合展開，如圖5所示。由于下一組物資內(nèi)部同樣也是“同類”物資，因此這樣的空間分解和組合方法保證了策略的有效性。重復(fù)上述步驟，直至航空集裝板剩余裝載空間中無法放入新的物資。

3.5 基于“三叉樹”空間分解和組合的“強異類”

物資堆碼策略設(shè)計

“強異類”物資指不同品種、規(guī)格、包裝形式的物資，且類別超過5種。這類物資的堆碼相比較前兩類要復(fù)雜的多。本文借鑒“三叉樹”空間分解和組合思想，對“強異類”物資堆碼策略進行設(shè)計，如圖6所示。

將當(dāng)前物資所占空間作為三叉樹的根節(jié)點，根據(jù)上文3.2航空集裝板三維裝載空間對航空集裝板三維裝載空間分解方法，得到R、L、M三個子空間作為三叉樹的子節(jié)點，依次搜索R、L、M三個子空間擺放物資，新物資所占空間作為三叉樹的新根節(jié)點，再次根據(jù)三維裝載空間分解方法得到新根節(jié)點下的三個子節(jié)點，重復(fù)上述步驟，直至航空集裝板剩余裝載空間中無法放入新的物資。

圖4 “同類”物資堆碼策略

4 堆碼策略的數(shù)學(xué)實現(xiàn)及堆碼模型的生成

遺傳算法是一種基于達爾文生物進化論的自然選擇和遺傳學(xué)機理的生物進化過程的計算模擬，是一種通過模擬生物界自然進化過程尋找最優(yōu)解的方法。遺傳

算法與傳統(tǒng)非智能算法相比較，具有運算簡易、搜索過程靈活、搜索能力高以及隱含并行性等優(yōu)點，因此被廣泛應(yīng)用于人工生命、自動控制、機器學(xué)習(xí)、生產(chǎn)調(diào)度、機器學(xué)習(xí)、組合優(yōu)化等領(lǐng)域。

但是，在經(jīng)典遺傳算法中，交叉和變異操作采用固定的概率，不能很好地反映生物種群的進化過程，同時隨著問題規(guī)模的不斷增大，容易產(chǎn)生時間維數(shù)的災(zāi)難問題，不能比較簡便有效地對大規(guī)模的航空轉(zhuǎn)運物資組板堆碼問題進行優(yōu)化求解。本文中采用一種自適應(yīng)遺傳算法，使交叉概率和變異概率隨群體的適應(yīng)度自動改變［2］，使群體中優(yōu)良個體得到有效保護，從而提高了進化速度，是解決航運物資組板堆碼問題行之有效的方法。

圖5 “弱異類”物資堆碼策略

圖6 “強異類”物資堆碼策略

4.1 自適應(yīng)算式設(shè)計

自適應(yīng)遺傳算法中交叉概率Pc、變異概率Pm隨著群體的適應(yīng)度而自動改變。當(dāng)種群個體的適應(yīng)度趨于局部最優(yōu)或者趨于一致時，應(yīng)該使Pc和Pm增加，以跳出局部最優(yōu)；而當(dāng)群體適應(yīng)度較為分散時，應(yīng)該使Pc和Pm減小，以保護優(yōu)良個體的生存。同時，對適應(yīng)度高于群體平均適應(yīng)度的個體，應(yīng)該選擇較小的Pc和Pm，使優(yōu)良個體得到保護，對適應(yīng)度低于群體平均適應(yīng)度的個體，選擇較大的Pc和Pm，以提高新個體產(chǎn)生速度。這種調(diào)節(jié)方法能有效保護優(yōu)良個體，提高算法的搜索效率。

同時，又為了避免某些適應(yīng)度較大的優(yōu)良個體之間的交叉概率過小而導(dǎo)致進化過程中根本不產(chǎn)生變化或變化過小，致使整個算法出現(xiàn)“早熟”現(xiàn)象，本文設(shè)計的交叉和變異概率的自適應(yīng)算式如下：

其中：favg表示每代群體的平均適應(yīng)度值，fmax表示群體中最大的適應(yīng)度值，f'表示要交叉的2個個體中較大的適應(yīng)度值，f表示要變異的個體的適應(yīng)度值，pc1=0.95，pc2=0.6，pm1=0.15，pm2=0.01。

4.2 個體的編碼及解碼

個體的編碼與解碼是將問題的可行解在解空間與遺傳算法所能處理的搜索空間相互轉(zhuǎn)換的過程［3］，它們的實現(xiàn)是遺傳算法應(yīng)用成功與否的關(guān)鍵。

4.2.1 個體編碼方法。編碼是將問題的可行解從解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的操作。正式編碼前，首先對待運物資、航空集裝板、堆碼順序編號以及放置方向進行如下的編碼預(yù)處理：

（1）待運物資編號i=1,2,…,n；

（2）航空集裝板編號j=1,2,…,m；

（3）堆碼順序編號按照自然數(shù)序列規(guī)定待運物資的堆碼順序，同一編號表示對應(yīng)的物資之間無堆碼順序要求；

（4）物資碼放方向編號，定義物資碼放方向編號為1，如果物資碼放方向為li//Li、wi//Wi、hi//Hi；定義編號為2，如果物資的碼放方向為wi//Li、li//Wi、hi//Hi；定義編號為3，如果物資的碼放方向為hi//Li、li//Wi、wi//Hi；定義編號為4，如果物資的碼放方向為li//Li、hi//Wi、wi//Hi；定義編號為5，如果物資的碼放方向為wi//Li、hi//Wi、li//Hi；定義編號為6，如果物資的碼放方向為hi//Li、wi//Wi、li//Hi。

編碼時應(yīng)該考慮物資碼放方向約束、物資堆碼順序約束和航空集裝板的編號，每種堆碼方案對應(yīng)著一個編碼長度為3n（n為待運物資的件數(shù)）的符號串個體

4.2.2 個體解碼方法。解碼是將問題的可行解從遺傳算法所能處理的搜索空間轉(zhuǎn)換還原至解空間的操作，按照編碼的逆過程進行。

（1）基因si、sn+i、s2n+i之間具有一一對應(yīng)關(guān)系，即基因si表示的具有某堆碼順序的物資i按照基因sn+i表示的碼放方向堆碼至基因s2n+i表示的集裝箱中。

（2）si取值不同時，小編號值對應(yīng)物資先堆碼，大編號值對應(yīng)物資后堆碼，而同一取值對應(yīng)的物資之間無堆碼順序要求。

（3）基因sn+i表示的物資碼放方向按照編碼預(yù)處理進行解碼。

（4）物資在航空集裝板上裝載嚴(yán)格按照3.1物資堆碼順序總原則進行。

4.3 評價函數(shù)及停止準(zhǔn)則

遺傳算法在搜索空間進行搜索過程中基本不需要外部的信息，只需要以評價函數(shù)（適應(yīng)度函數(shù)）為依據(jù)，通過個體適應(yīng)值大小評價群體中個體所對應(yīng)堆碼方案的優(yōu)劣。因此，適應(yīng)度函數(shù)的選取就非常重要，將會直接影響到遺傳算法的收斂速度以及能否準(zhǔn)確找到問題的最優(yōu)解。同時，我們通過適應(yīng)度函數(shù)值的大小來評價解的優(yōu)劣，適應(yīng)度值越大，則得到的解越優(yōu)。根據(jù)2.1所述，航空轉(zhuǎn)運物資組板堆碼優(yōu)化不僅要求航空集裝板空間利用率最大，同時還要考慮載重利用率最大以及重心位置等多個因素。本文為保證研究的完整性，將上述三者同時納入考量范圍，因此適應(yīng)度函數(shù)為：

同時，對于違反航空集裝板空間約束、航空集裝板載重約束以及物資堆碼重心約束的個體，在求解其適應(yīng)值的過程中要給予相應(yīng)的“懲罰”以確保符合條件的優(yōu)良個體具有較大的生存機會。第gen代中個體的適應(yīng)值計算如下：

上式中，pengen（q）為物資堆碼“懲罰”函數(shù)；式（9）為物資堆碼總體積懲罰函數(shù)；式（10）為物資堆碼總重量懲罰函數(shù)；式（11）-式（15）為物資堆碼重心懲罰函數(shù)；（xi,yi,zi）為航空集裝板上物資i的重心坐標(biāo)為待運物資在航空集裝板上堆碼后的重心坐標(biāo)且限定范圍分別為區(qū)間邊界值；cgen為懲罰因子；μij為0-1變量，若物資i碼放在航空集裝板 j上，μij=1，否則μij=0。

本文以算法迭代到預(yù)定的最大次數(shù)M后終止，取種群中適應(yīng)值最大的個體作為最優(yōu)解。

4.4 自適應(yīng)遺傳操作過程

在本算法中，對種群中每一個體實行的遺傳操作過程包括復(fù)制操作過程、交叉操作過程和變異操作過程。

（1）復(fù)制操作。在復(fù)制過程中可采用輪盤賭法或者最優(yōu)個體保存法復(fù)制N個個體。

最優(yōu)個體保存法基本思想是：父代種群內(nèi)最優(yōu)個體直接替代子代中最差個體，利用這一方法，能夠保證遺傳算法以1的概率收斂［5］。

（2）交叉操作。交叉操作是指在父代種群中以概率Pc對2個相互配對的個體（染色體）以約定方式相互交換部分基因，從而形成2個新的個體。為了確保物資碼

放方向基因在遺傳操作過程中的有效性，在交叉過程中采取基因s1-sn保持不變，基因sn+1-s3n參與交叉的策略，交叉操作如下所示：

（3）變異操作。為了在遺傳操作過程中保證種群的多樣性，避免算法“早熟”收斂甚至無法尋到全局最優(yōu)解，對種群中個體采取變異操作。變異操作是將個體染色體編碼串中的某些基因以概率Pm用其他的等位基因來替換，從而形成新的個體。對個體變異操作如下：在內(nèi)按照均勻分布隨機產(chǎn)生一個整數(shù)作為基因的變異位，并將該位的基因替換成對應(yīng)物資碼放方向編號間隨機產(chǎn)生的一個編號值；在內(nèi)同樣也按照均勻分布隨機產(chǎn)生一個整數(shù)作為基因的變異位，并將該位的基因替換為對應(yīng)航空集裝板編號間隨機產(chǎn)生的一個編號值。

5 實例分析

某航空貨運站有1 200件物資需要進行航空運輸前的組板作業(yè)，物資在航空集裝板上允許重心范圍為物資碼放方向任意。備選航空集裝板型號如圖7所示，部分待運物資相關(guān)特征數(shù)據(jù)如圖8所示。

圖7 備選航空集裝板型號

圖8 部分待運物資相關(guān)數(shù)據(jù)

應(yīng)用本文提出的自適應(yīng)遺傳算法，群體規(guī)模N=100。最大進化代數(shù)為300。每代種群中個體平均適應(yīng)度值與進化代數(shù)之間的變化關(guān)系如圖9所示。

圖9 平均適應(yīng)度值與進化代數(shù)之間的變化關(guān)系

可見，自適應(yīng)遺傳算法總共迭代了300次，但是在迭代到第189次時便已經(jīng)收斂到全局最優(yōu)點。根據(jù)計算，共需要航空集裝板11塊，其中P6P板5塊，P1P板3塊，PLA板3塊。其中，P6P板型第1塊板物資堆碼模型如圖10所示。

圖10 P6P板型第1塊板物資堆碼模型

6 總結(jié)

本文以航空轉(zhuǎn)運物資集裝為背景，針對航空集裝板物資堆碼（組板）問題，運用空間分解與組合思想對堆碼策略進行設(shè)計，利用自適應(yīng)遺傳算法完成堆碼策略的數(shù)學(xué)實現(xiàn)和堆碼模型的生成，并通過實例進行驗證。本文的研究結(jié)果可以為航運物資集裝輔助決策系統(tǒng)和自動組板系統(tǒng)的研發(fā)提供技術(shù)支撐。

［1］魏然.航空物流服務(wù)鏈的特征及現(xiàn)狀［J］.物流技術(shù),2008,（1）.

［2］許光濘,肖志勇,俞金壽.應(yīng)用自適應(yīng)遺傳算法解決集裝箱裝載問題［J］.控制與決策,2007,（11）：80-85.

［3］Pisinger D.Heuristics for the container loading problem［J］.European J of Operational Research,2002,141（2）：382-392.

［4］Mukhacheva E A,Mukhacheva A S.The rectangular packing problem：Local optimum search methods based on block structure［J］.Automation and Remote Control,2004,65（2）：248-257.

［5］Lipnitskii A A.Use of genetic algorithms for solution of the rectangle packing problem［J］.Cybernetics and Systems Analysis, 2002,38（6）：943-946.

Generation of Pallet Building and Piling Model in Aviation Logistics Transportation

Li Xin,Zhang Jun,Wang Aijia,Shi Hongxia
（Military Transportation Academy, Tianjin 300161, China）

In this paper, against the background of material containerization in airway transportation and in view of the pallet buildingand piling problem in the aviation logistics process, we designed the piling strategy following the principle of space decomposition andcombination, used the adaptive genetic algorithm to realize mathematically the piling strategy and generate the piling model, and at the end,validated the process in connection with an empirical case.

aviation logistics； material pallet building； piling strategy； piling model

F562；F259.2

A

1005-152X（2016）09-0085-06

10.3969/j.issn.1005-152X.2016.09.019

2016-08-09

李欣（1964-），男，天津薊州人，教授，研究方向：軍事物流；張俊（1991-），男，浙江慈溪人，碩士研究生，研究方向：軍事物流信息系統(tǒng)與技術(shù)集成；王愛嘉（1994-），男，河北保定人，碩士研究生，研究方向：軍事物流信息系統(tǒng)與技術(shù)集成；石紅霞（1978-），女，河北保定人，講師，研究方向：軍事物流。