裝備維修過程中備件布局的多目標(biāo)優(yōu)化決策

郭　璐　楊　云　王　崴　劉曉衛(wèi)

(空軍工程大學(xué)防空反導(dǎo)學(xué)院　陜西 西安 710051)

?

裝備維修過程中備件布局的多目標(biāo)優(yōu)化決策

郭璐楊云王崴劉曉衛(wèi)

(空軍工程大學(xué)防空反導(dǎo)學(xué)院陜西 西安 710051)

為保證在裝備維修過程中能精確、及時、高效地取用備件，提出備件車裝載布局優(yōu)化問題。針對該問題建立備件布局優(yōu)化數(shù)學(xué)模型，以備件車承載容積、載重量及重心等為約束條件，綜合考慮備件車空間利用率、備件合重心對行車安全性的影響和備件取用效率為目標(biāo)函數(shù)。根據(jù)備件布局模型的特殊性，基于模擬退火算法的思想，將其與帶壓縮因子的粒子群優(yōu)化算法結(jié)合，應(yīng)用于實例中求解布局方案，并將此混合算法的計算結(jié)果與基本粒子群優(yōu)化算法的計算結(jié)果進行了比較。結(jié)果表明，使用混合粒子群優(yōu)化算法可以獲得較好的裝載布局優(yōu)化方案，達到充分利用備件車裝載空間、安全性好和取用效率高的目的。

備件車布局粒子群算法模擬退火算法壓縮因子

0　引　言

備件車是專門用來裝載備件的車輛，其用途主要是給在戶外作業(yè)發(fā)生故障的設(shè)備提供維修所需工具及零件，保證其能及時地恢復(fù)正常工作[1]。在現(xiàn)代戰(zhàn)爭環(huán)境下，決定戰(zhàn)爭勝負(fù)的因素之一是裝備的保障能力。對于導(dǎo)彈裝備而言，保障工作的核心就是維修，而裝備維修保障的關(guān)鍵就在于保障備件的及時供應(yīng)[2]。因此，在有限空間內(nèi)，如何對備件進行布局，能否精確、迅速地取用備件決定著裝備的維修保障能力，這是裝備維修保障工作的重難點[3]。

備件車裝載布局是將復(fù)雜繁多的備件裝載到備件車有效空間內(nèi)以及將備件存放位置在此空間內(nèi)布置。此問題屬于NP[4]難問題，約束條件復(fù)雜，目標(biāo)函數(shù)多，采用確定性優(yōu)化算法求解時不易獲得理想的結(jié)果甚至有時得不到結(jié)果。鑒于此，對于NP

難問題，很多學(xué)者采用群智能優(yōu)化算法求解。文獻[5]采用空間分割方法建立了三維布局模型，運用蟻群算法對三維混合布局優(yōu)化問題優(yōu)化進行求解，得到了最優(yōu)解。隨著智能算法越來越受到廣大學(xué)者關(guān)注與研究，部分學(xué)者將多種智能算法混合求解裝載布局問題。文獻[6]為解決設(shè)備布局這一典型的NP難問題，提出將模擬退火方法與粒子群算法有機結(jié)合，使算法全局搜索能力增強。也有很多學(xué)者對群智能算法進行改進，以彌補部分算法較易陷入局部最優(yōu)的缺陷或者使算法收斂速度更快。文獻[7]針對面積不同但形狀固定的設(shè)備的布局問題，提出了改進的遺傳算法，實現(xiàn)了算法參數(shù)的非線性自適應(yīng)調(diào)整，實例仿真表明，此算法可以較快地獲得所求問題的近似最優(yōu)解。

本文提出了混合粒子群優(yōu)化算法PSO(particle swarm optimization)解決備件車裝載布局問題。PSO算法[8]憑借其操作流程簡單、收斂速度快等特點在組合優(yōu)化問題上獨樹一幟，但其缺陷也是不容忽視的，即其在尋優(yōu)過程中全局搜索能力不強，較易陷入局部極值。為此，本文在已有算法及各種改進算法的啟發(fā)下，將有突跳能力、能夠有效避免搜索過程陷入局部最優(yōu)的模擬退火SA(simulated annealing)算法[9]與PSO算法很好地融合在一起來求解備件車布局優(yōu)化問題。

