航空集裝板組板優化問題的混合遺傳算法

孫世峰，劉永軍，張　俊

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

航空集裝板組板優化問題的混合遺傳算法

孫世峰，劉永軍，張俊

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

在滿足航空集裝板組板優化問題的約束條件下，結合順序及擺放方向的因素，提出了一種混合編碼的遺傳算法，構造了體積利用率和載重利用率共存的多目標適應度函數，并利用AForge.NET開源框架實現了遺傳算法的編程。

航空集裝板；空間搜索；遺傳算法；組板優化

1　引言

目前對于航空集裝板組板主要依靠操作習慣和經驗，組板具有很大的不確定性。若組板超重超限，就必須拆箱重新裝載，增加了組板的時間，直接影響了貨運的效率和成本。

類似于集裝箱裝箱問題，航空集裝板組板優化問題也是一個NP-hard問題［1］，直接利用傳統方法進行求解會因為問題規模不斷增大而產生時間維度過長。遺傳算法（Genetic Algorithm，GA）作為一種模擬自然界遺傳機制和生物進化論而形成的一種過程搜索最優解算法，其基本思想簡單，運行方式和實現步驟規范，具有全局并行搜索、簡單通用、魯棒性強等優點，特別適合求解問題的近似最優解［2］。本文結合航空集裝板實際組板過程中的一些約束條件，提出了應用混合編碼［3］的遺傳算法解決航空集裝板組板優化問題的方法。

2　航空集裝板組板優化問題描述

航空集裝板組板類似于集裝箱裝載問題，根據貨箱的不同分為3類：（1）是物資的規格完全相同，即單一尺寸的物資裝載問題，這類問題被稱為“同類”問題。（2）是物資有不同的規格，這類問題被稱作“強異類”問題。（3）是物資只有少數的幾類，但是每一類的數量較多，這類問題被稱作“弱異類”問題［4］。本文應用一種物資擺放空間位置和其方向一一對應的編碼方法，尤其適合于解決“強異類”問題。文中物資所占空間指“盒組”形式的空間即一個或兩個以上呈立方體形式的空間。

2.1目標函數及約束條件

2.1.1目標函數.記符號Lj，Wj，Hj，Gj，k分別表示航空集裝板的長、寬、高和最大裝載質量、數量。Li，wi，hi，gi，n分別表示物資的長、寬、高和質量、數量。則目標可描述為：

式中μ為0-1的變量，當不考慮載重利用率時，μ= 1；當不考慮體積利用率時，μ=0。

2.1.2約束條件

（1）物資和航空集裝板的數量和種類：物資的數量和種類為本次待運物資數量和種類，航空集裝板數量和種類為航空公司根據待運物資數量、種類和質量而下發給本次貨運任務使用的航空集裝板的數量、種類和載重。

（2）物資的裝載容積：裝載的物資總容積之和不得大于可用之航空集裝板的總可用容積。

（3）物資的裝載質量：單個航空集裝板上的物資總質量之和不得大于單個航空集裝板可承受最大質量。

（4）物資的裝載界限：組裝好的物資界限不得超過航空集裝板的最大外形限制，物資垂直邊界不得超過卡網兜的孔。

（5）物資裝載的方向：所有物資的邊必須平行于航空集裝板的邊。

（6）物資懸空約束：物資不得懸空，物資上下層之間必須完全接觸。

（7）物資的承載能力約束：在裝載過程中，貨物的承載能力由貨物本身的性質和包裝盒的結構航空貨運飛機裝載問題研究決定，貨物碼放時要做到重不壓輕，大不壓小。

（8）物資編組約束：相同大小的物資應當放在一起，方便集裝板組板作業。

（9）貨物的配置位置約束：有些特殊物資不可以側放、倒放，有些特殊物資不能承擔重壓，這些物資必須單獨設定它們的配置位置。

（10）“物資”：均設定為立方體。

2.2裝載策略

2.2.1航空集裝板的空間劃分。先利用占角策略在全部空間的左下角放入“物資組”或者單個物資，之后將航空集裝板的剩余空間劃分為正上方剩余空間M，右方剩余空間R和前方剩余空間L，如圖1所示。

圖1　空間劃分示意圖

2.2.2航空集裝板的空間搜索策略。在空間搜索前將每一種型號的物資編號，記錄其大小，數量，質量，名稱，是否容許側放等信息，放入集合中，稱為物資集合。將每一種型號的航空集裝板編號，記錄其可用面積，限高，數量，質量，名稱，載重等信息，放入集合中，稱為航空集裝板集合。

根據2.2.1航空集裝板的空間劃分，選擇當前物資所占空間作為三叉樹的根節點，劃分出L，M，R三個空間，分別作為根節點的三個子節點，依次搜索L，M，R放入物資，物資所占空間作為三叉樹的新子節點，重復分割搜索空間，直到沒有物資可以放入或者航空集裝板沒有可利用空間為止。

3　問題的遺傳算法

3.1個體的編碼及解碼

結合航空集裝板物資裝載的空間搜索特性，本文選用了基于多參數交叉編碼，排列編碼和實數編碼混合使用的編碼方式。

