基于遺傳算法的彈藥集裝模塊垛位優(yōu)化*

任俊鵬 嚴(yán) 平 譚 波

(海軍工程大學(xué)兵器工程系 武漢 430033)

?

基于遺傳算法的彈藥集裝模塊垛位優(yōu)化*

任俊鵬 嚴(yán) 平 譚 波

(海軍工程大學(xué)兵器工程系 武漢 430033)

垛位優(yōu)化是彈藥庫房管理中的重要內(nèi)容。論文首先對庫房中的彈藥集裝模塊的總搬運距離和各個垛堆的作業(yè)頻率建立多目標(biāo)優(yōu)化模型——彈藥集裝模塊垛位優(yōu)化模型;然后采用權(quán)重系數(shù)變換法的遺傳算法對多目標(biāo)問題進行優(yōu)化計算,并結(jié)合實例給出了求解的具體步驟和操作過程。最后通過Matlab對實例尺寸為15m×10m×5m的庫房垛位優(yōu)化進行計算,垛位優(yōu)化初始解經(jīng)過計算由最初的139.5697將降為132.5724。通過計算可知優(yōu)化解的降幅達到了5.01%,證明了這一方法的有效性。

垛位優(yōu)化; 集裝模塊; 遺傳算法

Class Number TJ410.3

1 引言

海軍彈藥保障正逐步擺脫“人推肩扛”的傳統(tǒng)保障模式,實現(xiàn)以托盤集裝箱為基礎(chǔ)的模塊化儲存和機械化搬運。托盤化的彈藥在進入彈藥庫房后,如何確定其在庫房中堆垛位置就成為一個關(guān)鍵的問題。垛位分配是否合理對今后彈藥的作業(yè)效率將產(chǎn)生直接的影響。如果彈藥集裝模塊的垛位分配合理,則有利于庫房中進行機械搬運作業(yè),以提高彈藥保障效率;反之,就會出現(xiàn)不同規(guī)格的托盤彈藥的布局分散,常用彈藥和戰(zhàn)備彈藥的放置不合理等現(xiàn)象,這些因素對于彈藥的快速高效保障都是不利的。當(dāng)前,我軍倉庫中儲存的箱裝物資在垛位選擇上還沒有詳細的方案,垛位的分配完全憑倉庫業(yè)務(wù)人員的經(jīng)驗進行安排[1],在彈藥的堆垛過程中,對托盤的選擇以及垛位的順序則很少考慮,垛位被隨機排列,直接影響了收發(fā)作業(yè)的效率。鑒于此種現(xiàn)狀,彈藥庫房中的集裝模塊垛位優(yōu)化問題開展研究對提高作業(yè)效率,增強戰(zhàn)時保障能力都具有重要意義。

2 彈藥垛位優(yōu)化模型

在實際的倉庫儲存過程中,不能保證一個倉庫只對一種規(guī)格的彈藥托盤進行堆放。這就面臨著對一個倉庫中多種規(guī)格的彈藥托盤的堆放進行優(yōu)化計算。既要確定一個倉庫中擺放何種規(guī)格的彈藥托盤,還要確定在該倉庫中各個規(guī)格的托盤數(shù)量和堆碼方式以及對不同彈藥的使用頻率和彈藥的儲備量來確定堆垛的位置,同時還要保證工作通道的寬度和位置設(shè)置的科學(xué)合理,從而使得每個垛位在收發(fā)過程中到門口的總路程L最短[2～3]。這樣才能提高倉庫的利用率和保障能力。

2.1 目標(biāo)函數(shù)L

對整個彈藥庫房的儲存布局優(yōu)化來說,就是保證每個垛堆中所有彈藥模塊單元的作業(yè)路程最小。所以其目標(biāo)函數(shù)L為

Lmin=[F1+F2+F3+…+Fi]

(1)

2.2 子目標(biāo)函數(shù)Fi

