基于遺傳算法的軍用集裝箱裝載優(yōu)化

摘要：以軍用集裝箱裝載為研究對象，在考慮實際應(yīng)用中的一些約束條件下，構(gòu)造了軍用物資的裝載優(yōu)化模型，提出了一種軍用集裝箱三維裝載的遺傳算法。該算法考慮了貨物放置方向、裝載容積、裝載質(zhì)量及裝載重心等約束條件。最后對一個案例進行了計算，驗證了該模型的有效性，并且利用3ds max得到了裝載方案的三維圖。

關(guān)鍵詞：軍用集裝箱；三維裝載；遺傳算法

中圖分類號：U169文獻標識碼：A文章編號：1002-3100(2007)05-0169-03

Abstract: This paper studies the problem of military container packing. Considering multi-constraints in applications， an optimizing stowage model is set up， and a genetic algorithm for the three dimension packing problem is presented in this paper. The genetic algorithm takes account of the direction which the goods are placed， the loading capacity loading mass， the center of the gravity of the load and other constraints. Finally， the practical calculation shows that the method is effective， and three-dimensional drawing is gotten with help of 3ds max.

Key words: military container; three-dimensional packing; genetic algorithm

對軍用集裝箱的裝載方案進行優(yōu)化設(shè)計可以提高軍用集裝箱的利用率，不僅可以帶來可觀的經(jīng)濟利益，而且對于提高部隊的后勤保障能力有著重要的意義。

裝箱問題是一個具有復(fù)雜約束條件的組合優(yōu)化問題，理論上屬于NP-hard問題，對于這個問題的求解，通常采用動態(tài)規(guī)劃和啟發(fā)式算法。動態(tài)規(guī)劃法可以搜索到符合條件的全部裝載方案，但隨著箱子數(shù)目的增加，就會使搜索空間以2n指數(shù)規(guī)模擴大，計算時間增加。孟冬梅對George和Robinson啟發(fā)式算法進行了改進，但該算法沒有考慮物資裝載時的重心問題；劉寶新對相同尺寸軍用物資的裝箱問題進行了研究，但該方法實際使用時受到較大限制。為此，本文將就上述存在的問題著力進行如下的工作：根據(jù)實際裝載過程的約束條件，建立了以最大空間利用率為目標的單集裝箱三維裝載的數(shù)學(xué)模型；提出一種基于計算機的三維裝箱問題的遺傳算法；其結(jié)果可為一線裝載人員提供科學(xué)指導(dǎo)。

1軍用集裝箱裝載問題的描述

1.1問題的描述和建模。我軍集裝箱運輸起步晚、發(fā)展規(guī)模比較小，在實際的軍用集裝箱運輸過程中經(jīng)常遇到的問題是：待裝的軍用物資數(shù)量遠遠超過集裝箱的承載能力，要求在有限的集裝箱空間內(nèi)盡可能多地裝填貨物，使得集裝箱的利用率最大。

鑒于問題的復(fù)雜性，本文對實際問題進行如下的約定和要求：（1）軍用物資簡化為長方體，且?guī)缀沃行臑槠渲匦模唬?）物資可以放置于集裝箱中任意位置而不受配置位置的限制；

集裝箱在實際裝載過程中常見的約束條件包括：（1）總重量約束：集裝箱裝載的總質(zhì)量不得大于集裝箱的額定裝載量；（2）總?cè)莘e約束：集裝箱裝載的總?cè)莘e不得大于集裝箱的額定容積；（3）方向性約束：在裝載中，貨物的擺放方向受到的約束，如“不可倒置”、“必須橫裝”等。引入自由度變量R，R=1表示軍用貨物可以水平旋轉(zhuǎn)，R=0表示軍用貨物只能橫裝；（4）穩(wěn)定性約束：物資裝載完畢后，貨物的重心應(yīng)該在集裝箱的幾何中心附近，以保證物資運輸?shù)陌踩浴?/p>

1.2裝載空間的描述。本文采用三叉樹空間分割的方法，即當一個貨物裝入一個集裝箱后，該集裝箱被分割為三個空間，分別為右空間，前空間，上空間，如圖1所示。

2遺傳算法的實現(xiàn)

2.1個體編碼及解碼

2.2適應(yīng)度計算

