孫世峰，劉永軍，張　俊

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

航空集裝板組板優(yōu)化問(wèn)題的混合遺傳算法

孫世峰，劉永軍，張俊

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

在滿足航空集裝板組板優(yōu)化問(wèn)題的約束條件下，結(jié)合順序及擺放方向的因素，提出了一種混合編碼的遺傳算法，構(gòu)造了體積利用率和載重利用率共存的多目標(biāo)適應(yīng)度函數(shù)，并利用AForge.NET開(kāi)源框架實(shí)現(xiàn)了遺傳算法的編程。

航空集裝板；空間搜索；遺傳算法；組板優(yōu)化

1　引言

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

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

2　航空集裝板組板優(yōu)化問(wèn)題描述

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

2.1目標(biāo)函數(shù)及約束條件

2.1.1目標(biāo)函數(shù).記符號(hào)Lj，Wj，Hj，Gj，k分別表示航空集裝板的長(zhǎng)、寬、高和最大裝載質(zhì)量、數(shù)量。Li，wi，hi，gi，n分別表示物資的長(zhǎng)、寬、高和質(zhì)量、數(shù)量。則目標(biāo)可描述為：

式中μ為0-1的變量，當(dāng)不考慮載重利用率時(shí)，μ= 1；當(dāng)不考慮體積利用率時(shí)，μ=0。

2.1.2約束條件

（1）物資和航空集裝板的數(shù)量和種類：物資的數(shù)量和種類為本次待運(yùn)物資數(shù)量和種類，航空集裝板數(shù)量和種類為航空公司根據(jù)待運(yùn)物資數(shù)量、種類和質(zhì)量而下發(fā)給本次貨運(yùn)任務(wù)使用的航空集裝板的數(shù)量、種類和載重。

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

（3）物資的裝載質(zhì)量：?jiǎn)蝹€(gè)航空集裝板上的物資總質(zhì)量之和不得大于單個(gè)航空集裝板可承受最大質(zhì)量。

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

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

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

（7）物資的承載能力約束：在裝載過(guò)程中，貨物的承載能力由貨物本身的性質(zhì)和包裝盒的結(jié)構(gòu)航空貨運(yùn)飛機(jī)裝載問(wèn)題研究決定，貨物碼放時(shí)要做到重不壓輕，大不壓小。

（8）物資編組約束：相同大小的物資應(yīng)當(dāng)放在一起，方便集裝板組板作業(yè)。

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

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

2.2裝載策略

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

圖1　空間劃分示意圖

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

根據(jù)2.2.1航空集裝板的空間劃分，選擇當(dāng)前物資所占空間作為三叉樹(shù)的根節(jié)點(diǎn)，劃分出L，M，R三個(gè)空間，分別作為根節(jié)點(diǎn)的三個(gè)子節(jié)點(diǎn)，依次搜索L，M，R放入物資，物資所占空間作為三叉樹(shù)的新子節(jié)點(diǎn)，重復(fù)分割搜索空間，直到?jīng)]有物資可以放入或者航空集裝板沒(méi)有可利用空間為止。

3　問(wèn)題的遺傳算法

3.1個(gè)體的編碼及解碼

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

個(gè)體的編碼方法：每種裝載方案對(duì)應(yīng)一個(gè)字符串，長(zhǎng)度為2n，即S=S1，S2，…，Sn，Sn+1，Sn+2，…，Sn+i，…，S2n?；騍1-S2由排列編碼實(shí)現(xiàn)，對(duì)以物資總數(shù)為限的元素進(jìn)行排列所得，表示每個(gè)物資在物資集合中的位置?；騍n+i-S2n由實(shí)數(shù)編碼實(shí)現(xiàn)，單個(gè)基因?qū)?yīng)的數(shù)值用一定范圍內(nèi)的一個(gè)實(shí)數(shù)來(lái)表示，表示物資的放置方向編號(hào)。放置方向編號(hào)規(guī)定為：編號(hào)為1，則物資的放置方向?yàn)長(zhǎng)j// Lj，wj//Wj，hj//Hj；編號(hào)為2，則貨物的放置方向?yàn)閣j//Lj，lj// Wj，hj//Hj；編號(hào)為3，則貨物的放置方向?yàn)閔j//Lj，lj//Wj，wj//Hj；編號(hào)為4，則貨物的放置方向?yàn)閘j//Lj，hj//Wj，wj//Hj；編號(hào)為5，則貨物的放置方向?yàn)閣j//Lj，hj//Wj，lj//Hj；編號(hào)為6，則貨物的放置方向?yàn)閔j//Lj，wj//Wj，lj//Hj。

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