國內(nèi)外研究備件車的文獻比較少，在類似問題上已有不少相關(guān)研究成果。主要的研究關(guān)注對布局空間利用率的提升上，對于待布備件重心的約束與優(yōu)化較少，鮮有考慮提高待布備件取用效率的問題。根據(jù)備件車裝載的一般性及特殊性，對于備件車裝載布局的研究既要參考一般貨物裝載布局設(shè)計又要借鑒人機工效。因此，本文充分考慮備件車空間利用率、備件車行車安全性和備件取用效率，對備件建立多目標(biāo)布局優(yōu)化模型，采用混合粒子群優(yōu)化算法求解數(shù)學(xué)模型，得到備件裝載布局的優(yōu)化方案。

1　備件布局優(yōu)化模型

本文采用提取備件最小組合包絡(luò)矩形塊的方法對備件進行簡化處理。處理完成后，備件即為大小各異的矩形塊。設(shè)有N個待布備件，pi表示第i個備件，i=1,2,…,N，qi和vi分別為備件pi的重量和體積；L、W和H為備件車的長、寬和高；Q和V分別表示備件車最大載重量和最大可用空間。進行布局前，先建立笛卡爾坐標(biāo)系，以備件車內(nèi)左前下角為坐標(biāo)原點，X軸從原點出發(fā)，沿備件車底板側(cè)邊，平行于備件車底板縱中心線；Y軸從原點出發(fā)，沿備件車端，平行于備件車底板橫中心線；Z軸從原點出發(fā)，垂直于備件車底板平面。如圖1所示。

圖1　備件車坐標(biāo)系

基于此，分別考慮備件車空間及載重約束、備件車行車安全性及備件取用效率這三方面因素建立布局優(yōu)化數(shù)學(xué)模型。

1.1基于備件車空間及載重約束的數(shù)學(xué)模型

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

i=1,2,…,Nj=1,2,…,Ni≠j

(10)

目標(biāo)函數(shù)表示使備件車空間利用率最大。約束條件中，式(2)—式(4)為備件布局的不干涉約束，表示備件在布置時互不重疊；式(5)—式(7)為備件車的邊界約束，表示備件布局時不允許超出備件車的邊界；式(8)為載重約束，表示裝載備件的總重量不允許超過備件車的最大載重量；式(9)為容積約束，表示裝載備件的總體積不允許超過備件車的有效容積。

1.2基于備件車行車安全性的數(shù)學(xué)模型

(11)

(12)

(13)

(14)

式(11)—式(14)中，(Cx,Cy,0)為車底板縱橫中心線交叉點坐標(biāo)；Δy為備件合重心的橫向容許偏移量；Δx為備件合重心的縱向容許偏移量；Δz為備件合重心的最大允許高度(以備件車底板為起始面)。

目標(biāo)函數(shù)表示使備件的合重心偏移量最小。約束條件中，式(12)—式(14)為合重心約束，表示備件車中的備件的合重心偏移量必須在規(guī)定的范圍內(nèi)。

1.3基于備件取用效率的數(shù)學(xué)模型

人機工效布局原則是進行布局設(shè)計的依據(jù)，本文依照備件布局的特殊性，選取備件的重要性、使用頻率、以及備件相關(guān)性等設(shè)計原則對基于備件取用效率的備件車進行布局研究。根據(jù)人在備件車內(nèi)手部的操作范圍、人眼的視野范圍及人存取備件需要行走的距離(備件距離備件車門的距離)，來評判備件位置的優(yōu)劣，并對備件進行排序。綜合考慮這三個因素，將人手操作最舒適、人眼最易注意到且距離車門最近的位置的備件排列在最前面，位置次之的備件接連排列，直到位置最次的備件排列完成。對于N個需要布局的備件，可組成有序序列X={x1,x2,…,xn}，x1,x2,…,xn∈pi，i=1,2,…,N。本文結(jié)合以下人機工效布局原則，建立備件取用效率評價的數(shù)學(xué)模型。