通過個體適應(yīng)值的大小來評價群體中個體所對應(yīng)裝載方案的優(yōu)劣，對于違反裝載質(zhì)量約束、裝載容積約束的和裝載重心約束的個體，在求解其適應(yīng)值的過程中要給與相應(yīng)的懲罰以確保符合條件而較優(yōu)的個體有較大的生存機會。評價一個解的好壞需要考慮三個方面。

2.2.1空間的利用率函數(shù)

2.3遺傳操作過程

2.3.1選擇操作。本文采用比例選擇法來選擇個體，其基本思想：各個個體被選擇中的概率與其適應(yīng)度的大小成正比，適應(yīng)度越高的個體被選中的個體被選中的概率越大；反之，適應(yīng)度越低的個體被選中的概率就越小。第gen

2.3.2交叉操作。為了確保貨物放置方向基因編碼在遺傳操作過程中的有效性，本文采用部分映射交叉的方式。部分交叉映射也稱為匹配交叉，其基本的思想是：整個交叉操作由兩步來完成，首先對個體編碼串進行常規(guī)的雙點交叉操作，然后根據(jù)交叉區(qū)域內(nèi)各個基因值之間的映射關(guān)系來修改交叉區(qū)域之外的各個基因座的基因值。

2.3.3變異操作。為了在遺傳操作過程中保持群體的多樣性，避免算法早熟收斂甚至無法尋到全局最優(yōu)解，對個體采取變異操作：在n+1， 2n之間按均勻分布隨機產(chǎn)生一個整數(shù)作為基因s ~s 間的變異位，并將該位置基因值替換為貨物放置方向編號取值范圍內(nèi)隨機產(chǎn)生的一個編號值。

3應(yīng)用舉例

現(xiàn)有一批軍用物資，每類物資的長度、寬度、高度、質(zhì)量及數(shù)量見表。待用集裝箱JY10的主要技術(shù)參數(shù)為：長4 012mm，寬2438mm，高度2438mm，額定載重量為10t。試確定充分利用集裝箱空間利用率的合理裝載方案。（自由度R=1，即軍用物資可以橫、順混裝）

應(yīng)用本文提出的遺傳算法計算，各項初始參數(shù)取值分別為：群體規(guī)模n=30，最大迭代代數(shù)GEN=200，交叉概率Pc=0.95，變異概率Pm=0.01。優(yōu)化裝載的結(jié)果為：A物資24箱，B物資60箱，D物資72箱，共裝載156箱。集裝箱的總裝載質(zhì)量為6.57t，總裝載容積為20.44m3，集裝箱的空間利用率為85.72%。通過3ds max圖形處理技術(shù)，得到最優(yōu)裝載方案的三維圖（如圖2所示）。為了防止軍用物資破損，在實際裝載過程中需要用木板、覆蓋物之類材料來填補貨物之間的空隙。

4結(jié)束語

要搞好軍用物資集裝箱儲運工作，充分發(fā)揮集裝箱運輸?shù)膬?yōu)勢，除了要有良好的運輸設(shè)備和搬運設(shè)備外，還應(yīng)該提高集裝箱的利用率。采用遺傳算法對這類問題進行求解，方法簡單易行，其結(jié)果可為后勤倉庫的指揮員的指揮決策提供科學(xué)的依據(jù)，從而大大提高后勤倉庫工作效率。

參考文獻：

[1] 王小平，曹立明. 遺傳算法——理論、應(yīng)用與軟件實現(xiàn)[M]. 西安：西安交通大學(xué)出版社，2002:123-140.

[2] 付景珊. 3ds max6.0從入門到精通[M]. 北京：中國電力出版社，2005:56-131.

[3] 錢頌迪. 運籌學(xué)[M]. 北京：清華大學(xué)出版社，1990:193-253.

[4] 孟冬梅. 集裝箱裝載問題研究[D]. 天津：天津大學(xué)，2002:25-36.

[5] 卜雷，等. 遺傳算法確定零擔貨物的選擇裝箱方式[J]. 交通運輸工程學(xué)報，2002，2(3):93-96.

[6] 劉寶新，等. 集裝箱裝載貨物的優(yōu)化研究[J]. 集裝箱化，2003(4):12-13.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”