為保證庫房內(nèi)每個垛位的托盤到門口的總路程最短,以倉庫的一個角建立三維直角坐標(biāo)系,設(shè)一個倉庫中有l(wèi)堆托盤,第i(i=1,2,3,…,l)堆垛中任一托盤的坐標(biāo)為Vi=(x,i,y,i,z,i)m,n,g,距離函數(shù)Fi為第i堆中的所有托盤到門口的總路程。則:

(2)

其中,(i,m,n,g)表示第i堆的第m行,n列,g層的托盤。

2.3 各垛堆的權(quán)重系數(shù)

由于倉庫中儲存的彈藥品種和儲量不盡相同,且部隊對不同彈藥的需求量也不同。每一垛堆的彈藥品種、批次相同,根據(jù)不同的收發(fā)頻率和需求量設(shè)定第i堆的權(quán)重系數(shù)為Ki。垛堆的收發(fā)頻率越高[4],其權(quán)重系數(shù)Ki就越大,說明該垛堆應(yīng)該擺放在靠近門口和主通道的位置,以便于快速、高效的收發(fā)作業(yè)。

2.4 約束條件

在軍用彈藥倉庫的存儲布局中,影響路徑優(yōu)化的主要是通道的設(shè)置,如果通道的寬度和位置設(shè)置合理,就可以大大縮短作業(yè)路程和作業(yè)時間,提高作業(yè)效率。存儲區(qū)的通道主要是用于出入庫房作業(yè)的工作通道(包括機械搬運通道和手動叉車通道)和人員的檢查通道[5]。主通道連接彈藥倉儲區(qū)的進出口和各作業(yè)區(qū)域,手動叉車通道是連接主通道和各垛堆的通道,一般平行或垂直于主通道,不應(yīng)與庫房墻壁臨近,檢查通道是相鄰垛堆之間通道,用于對彈藥的日常常規(guī)性檢查[6]。

通道寬度設(shè)計根據(jù)不同作業(yè)區(qū)域、人員或車輛行走速度、單位時間按通行人數(shù)、搬運物品體積等因素而定。為了滿足搬運機械的轉(zhuǎn)彎半徑和作業(yè)順暢,設(shè)定作業(yè)面T作≥4.2m,叉車通道T叉≥1.8m,為方便庫房的日常檢查,設(shè)定檢查通道T檢≥0.6m,為了保證機械作業(yè)的安全,垛堆的頂高距天花板的距離D通常大于等于0.5m[7～10]。即約束條件為

(3)

這樣才能保證機械搬運的順利作業(yè),完成收發(fā)任務(wù)。

2.5 歸一簡化處理

根據(jù)彈藥庫房的堆垛原則,同一批次的彈藥和同一型號的托盤集中放置。在儲存布局的確定中,由于垛堆的層數(shù)g對于垛堆位置的設(shè)定不產(chǎn)生影響,而且在確定了垛堆的位置后,層數(shù)g對于作業(yè)路程L的影響也比較小。因此,為了簡化運算,將模型中堆垛層數(shù)設(shè)定為1層。

由式(2)可知,第i垛堆中的任一托盤坐標(biāo)為Vi,因此Vi可簡化為(xi,yi,1)m,n,1。對于垛堆中的每個托盤的坐標(biāo)可進行歸一化處理。由于每個垛堆的托盤的規(guī)格相同,所以垛堆的中心坐標(biāo)V中為

(4)

進而可以得到Fi的簡化

Fi=m*n*V中

(5)

即當(dāng)確定了一個垛堆的托盤數(shù)和中心坐標(biāo)后,便可以得到該垛堆所有集裝單元的作業(yè)路程總值。

2.6 模型表示

綜上所述,根據(jù)式(1)～式(5),彈藥庫的儲存布局?jǐn)?shù)學(xué)模型為

Lmin=[k1*F1+k2F2+k3F3+…+klFl]

約束條件:

(6)

3 遺傳算法對實例問題的優(yōu)化求解