(1) 重要性原則

重要性原則是指根據(jù)備件的重要程度大小，把重要的備件布置在備件車內(nèi)易于取用的位置。對于取用者來講，重要度高的備件應(yīng)該布置在操作者手部最適宜存取區(qū)域內(nèi)或者操作者視野的最佳范圍內(nèi)或者存取所需移動的距離最短的位置。

在備件的布局序列中，重要性越高的備件則在布局序列中越靠前。備件pi的重要性權(quán)值用Pmi表示，由此構(gòu)造備件重要性子目標(biāo)函數(shù)：

(15)

由式(15)意義可知，f1(X)值越大表示序列X={x1,x2,…,xn}越符合重要性原則。

(2) 使用頻率原則

使用頻率原則是指將維修過程中使用次數(shù)多的備件布置在便于尋找和存取的位置，提高取用的速度和準(zhǔn)確性，并減輕維修人員的生理和心理負(fù)擔(dān)。

對于使用頻率的量化可采用統(tǒng)計方法，備件pi的使用頻率權(quán)值用Fri表示。使用頻率越高的備件在布局序列中的位置越靠前，由此得使用頻率子目標(biāo)函數(shù)：

(16)

由式(16)可知，f2(X)值越大表示序列X={x1,x2,…,xn}越符合使用頻率原則。

(3) 相關(guān)性原則

在維修過程中，有些備件需要與其他備件協(xié)同使用來完成維修任務(wù)，這些備件具有相關(guān)性，相關(guān)性是備件布局中需考慮的重要原則。備件pi與pj的相關(guān)性大小用Rexixj表示，相關(guān)性參數(shù)進行歸一化處理，數(shù)值越大表明備件相關(guān)性越大。備件間相關(guān)性系數(shù)如表1所示。

表1　備件相關(guān)性

兩備件間相關(guān)性越大，在布局序列中的位置越靠近，由此可得相關(guān)性子目標(biāo)函數(shù)：

(17)

由式(17)可知，f3(X)值越大表示序列X={x1,x2,…,xn}越符合相關(guān)性原則。

(4) 目標(biāo)函數(shù)

綜合考慮上述三種布局原則及各原則之間的關(guān)系，通過加權(quán)法將以上三個子目標(biāo)函數(shù)組合，可構(gòu)建如下備件布局優(yōu)化目標(biāo)函數(shù)：

maxF(X)=ω1f1(X)+ω2f2(X)+ω3f3(X)

(18)

式(18)中，ωi(i=1,2,3)為各子目標(biāo)函數(shù)的權(quán)重系數(shù)，可根據(jù)維修任務(wù)及待裝備件的特點對子目標(biāo)權(quán)重值加以調(diào)整，以適應(yīng)實際的需求。

1.4備件車裝載布局優(yōu)化的數(shù)學(xué)模型

本文所研究的備件車裝載布局優(yōu)化問題屬于多目標(biāo)優(yōu)化問題，因此先根據(jù)不同的約束或者原則對各目標(biāo)函數(shù)進行分步設(shè)計，最終采用加權(quán)法確定最終目標(biāo)函數(shù)。綜合考慮備件車空間及載重約束、備件車行車安全性及備件取用效率這三方面因素，可建立約束條件為式(2)—式(9)及式(11)—式(13)、目標(biāo)函數(shù)如式(18)的布局優(yōu)化數(shù)學(xué)模型：

(19)

式(19)中的權(quán)重系數(shù)α為備件車空間利用率權(quán)重系數(shù)，β為備件合重心位置偏移量權(quán)重系數(shù)，γ為備件存取效率權(quán)重系數(shù)。目標(biāo)函數(shù)中，第1項為備件車空間利用率，第2項為備件合重心位置偏移量，第3項為備件存取效率。

2　備件布局的混合粒子群算法求解過程

2.1基于模擬退火的粒子群優(yōu)化算法

