裝備維修過程中備件布局的多目標優化決策

郭　璐　楊　云　王　崴　劉曉衛

(空軍工程大學防空反導學院　陜西 西安 710051)

?

裝備維修過程中備件布局的多目標優化決策

郭璐楊云王崴劉曉衛

(空軍工程大學防空反導學院陜西 西安 710051)

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

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

0　引　言

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

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

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

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

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

1　備件布局優化模型

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

圖1　備件車坐標系

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

1.1基于備件車空間及載重約束的數學模型

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

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

(10)

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

1.2基于備件車行車安全性的數學模型

(11)

(12)

(13)

(14)

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

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

1.3基于備件取用效率的數學模型

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

(1) 重要性原則

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

在備件的布局序列中，重要性越高的備件則在布局序列中越靠前。備件pi的重要性權值用Pmi表示，由此構造備件重要性子目標函數：

(15)

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

(2) 使用頻率原則

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

對于使用頻率的量化可采用統計方法，備件pi的使用頻率權值用Fri表示。使用頻率越高的備件在布局序列中的位置越靠前，由此得使用頻率子目標函數：

(16)

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

(3) 相關性原則

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

表1　備件相關性

兩備件間相關性越大，在布局序列中的位置越靠近，由此可得相關性子目標函數：

(17)

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

(4) 目標函數

綜合考慮上述三種布局原則及各原則之間的關系，通過加權法將以上三個子目標函數組合，可構建如下備件布局優化目標函數：

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

(18)

式(18)中，ωi(i=1,2,3)為各子目標函數的權重系數，可根據維修任務及待裝備件的特點對子目標權重值加以調整，以適應實際的需求。

1.4備件車裝載布局優化的數學模型

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

(19)

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

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

2.1基于模擬退火的粒子群優化算法

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

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應用混合粒子群算法的備件車布局

(1) 粒子群初始化

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

(2) 適應度函數

針對此備件車布局，適應度函數可表示為F=maxZ。由此可知，適應度值越大，目標函數值越大，求得的布局方案越滿足要求。

(3) 停止規則

算法運行之前會設定一個迭代次數，若算法運行到最大迭代次數，則迭代結束，退出程序；或者算法運行到一定程度，適應度函數值連續迭代30步保持平穩，則停止循環，退出程序。退出后即可得到適應度值最優的布局結果。

2.3問題求解和算法流程設計

SA-PSO算法尋優步驟如下：

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

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

步驟3重復執行以下步驟。

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

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

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

步驟5執行最優選擇操作，更新種群gbest。

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

3　算例分析

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

表2　待布備件重要性及使用頻率權值

表3　待布備件相關性

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

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

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

算法最優解首次達到最優解的迭代次數達到最優解的迭代次數SA-PSO3.35410129PSO3.33955191

表6　SA-PSO算法與PSO算法結果對比

圖3　備件布局位置

4　結　語

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

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

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

[3] 田繼亮.設備維修過程中備件管理多目標優化技術研究[D].西安：西安電子科技大學，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] 張泓，李愛平，劉雪梅.基于多目標改進蟻群算法的三維混合布局方案設計[J].農業機械學報，2010，41(7)：191-197.

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

[7] 周娜，宓為建，徐子奇，等.基于改進型自適應遺傳算法求解設備多行布局問題[J].上海交通大學學報，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] 王正元,曹繼平,朱昱,等.考慮維修能力的戰時備件資源配置方法研究[J].兵工學報,2014,35(5)：719-724.

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

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

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

[14] 范文,余隋懷,王文軍,等.蟻群算法求解人機布局優化問題[J].機械科學與技術,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] 王帥旗.船舶駕駛室布置人機工程設計及其應用[D]哈爾濱：.哈爾濱工程大學，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。國家自然科學基金項目(51075395);國家高技術研究發展計劃項目(2013AA040604)。郭璐，碩士生，主研領域：機械結構優化設計。楊云，副教授。王崴，副教授。劉曉衛，講師。

TP311

A

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