3.1 選取算法類型

從上述模型建立過程中可以看出,對于彈藥存儲的集裝模塊優(yōu)化問題是多目標(biāo)優(yōu)化問題,需要考慮多個目標(biāo)函數(shù)的同時優(yōu)化。根據(jù)本模型中的多目標(biāo)優(yōu)化,采用權(quán)重系數(shù)變換法來進行計算,根據(jù)各個垛堆不同的收發(fā)頻率和需求量等因素綜合設(shè)定權(quán)重系數(shù)Ki。將多目標(biāo)優(yōu)化問題化為單目標(biāo)優(yōu)化問題,進而求解多目標(biāo)優(yōu)化問題[11～12]。

3.2 實例計算

3.2.1 選定托盤規(guī)格

托盤是一種用于機械化裝卸、搬運和堆存貨物的集裝單元工具,GJB184A-1999《軍用立柱式托盤和箱式托盤基本尺寸和額定載重量》中規(guī)定了三種軍用托盤標(biāo)準(zhǔn)尺寸,分別是800mm×1200mm、1000mm×1200mm和1100mm×1100mm。

設(shè)定一地面庫長D=15m,寬W=10m,高為Z=5m,堆垛最多層數(shù)為G=3,為簡化計算,選擇規(guī)格為1200×1000×1300,1200×800×1300,1100×1100×1300的三種托盤來進行堆垛。為了保障堆碼的順利和收放作業(yè)的通暢,設(shè)定主作業(yè)面4.2m,檢查通道0.6m,叉車通道1.8m。托盤的堆放按照彈藥庫房的堆放原則擺放,保證彈體與通風(fēng)口方向一致[13]。其堆垛樣式如圖1所示。

圖1 地面庫堆碼效果圖

3.2.2 數(shù)學(xué)模型表示

現(xiàn)對實例庫房中的集裝模塊垛位優(yōu)化模型進行數(shù)學(xué)表達。設(shè)地面彈藥庫有一個出入口,庫房長15m,寬10m,高5m?，F(xiàn)存三個垛堆,垛堆的托盤規(guī)格分別為:1200×1000×1300,1200×800×1300,1100×1100×1300三種。如圖2所示。

圖2 庫房儲存布局示意圖

其中,各垛堆的權(quán)重系數(shù)k1=0.7,k2=0.5,k3=0.3。編號為①、②、③的托盤分別為三個垛堆的中心托盤,設(shè)其坐標(biāo)分別為V1(x1,y1),V2(x2,y2),V3(x3,y3)。則目標(biāo)函數(shù)為

Lmin=[k1F1+k2F2+k3F3]

(7)

約束條件:

即:

Lmin=[k1F1+k2F2+k3F3]

(8)

3.3 具體算法步驟

· 第一步:編碼

在遺傳算法中最常用的編碼方式為二進制編碼,但是這種編碼方式不能較好地適用于貨位規(guī)劃這個多目標(biāo)優(yōu)化分配問題[14]。由于約束條件為實數(shù)區(qū)間,所以本文采用十進制實數(shù)編碼。染色體的編碼采用順序表達法,即根據(jù)集裝模塊單元的位置在庫房中的順序進行編碼。設(shè)定庫房中共有i個集裝模塊單元,每個單元的位置可以設(shè)定為(xi,yi),那么染色體的編碼為[(x1,y1)(x2,y2)(x3,y3)(x4,y4)…(xi,yi)],其示意圖如下:

X1，Y1X2，Y2X3，Y3X4，Y4……Xi，Yi

在運算過程中為保證計算的精度,可以將染色體編碼轉(zhuǎn)換為二進制進行計算,再對計算結(jié)果轉(zhuǎn)換為十進制進行表示。

· 第二步:生成初始種群

根據(jù)約束條件,隨機生成數(shù)量為N的初始種群,作為垛位優(yōu)化的初始解。