3.2適應(yīng)度函數(shù)

遺傳算法通過(guò)適應(yīng)度函數(shù)計(jì)算每一個(gè)個(gè)體的適應(yīng)值來(lái)判斷該個(gè)體的質(zhì)量好壞。適應(yīng)度的值越大，解的質(zhì)量越好，該個(gè)體越有可能保留到子代種群中。在航空集裝板的裝載中，不僅要考慮集裝板的體積利用率，還要考慮其載重利用率。因此，根據(jù)處理多目標(biāo)優(yōu)化的加權(quán)系數(shù)法［5］，本文提出的適應(yīng)度函數(shù)同上述目標(biāo)函數(shù)一致。

3.3停止準(zhǔn)則

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

3.4遺傳的操作過(guò)程

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

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

變異：為了使遺傳算法避免過(guò)早收斂而陷入局部最優(yōu)解中，對(duì)遺傳算法采取變異操作。本文的方法是在［n+1，2n］中隨機(jī)數(shù)作為該染色體的變異位，并隨機(jī)生成一個(gè)［1，6］的數(shù)來(lái)替換變異位上的數(shù)。

4　航空集裝板組板優(yōu)化問(wèn)題的編程實(shí)現(xiàn)

本文主要利用Andrew Kirillov開(kāi)發(fā)的AForge.NET開(kāi)源框架中的進(jìn)化算法庫(kù)（Evolution algorithms library）來(lái)完成對(duì)遺傳算法的實(shí)現(xiàn)。

4.1主程序

主程序是遺傳算法的主要部分，負(fù)責(zé)實(shí)現(xiàn)算法的體系結(jié)構(gòu)。包括創(chuàng)建初始種群，設(shè)置迭代次數(shù)，適應(yīng)值比較等功能。

4.2Chromosome類

Chromosome類包括染色體的編碼，創(chuàng)建新的染色體，克隆染色體以及染色體的交叉，變異等操作。在染色體的編碼中，通過(guò)對(duì)染色體構(gòu)造函數(shù)的重寫(xiě)，達(dá)到混合編碼的目的。

4.3FitnessFunction類

FitnessFunction類包括染色體解碼，適應(yīng)值的計(jì)算。通過(guò)對(duì)染色體的解碼，確定染色體各個(gè)基因?qū)ξ镔Y擺放空間位置確定的作用，通過(guò)構(gòu)造目標(biāo)函數(shù)，達(dá)到適應(yīng)值計(jì)算的目的。

5　小結(jié)

本文針對(duì)航空集裝板組板優(yōu)化問(wèn)題提出了一種基于混合編碼形式的遺傳算法，解決了簡(jiǎn)化模型下航空集裝板組板的求解問(wèn)題。同時(shí)利用開(kāi)源的遺傳算法框架提供了航空集裝板組板優(yōu)化問(wèn)題的編程思路，有利于推廣遺傳算法在空間規(guī)劃設(shè)計(jì)中的應(yīng)用。

［1］周獻(xiàn)中，鄭華利，田衛(wèi)萍，等.指揮自動(dòng)化系統(tǒng)輔助決策技術(shù)［M］.北京∶國(guó)防工業(yè)出版社，2012.

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

［3］余游明，劉玉樹(shù)，閻光偉.遺傳算法的編碼理論與應(yīng)用［J］.計(jì)算機(jī)工程與應(yīng)用，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］胡貴強(qiáng).多目標(biāo)優(yōu)化的遺傳算法及其實(shí)現(xiàn)［J］.重慶文理學(xué)院學(xué)報(bào)，2008，27（5）∶12-15.

［6］王曙霞，朱三元，涂俊英.基于Elitism的改進(jìn)免疫遺傳算法應(yīng)用研究［J］.計(jì)算機(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

國(guó)家自然科學(xué)基金資助項(xiàng)目（70371186）

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