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

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

（軍事交通學院，天津 300161）

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

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

（軍事交通學院，天津 300161）

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

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

1 引言

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

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

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

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

2.1 堆碼問題目標函數建立

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

航空集裝板空間利用率函數為：

航空集裝板載重利用率函數為：

航空集裝板重心考察函數為：

因此，綜合航空集裝板空間利用率函數（1）、載重利用率函數（2）以及重心考察函數（3），根據多目標優化的加權系數法，定義本問題目標函數為：

式中，λ、β、γ分別為航空集裝板空間利用率、載重利用率以及重心偏移量的權重系數，均為0-1變量，且λ+β+γ=1。當認為上述三者同等重要時，可令λ=β=γ=1/3。目標函數值越大，則堆碼方案越優。

2.2 堆碼問題約束條件分析

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

航空集裝板屬性約束：

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

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

物資堆碼約束：

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

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

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

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

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

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

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

3.1 物資堆碼順序總原則

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

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

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

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

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

圖3 子空間隊列

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

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

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

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

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

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

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

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

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

物資堆碼策略設計

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

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

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

4 堆碼策略的數學實現及堆碼模型的生成

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

算法與傳統非智能算法相比較，具有運算簡易、搜索過程靈活、搜索能力高以及隱含并行性等優點，因此被廣泛應用于人工生命、自動控制、機器學習、生產調度、機器學習、組合優化等領域。

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

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

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

4.1 自適應算式設計

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

同時，又為了避免某些適應度較大的優良個體之間的交叉概率過小而導致進化過程中根本不產生變化或變化過小，致使整個算法出現“早熟”現象，本文設計的交叉和變異概率的自適應算式如下：

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

4.2 個體的編碼及解碼

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

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

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

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

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

（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。

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

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

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

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

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

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

4.3 評價函數及停止準則

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

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

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

本文以算法迭代到預定的最大次數M后終止，取種群中適應值最大的個體作為最優解。

4.4 自適應遺傳操作過程

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

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

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

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

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

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

5 實例分析

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

圖7 備選航空集裝板型號

圖8 部分待運物資相關數據

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

圖9 平均適應度值與進化代數之間的變化關系

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

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

6 總結

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

［1］魏然.航空物流服務鏈的特征及現狀［J］.物流技術,2008,（1）.

［2］許光濘,肖志勇,俞金壽.應用自適應遺傳算法解決集裝箱裝載問題［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-），男，浙江慈溪人，碩士研究生，研究方向：軍事物流信息系統與技術集成；王愛嘉（1994-），男，河北保定人，碩士研究生，研究方向：軍事物流信息系統與技術集成；石紅霞（1978-），女，河北保定人，講師，研究方向：軍事物流。