· 第三步:適應(yīng)度函數(shù)

根據(jù)目標(biāo)函數(shù)Lmin=[k1*F1+k2F2+k3F3+…+kiFi]以及權(quán)重系數(shù)ki計算出每個集裝模塊單元的最短路徑,因此,目標(biāo)函數(shù)值越大,個體遺傳到下一代的概率就越小,即適應(yīng)度越小。為了滿足目標(biāo)值的優(yōu)化要求,就要在選擇之前將個體目標(biāo)函數(shù)轉(zhuǎn)化為適應(yīng)值:

(9)

式中Cmax為一個適當(dāng)?shù)南鄬^大的數(shù),這里定為L(x)的最大值。適應(yīng)度函數(shù)的分配通過ranking函數(shù)計算,按照個體的目標(biāo)值Lmin由小到大的順序進行對它們進行排序,使用線性評估,給最適應(yīng)個體的適應(yīng)度值為2,最差個體的適應(yīng)度值為0。

· 第四步:選擇遺傳算子

在選擇遺傳算子時采用選擇比例算子。個體被選擇的概率由式(10)給出,

(10)

其中P(xI)為這個個體被選擇的概率,fi為個體的適應(yīng)度值,∑fi為個體的適應(yīng)度之和。

· 第五步:交叉、變異運算

在遺傳算法中,通常隨機選擇兩個個體進行交叉操作。通過交叉操作使得目標(biāo)函數(shù)下的優(yōu)良基因可以充分組合,以保證較大概率的找到目標(biāo)函數(shù)的有化解。交叉概率的取值范圍一般是:0.4～0.99。

變異運算決定了遺傳算法的局部搜索能力。變異算子按照一定的概率(變異概率)選擇部分個體的部分染色體進行變異,被選定的個體按照隨機選擇的兩個垛位的位置進行相互對換,生成新的個體的同時又保持了種群的多樣性。交叉概率的取值范圍一般為:0.0001～0.1。

· 第六步:終止操作

遺傳算法的終止操作有很多種,本文采用設(shè)定遺傳的迭代代數(shù)。當(dāng)遺傳迭代代數(shù)達到設(shè)定數(shù)值后,自動停止計算。否則繼續(xù)返回到第三步繼續(xù)運算,直到到達設(shè)定代數(shù)為止[15]。

3.4 通過Matlab編程對優(yōu)化解進行表示

根據(jù)本文中的實例設(shè)定,可以通過Matlab編程進行運算。設(shè)定初始種群NIND=100;最大遺傳代數(shù)MAXGEN=50;代溝GGAP=0.9;交叉概率Px=0.7;變異概率Pm=0.02。計算50代后得到最優(yōu)解如表2及種群均值變化的性能跟蹤如圖3所示。

表2 進化后的最優(yōu)化解

圖3 種群均值變化性能跟蹤圖

4 結(jié)果

通過以上計算可以看出,隨著遺傳代數(shù)的增加,最優(yōu)解有了明顯的下降。經(jīng)過50代的遺傳進化,最優(yōu)解從最初的139.5697將降為132.5724,降幅達到了5.01%。對于垛堆的位置坐標(biāo)也得到了最優(yōu)解:(x1,y1)=(3.9051,3.0000),(x2,y2)=(3.9020,4.3019),(x3,y3)=(3.7513,6.4618)。在優(yōu)化進程中,庫房中各個通道的寬度數(shù)據(jù)如表3所示,T3的初始值為0.0833,經(jīng)過交叉變異30代后達到了0.4358,雖然有所提高,但仍不滿足要求。在50代時達到了0.7118(大于0.6),滿足了庫房作業(yè)通道的基本要求。以上數(shù)據(jù)計算表明通過遺傳算法該對解決垛位優(yōu)化問題有較為明顯的效果。

表3 優(yōu)化后的通道數(shù)值

5 結(jié)語