個體的編碼方法：每種裝載方案對應一個字符串，長度為2n，即S=S1，S2，…，Sn，Sn+1，Sn+2，…，Sn+i，…，S2n。基因S1-S2由排列編碼實現，對以物資總數為限的元素進行排列所得，表示每個物資在物資集合中的位置。基因Sn+i-S2n由實數編碼實現，單個基因對應的數值用一定范圍內的一個實數來表示，表示物資的放置方向編號。放置方向編號規定為：編號為1，則物資的放置方向為Lj// Lj，wj//Wj，hj//Hj；編號為2，則貨物的放置方向為wj//Lj，lj// Wj，hj//Hj；編號為3，則貨物的放置方向為hj//Lj，lj//Wj，wj//Hj；編號為4，則貨物的放置方向為lj//Lj，hj//Wj，wj//Hj；編號為5，則貨物的放置方向為wj//Lj，hj//Wj，lj//Hj；編號為6，則貨物的放置方向為hj//Lj，wj//Wj，lj//Hj。

個體解碼方法：基因S1-Sn和基因Sn+1-S2n之間具有一一對應的關系。比如現有物資A，B，C，D，E各一個，基因Si和S5+i（i∈｛1，2，3，4，5｝）即表示該物資在物資集合中的順序和其放置方向。

3.2適應度函數

遺傳算法通過適應度函數計算每一個個體的適應值來判斷該個體的質量好壞。適應度的值越大，解的質量越好，該個體越有可能保留到子代種群中。在航空集裝板的裝載中，不僅要考慮集裝板的體積利用率，還要考慮其載重利用率。因此，根據處理多目標優化的加權系數法［5］，本文提出的適應度函數同上述目標函數一致。

3.3停止準則

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

3.4遺傳的操作過程

選擇：在選擇算子中選擇Elitism算法［6］，Elitism算法的基本思想是當前群體中適應度最高的個體不參與遺傳算法中的交叉、變異等操作，而是用它來替換交叉、變異等操作給新種群帶來的適應值最低的個體。

交叉：本文采用一種改進的兩點交叉算法。在交叉過程中，［1，2n］間隨機生成兩個整數a1和a2（a1＜a2）確定父代交換的位置。若a2≤n則交叉在兩個父代的［a1，a2］間進行；若a1＞n則交叉在兩個父代的［a1，a2］間進行；若a1≤n，a2＞n，則交叉在兩個父代的［a1，n］，［n+1，a2］間進行。

變異：為了使遺傳算法避免過早收斂而陷入局部最優解中，對遺傳算法采取變異操作。本文的方法是在［n+1，2n］中隨機數作為該染色體的變異位，并隨機生成一個［1，6］的數來替換變異位上的數。

4　航空集裝板組板優化問題的編程實現

本文主要利用Andrew Kirillov開發的AForge.NET開源框架中的進化算法庫（Evolution algorithms library）來完成對遺傳算法的實現。

4.1主程序

主程序是遺傳算法的主要部分，負責實現算法的體系結構。包括創建初始種群，設置迭代次數，適應值比較等功能。

4.2Chromosome類

Chromosome類包括染色體的編碼，創建新的染色體，克隆染色體以及染色體的交叉，變異等操作。在染色體的編碼中，通過對染色體構造函數的重寫，達到混合編碼的目的。

4.3FitnessFunction類

FitnessFunction類包括染色體解碼，適應值的計算。通過對染色體的解碼，確定染色體各個基因對物資擺放空間位置確定的作用，通過構造目標函數，達到適應值計算的目的。

5　小結

本文針對航空集裝板組板優化問題提出了一種基于混合編碼形式的遺傳算法，解決了簡化模型下航空集裝板組板的求解問題。同時利用開源的遺傳算法框架提供了航空集裝板組板優化問題的編程思路，有利于推廣遺傳算法在空間規劃設計中的應用。

［1］周獻中，鄭華利，田衛萍，等.指揮自動化系統輔助決策技術［M］.北京∶國防工業出版社，2012.

［2］邊霞，米良.遺傳算法理論及其應用研究進展［J］.計算機應用研究，2010，27（7）∶2 425-2 434.

［3］余游明，劉玉樹，閻光偉.遺傳算法的編碼理論與應用［J］.計算機工程與應用，2006，42（3）∶86-89.

［4］David Pisinger.Heuristics for the container loading problem［J］. European Journal of Operational Research，2002，141∶382-392.

［5］胡貴強.多目標優化的遺傳算法及其實現［J］.重慶文理學院學報，2008，27（5）∶12-15.

［6］王曙霞，朱三元，涂俊英.基于Elitism的改進免疫遺傳算法應用研究［J］.計算機仿真，2010，27（6）∶230-243.

Study on Hybrid Genetic Algorithm to Solve Aviation Pallet-building Optimization Problem

Sun Shifeng，Liu Yongjun，Zhang Jun
（Military Transportation Academy， Tianjin 300161， China）

In this paper， upon the precondition of satisfying the constraints in the aviation pallet-building optimization problem， and inconnection with the sequential and orientation considerations， we proposed a hybrid coding based genetic algorithm， established thesuitability function aimed at both bulk utilization and load utilization， and at the end， used the AForge.NET open- source framework toprogram the genetic algorithm proposed in this paper.

aviation pallet； spatial search； genetic algorithm； pallet-building optimization

TP18；F562

A

1005-152X（2016）03-0174-03

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

2016-02-19

國家自然科學基金資助項目（70371186）

孫世峰（1993-），男，新疆烏魯木齊人，研究方向：軍事物流；劉永軍（1971-），男，湖北鐘祥人，博士，研究方向：物流與供應鏈管理；張俊（1991-），男，浙江慈溪人，碩士研究生，研究方向：軍事物流信息系統技術集成。