基于模擬退火SA的粒子群算法中的粒子群算法采用帶壓縮因子的粒子群優(yōu)化算法CFPSO(Constrict Factor Particle Swarm Optimizer)，CFPSO算法通過選取合適參數(shù)，可確保算法的收斂性。算法中速度和位置更新公式如下：

vi,j(t+1)=χ[vi,j(t)+c1r1(pi,j(t)-xi,j(t))+

c2r2(pg,j(t)-xi,j(t))]

(20)

xi,j(t+1)=xi,j(t)+vi,j(t+1)j=1,2,…,d

(21)

vi,j(t+1)=χ[vi,j(t)+c1r1(pi,j(t)-xi,j(t))

(22)

(23)

2.2應(yīng)用混合粒子群算法的備件車布局

(1) 粒子群初始化

在備件車布局優(yōu)化過程中，假設(shè)備件車要裝載D個矩形塊備件，一個微粒表示一種布局方案，則每個微粒的編碼是一個3D維向量P=(x1,…,xd,y1,…,yd,z1,…,zd)，前面、中間及后面D維分別表示備件重心的X坐標(biāo)、Y坐標(biāo)及Z坐標(biāo)；每個粒子的行進方向和飛行速率也是一個3D維向量V=(vx1,…,vxd,vy1,…,vyd,vz1,…,vzd)，前面、中間及后面D維分別表示備件在X方向、Y方向及Z方向的移動速度。每個微粒的位置根據(jù)式(20)和式(21)進行變換。

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

針對此備件車布局，適應(yīng)度函數(shù)可表示為F=maxZ。由此可知，適應(yīng)度值越大，目標(biāo)函數(shù)值越大，求得的布局方案越滿足要求。

(3) 停止規(guī)則

算法運行之前會設(shè)定一個迭代次數(shù)，若算法運行到最大迭代次數(shù)，則迭代結(jié)束，退出程序；或者算法運行到一定程度，適應(yīng)度函數(shù)值連續(xù)迭代30步保持平穩(wěn)，則停止循環(huán)，退出程序。退出后即可得到適應(yīng)度值最優(yōu)的布局結(jié)果。

2.3問題求解和算法流程設(shè)計

SA-PSO算法尋優(yōu)步驟如下：

步驟1隨機初始化微粒的位置和速度。

步驟2計算種群中每個微粒的適應(yīng)度fitness，并尋找粒子的pbest和gbest。

步驟3重復(fù)執(zhí)行以下步驟。

① 對粒子的pbest進行SA鄰域搜索，初始化退火溫度Tk(k=0)。

③ 退火操作：Tk+1=CTk,k←k+1，其中C∈(0,1)。若滿足收斂判據(jù)，則退火過程結(jié)束；否則，轉(zhuǎn)②。

步驟4根據(jù)改進的更新方程式(22)和式(21)來調(diào)整粒子的速度和位置，并更新粒子的pbest。

步驟5執(zhí)行最優(yōu)選擇操作，更新種群gbest。

步驟6判斷gbest是否滿足算法終止準(zhǔn)則，若滿足，則輸出全局最優(yōu)解；若不滿足，返回到步驟3。

3　算例分析

本文以備件車為背景，求解備件的3維正交布局方案，抽取16組待布備件，備件重要性權(quán)值、使用頻率權(quán)值及其相關(guān)性系數(shù)如表2和表3所示。設(shè)定備件布局優(yōu)化數(shù)學(xué)模型中重要性權(quán)重系數(shù)w1=0.2，使用頻率權(quán)重系數(shù)w2=0.5，相關(guān)性權(quán)重系數(shù)w3=0.3；設(shè)定優(yōu)化算法種群規(guī)模sizepop=50，學(xué)習(xí)因子c1=c2=2，最大迭代次數(shù)M=1000；退火初始溫度退火溫度T0=1000，衰減因子C=0.5。

表2　待布備件重要性及使用頻率權(quán)值

表3　待布備件相關(guān)性

由于對備件進行布局設(shè)計需綜合考慮備件車空間利用率、備件合重心對行車安全性的影響和備件取用效率，故在維修任務(wù)及外界環(huán)境因素不同的情況下備件布局優(yōu)化數(shù)學(xué)模型參數(shù)設(shè)置不同。若備件繁多，備件車空間有限，需重點考慮備件車空間利用率的問題，則權(quán)重系數(shù)α取值較大；若備件車行車路況惡劣，需保證備件車行車安全性，則權(quán)重系數(shù)β取值較大；若備件車空間較大，行車路況良好，在維修過程中需精確、快速地取用備件，則權(quán)重系數(shù)γ取值較大。下面設(shè)計三種備件布局模型：(1)側(cè)重考慮備件車空間利用率，取權(quán)重系數(shù)α=0.6，β=0.2，γ=0.2；(2)側(cè)重考慮備件車行車安全性，取權(quán)重系數(shù)α=0.2，β=0.6，γ=0.2；(3)側(cè)重考慮備件取用效率，取權(quán)重系數(shù)α=0.2，β=0.2，γ=0.6。采用SA-PSO算法求解布局模型，進行了10次計算，對求解結(jié)果取平均值如表4所示。由表4可以看出，方案一的布局結(jié)果備件車空間利用率最大；方案二的布局結(jié)果備件合重心偏移最小，備件車行車安全性最高；方案三的布局結(jié)果備件取用效率最高。三種布局結(jié)果均符合外界環(huán)境及維修任務(wù)的需求。

采用標(biāo)準(zhǔn)PSO算法求解布局模型，進行了10次計算，選取布局模型三的一次求解過程如圖2所示。由圖2可知，本文的SA-PSO算法能搜索到全局最優(yōu)點，且找到最優(yōu)解的速度更快。觀察10次平均求解過程及結(jié)果如表5和表6所示。根據(jù)SA-PSO算法求得的布局結(jié)果，畫出備件最優(yōu)布局位置如圖3所示。

圖2　SA-PSO算法與PSO算法迭代過程

算法最優(yōu)解首次達到最優(yōu)解的迭代次數(shù)達到最優(yōu)解的迭代次數(shù)SA-PSO3.35410129PSO3.33955191

表6　SA-PSO算法與PSO算法結(jié)果對比

圖3　備件布局位置

4　結(jié)　語

本文提出一種SA-PSO算法用于求解備件車裝載布局優(yōu)化問題。由于基本PSO算法容易陷入局部最優(yōu)，故采用了CFPSO算法，壓縮因子能有效地避免所以粒子均飛向局部極值點，增強了算法的局部尋優(yōu)能力，這種調(diào)整方式只需選取合適的參數(shù)，就可保證PSO算法收斂。SA算法在尋優(yōu)過程能有效地避免陷入局部極值，在一定條件下一定能收斂于全局最優(yōu)解。SA-PSO算法在優(yōu)化過程中以依照突跳概率接受接近全局極值的次優(yōu)解，避免陷入局部極值，實現(xiàn)了全局尋優(yōu)。從理論分析及布局優(yōu)化實例結(jié)果可以看出，本文提出的SA-PSO算法用來解決備件車布局問題時，能綜合考慮備件車空間利用率、備件合重心對行車安全性的影響和備件取用效率，得到較好的布局結(jié)果。

[1] 張蕊，袁立峰，汪凱蔚.備件優(yōu)化理論分析與應(yīng)用研究[J].裝備環(huán)境工程，2012，9(5)：52-55.

[2] 王明亮，余勃彪.裝甲裝備器材倉庫備件庫存優(yōu)化方法[J].兵工自動化，2013，32(8)：21-24.

[3] 田繼亮.設(shè)備維修過程中備件管理多目標(biāo)優(yōu)化技術(shù)研究[D].西安：西安電子科技大學(xué)，2013.

[4] Garey M R，Johnson D S.Computer and Intractability：A guide to the Theory of NP-Completeness[M].New York：Freeman，1979：16-20.

[5] 張泓，李愛平，劉雪梅.基于多目標(biāo)改進蟻群算法的三維混合布局方案設(shè)計[J].農(nóng)業(yè)機械學(xué)報，2010，41(7)：191-197.

[6] 祝恒云，葉文華.模擬退火粒子群算法在動態(tài)單元布局中的應(yīng)用[J].中國機械工程，2009，20(2)：181-185.

[7] 周娜，宓為建，徐子奇，等.基于改進型自適應(yīng)遺傳算法求解設(shè)備多行布局問題[J].上海交通大學(xué)學(xué)報，2013，47(12)：1924-1929.

[8] Kennedy J，Eberhart R C.Particle swarm optimization[C]//Proc of IEEE Int’l Conf Neural Networks.Los Alamitos，CA：IEEE Computer Society Press，1995：1942-1948.

[9] Szykman S，Cagan J.A simulated annealing-based approach to three-dimensional component packing[J].Transaction of ASME，1995，117：308-314.

[10] 王正元,曹繼平,朱昱,等.考慮維修能力的戰(zhàn)時備件資源配置方法研究[J].兵工學(xué)報,2014,35(5)：719-724.

[11] 楊仕美,石忠義,翟旭升,等.基于重要度的航材備件庫存綜合優(yōu)化模型[J].火力與指揮控制,2014,39(8)：109-113.

[12] 郭源源，王謙，梁峰.基于粒子群優(yōu)化算法的車間布局設(shè)計[J].計算機集成制造系統(tǒng)，2012，18(11)：2476-2484.

[13] 劉衍民.一種求解約束優(yōu)化問題的混合粒子群算法[J].清華大學(xué)學(xué)報:自然科學(xué)版，2013，53(2)：242-246.

[14] 范文,余隋懷,王文軍,等.蟻群算法求解人機布局優(yōu)化問題[J].機械科學(xué)與技術(shù),2013,32(7)：955-962.

[15] Wu Hao，Zuo Hongfu.Using genetic /simulated annealing algorithm to solve disassembly sequence planning[J].Journal of Systems Engineering and Electronics，2009，20(4)：906-912.

[16] 王帥旗.船舶駕駛室布置人機工程設(shè)計及其應(yīng)用[D]哈爾濱：.哈爾濱工程大學(xué)，2013.

MULTI-OBJECTIVE OPTIMISATION DECISION FOR SPARE PARTS LAYOUT IN EQUIPMENT MAINTENANCE PROCESS

Guo LuYang YunWang WeiLiu Xiaowei

(SchoolofAirDefenseandAnti-missileInstitute,AirForceEngineeringUniversity,Xi’an710051,Shaanxi,China)

In order to ensure accurate,timely and efficient spare parts access in equipment maintenance process,we put forward the problem of loading and layout optimisation for spare parts car.In light of this issue we built the mathematical model of spare parts layout optimisation,took the bearing volume,load capacity and gravity centre of the spare car as the constraint conditions,and took into account comprehensively the space utilisation of spare parts car,the influence of spare parts’ combined gravity centres on driving safety and the spare parts’ access efficiency as the objective functions.According to the particularity of spare parts layout model and based on the idea of simulated annealing algorithm,we combined them with the particle swarm optimisation with constrict factor and applied it in actual example to calculate the layout solution.We also compared the calculation result of this hybrid algorithm with that of the basic particle swarm optimisation algorithm.Results showed that to use hybrid particle swarm optimisation algorithm can obtain better loading and layout optimisation scheme,it achieves the goals of making full use of spare car’s loading space,good in safety and high access efficiency.

Spare carLayoutParticle swarm optimisationSimulated annealing algorithmConstrict factor

2015-07-03。國家自然科學(xué)基金項目(51075395);國家高技術(shù)研究發(fā)展計劃項目(2013AA040604)。郭璐，碩士生，主研領(lǐng)域：機械結(jié)構(gòu)優(yōu)化設(shè)計。楊云，副教授。王崴，副教授。劉曉衛(wèi)，講師。

TP311

A

10.3969/j.issn.1000-386x.2016.10.052