本文通過對現(xiàn)有彈藥倉庫的集裝化模塊彈藥垛位優(yōu)化問題建立數(shù)學(xué)模型,選定合適規(guī)格的托盤,運用遺傳算法對彈藥倉庫垛位布局進行實例優(yōu)化計算,通過Matlab編程計算得出集裝模塊彈藥垛堆的優(yōu)化位置以及庫房的作業(yè)通道設(shè)置,在計算過程中,隨著遺傳進化代數(shù)的增加,可以看出總路程明顯的減少以及通道寬度的不斷優(yōu)化,最終實現(xiàn)了彈藥跺位的優(yōu)化,為提高倉庫作業(yè)效率和彈藥堆的合理布局提供了較為科學(xué)的依據(jù)。

[1] 馮濤,鐘敬武.貨位布局技術(shù)在后方倉庫中的研究與實現(xiàn)[J].計算機技術(shù)與自動化,2006,25(4):293-295.

[2] 陶英歌,郭乃林,羅紅英.基于遺傳算法的目標(biāo)分配優(yōu)化模型研究[J].系統(tǒng)工程與電子技術(shù),2003:817-819.

[3] 魏國辰.物流機械設(shè)備的運用與管理[M].北京:中國物資出版社,2002,1:173-190.

[4] 賀鑫,馬振書,李良春,等.遺傳算法在箱裝軍用物資垛位優(yōu)化中應(yīng)用[J].科學(xué)技術(shù)與工程,2011,11(1):93-94.

[5] 朱子音.提高庫房利用率方法研究[D].長春:吉林大學(xué)碩士論文,2008:22-23.

[6] 劉昌祺.物流配送中心設(shè)施及設(shè)備設(shè)計[M].北京:機械工業(yè)出版社,2004,9:1-18,156-169.

[7] 李梅娟,陳雪波.Pareto遺傳算法在貨位配置中的應(yīng)用研究[J].控制工程,2006:139-140.

[8] Stengel R F, Ray L R. Stochastic robustness of linear time-invariant systems[J]. IEEE Trans On Aut Control,1991,36(1):82-87.

[9] Ray L R, Stengel RF. AMont Carlo approachtothe analysisof control system robustness[J]. Automatica,1993,29(2):229-236.

[10] Carlos F M, Peter F J. An overview of evolutionary algorithmsin multiobjective optimization[J]. Evolutionary Computation,1995,3(1):1-16.

[11] 雷英杰,張善文,李續(xù)武,等.MATLAB遺傳算法工具箱及應(yīng)用[M].西安:西安電子科技大學(xué)出版社,2011:45-61,107-118.

[12] 龔純,王正林.精通MATLAB最優(yōu)化計算[M].北京:電子工業(yè)出版社,313-315.

Ammunition Container Module Stacking Location Optimization Based on Genetic Algorithm

REN Junpeng YAN Ping TAN Bo

(Department of Weaponry Engineering, Naval University of Engineering, Wuhan 430033)

Stacking location optimization is an important content of ammuniction warehouse management. Firstly, this paper establishes the warehouse of the module ammunition container tatal moving distance and the heap stacking location usage frequency multi-objecctive optimization model. Then, the weight coefficient transform method of multi-objective genetic algorithm is used for optimization calculation with true instance, and the specific steps and the operating process are given. Finally, the warehouse of the actual size of 15m×10m×5m optimizations are calculated by Matlab, and the optimization solution down from 139.569 to 132.5724, reduced by 5.01% which have proved the effectiveness of the proposed method.

stacking location optimization, containers module, genetic algorithm

2015年6月13日,

2015年8月1日

任俊鵬,男,碩士研究生,研究方向:武器系統(tǒng)運用與保障工程。嚴(yán)平,男,博士,副教授,研究方向:武器毀傷效能與彈藥設(shè)計。譚波,男,博士,講師,研究方向:彈藥工程。

TJ410.3

10.3969/j.issn.1672-9730.2015.12.030