?

基于改進邊際優(yōu)化算法的備件配置研究*1

董琪1a，徐廷學(xué)1b，楊繼坤2，趙建忠1b

(1．海軍航空工程學(xué)院,a．研究生管理大隊，b．兵器科學(xué)與技術(shù)系，山東 煙臺264001；

2．中國人民解放軍92493部隊，遼寧 葫蘆島125000)

摘要：針對傳統(tǒng)邊際優(yōu)化算法在解決備件配置優(yōu)化問題存在運算效率不高的問題，提出了基于改進邊際優(yōu)化算法的備件優(yōu)化配置方法。在傳統(tǒng)邊際優(yōu)化算法思想的基礎(chǔ)上，提出了改進的邊際優(yōu)化算法，通過引入備件短缺系數(shù)，提高了算法的優(yōu)化效率。給出了該優(yōu)化算法的設(shè)計思想和優(yōu)化流程，并在理論上分析了算法的優(yōu)化效率。通過算例數(shù)值結(jié)果的分析，驗證了算法在保持最優(yōu)解精度的情況下，大幅提高了運算效率，為備件庫存配置優(yōu)化提供了指導(dǎo)。

關(guān)鍵詞：備件；優(yōu)化配置；邊際優(yōu)化算法；系統(tǒng)可用度；備件短缺系數(shù)；庫存系統(tǒng)

0引言

隨著武器裝備規(guī)模、復(fù)雜性的不斷增加，裝備保障技術(shù)，特別是影響大規(guī)模、復(fù)雜裝備系統(tǒng)達到戰(zhàn)備完好性要求的備件優(yōu)化配置研究顯得越來越重要。通過構(gòu)建有效的分析模型以確定裝備系統(tǒng)的最優(yōu)備件配置方案是備件優(yōu)化配置技術(shù)的核心內(nèi)容。統(tǒng)計表明，在相同的情況下，合理的備件配置模型確定的庫存水平與部隊慣用的單項法相比，可降低40%～50%[1]。許多學(xué)者也通過不同的方式驗證了優(yōu)化配置建模在備件配置應(yīng)用中的優(yōu)點[2-3]。

一般來說，對裝備系統(tǒng)庫存問題的求解普遍采用多品種備件多級最優(yōu)庫存建模，該模型通常根據(jù)不同的假設(shè)條件，在多級多站點的保障系統(tǒng)結(jié)構(gòu)下，以系統(tǒng)可用度為約束條件、配置費用最少為目標或者以配置費用為約束條件、系統(tǒng)可用度最大為目標建立模型并確定備件的配置方案。這些模型的求解常采用METRIC法(multi-echelon technique for recovery item control)。該方法的核心思想是通過邊際優(yōu)化算法對各級各站點倉庫進行備件分配，從而確定出各級各站點倉庫的備件初始配置量[4]。

目前，國內(nèi)外學(xué)者針對備件優(yōu)化配置及其優(yōu)化算法開展了大量研究，取得了較大的進展。文獻[5-7]從備件保障系統(tǒng)結(jié)構(gòu)的角度，建立了從兩級到多級的備件配置優(yōu)化模型。解決多級保障系統(tǒng)備件配置優(yōu)化問題，選擇合理的優(yōu)化算法是關(guān)鍵。常見的用以解決METRIC模型的優(yōu)化算法是邊際優(yōu)化算法，盡管文獻[8-9]利用分層思想對邊際優(yōu)化算法進行了改進，但該方法將裝備系統(tǒng)作為串聯(lián)結(jié)構(gòu)進行處理，而隨著裝備結(jié)構(gòu)復(fù)雜性的增加，該方法具有一定局限性。也有文獻利用相關(guān)回歸方法[10]及拉

格朗日乘子法[11]對模型進行優(yōu)化。另外，以遺傳算法[12]、粒子群算法[13]、神經(jīng)網(wǎng)絡(luò)[14]等為代表的智能算法也越來越多應(yīng)用于解決備件配置優(yōu)化問題，這些方法雖然運算效率較高，但其優(yōu)化分析過程不直觀，無法為決策者提供更多直觀輔助信息。相比之下，邊際優(yōu)化算法在這方面有著無可比擬的優(yōu)勢。常見的備件優(yōu)化軟件如OPUS10，V-METRIC等[1]均基于邊際優(yōu)化算法開發(fā)的，但該算法存在著計算量大，運算效率低的缺點。

綜上所述，本文針對邊際優(yōu)化算法的運算效率偏低，通過建立基于METRIC的多級備件配置模型，在分析傳統(tǒng)邊際優(yōu)化算法的基本原理的基礎(chǔ)上，引入了備件短缺系數(shù)，提出了改進的邊際優(yōu)化算法，并給出了基本原理和優(yōu)化步驟。

1基于METRIC的多級備件配置模型

1.1問題描述及符號說明

多級備件保障系統(tǒng)通常e個保障層級，其中e=0,1,…,E；在第e層級上存在n(n=1,2,…,Ne)個倉庫站點；M表示備件保障系統(tǒng)所保障的裝備數(shù)量；i(i=1,2,…,I)為所保障的備件種類，如圖1所示。構(gòu)建備件配置模型的目的是確定各層級倉庫關(guān)于各類備件的庫存水平，以滿足約束條件下的系統(tǒng)庫存目標最優(yōu)。

圖1　多級備件保障系統(tǒng)網(wǎng)絡(luò)結(jié)構(gòu)圖Fig.1　Supply network of multi-echelon spare parts system

文中所用到的其他符號說明如下：

γ：備件短缺系數(shù)；

Zi：備件i在一個裝備上的機用數(shù)；

C：系統(tǒng)備件配置總費用。

1.2基本假設(shè)

根據(jù)以上描述，結(jié)合METRIC模型的基本假設(shè)條件，現(xiàn)作假設(shè)如下：

(1) 保障系統(tǒng)內(nèi)周轉(zhuǎn)的備件均為可修復(fù)備件，其維修過程即為備件的周轉(zhuǎn)過程；

(2) 各層級倉庫對備件的需求服從獨立的泊松分布，其維修分布滿足Palm定理；

(3) 備件保障系統(tǒng)不存在備件橫向轉(zhuǎn)運；

(4) 各級倉庫的庫存檢查策略為(s,s-1)策略；

(5) 整個備件保障系統(tǒng)的供應(yīng)鏈守恒，即無備件報廢；

(6) 不同種類備件的短缺代價相同；

(7) 各級維修站點采用“先到先修”的原則處理失效備件，且維修能力無限。

1.3模型構(gòu)建

根據(jù)METRIC建模理論，首先計算在周轉(zhuǎn)期t內(nèi)，備件需求服從泊松分布條件下，保障層級e上保障站點n關(guān)于備件i的待收庫備件數(shù)的穩(wěn)態(tài)概率分布：

(1)

當t時刻，保障站點的庫存量小于備件需求量時，則會出現(xiàn)備件短缺的情況，短缺量為

(2)

由于備件配置的目標是確定各倉庫最優(yōu)的穩(wěn)態(tài)庫存水平，因此，需要計算保障層級e上保障站點n關(guān)于備件i的期望短缺量，如下：

(3)

當多級備件保障系統(tǒng)維修建模過程可參考文獻[4,8]構(gòu)建。

METRIC模型的優(yōu)化配置目標函數(shù)一般是系統(tǒng)可用度函數(shù)，也有學(xué)者使用備件期望短缺量作為優(yōu)化目標。通過系統(tǒng)可用度可以更好分析備件方案的費效全過程，更有利于說明不同優(yōu)化算法的優(yōu)化效果，因此，本文采用系統(tǒng)可用度為系統(tǒng)效能指標。

由裝備可用度定義，在備件期望短缺量計算公式的基礎(chǔ)上得到了系統(tǒng)可用度表達式：

(4)

由此可知，備件保障方案的確定需要綜合考慮系統(tǒng)可用度、備件期望短缺數(shù)、備件需求、備件延誤等因素。

于是，構(gòu)建系統(tǒng)備件配置模型為

目標函數(shù)

(5)

約束條件

s.t.A0≥A,

(6)

式中：Ci為第i個備件的配置費用；A為規(guī)定的系統(tǒng)可用度要求。

由式(5)，(6)組成的系統(tǒng)備件配置模型屬于典型的METRIC模型。

2基于邊際優(yōu)化算法的備件配置優(yōu)化

傳統(tǒng)的邊際優(yōu)化算法屬于一種漸進的優(yōu)化方法。其基本思想為[15]：首先，將因變量變化值與自變量變化值的比值稱為邊際值；其次，根據(jù)本文實際，確定邊際成本與邊際收益，以及模型控制變量，本文所研究備件優(yōu)化問題的控制變量顯然為系統(tǒng)需配置的備件數(shù)量；其次，通過對控制變量加1，計算各邊際單元每單位控制變量總效益的增量(即邊際效益)，根據(jù)邊際效益分析，確定需增加備件配置量的單元，并對該單元備件配置量加1；最后，當滿足條件時，迭代停止。

針對本文模型和實際條件，具體應(yīng)用步驟如下：

步驟1： 將式(4)進行取對數(shù)處理，將系統(tǒng)可用度轉(zhuǎn)化為備件短缺量之和，便于后期計算：

(7)

步驟2： 初始化各站點備件庫存量，一般在初始階段各站點庫存量為0。

步驟3： 計算每次迭代的邊際效益值：

(8)

步驟5： 將步驟4結(jié)束時的庫存量作為下一次迭代的初始庫存量，按照步驟3和步驟4反復(fù)迭代，直到滿足模型中系統(tǒng)可用度要求為止。

3改進的邊際優(yōu)化算法

傳統(tǒng)邊際優(yōu)化算法的原理類似于“貪婪算法”，通過模型通過邊際優(yōu)化算法達到目標最優(yōu)解時，其計算量由備件種類數(shù)、倉庫站點數(shù)量和約束條件要求共同決定，如果一個庫存系統(tǒng)1 000種備件，各級倉庫共100個，那么利用邊際優(yōu)化算法進行一次迭代至少需要1×105次計算，當求得最優(yōu)解時，需要多百萬或千萬次計算[16]。

針對傳統(tǒng)邊際優(yōu)化算法存在計算效率偏低的確定，本文提出了改進的邊際優(yōu)化算法。其基本思想是：首先，通過引入備件短缺系數(shù)確定各倉庫備件的初始庫存量；其次，每一次迭代都來源于前一次的“批量”計算，這種“批量”是與傳統(tǒng)邊際算法相對應(yīng)的，由于傳統(tǒng)邊際優(yōu)化算法每一次迭代都是在站點現(xiàn)有庫存量基礎(chǔ)上加1進行決策，而改進算法通過備件短缺系數(shù)在站點現(xiàn)有庫存量基礎(chǔ)上加m，m的取值是由備件短缺系數(shù)和現(xiàn)有庫存量共同決定的。這樣，改進的優(yōu)化算法就可以簡化計算，提高計算效率。

改進的邊際優(yōu)化算法步驟為：

改進的邊際優(yōu)化算法流程如圖2所示。

4算例分析

某裝備保障系統(tǒng)為三級保障體制，各級保障結(jié)構(gòu)及關(guān)系如圖3所示。該保障系統(tǒng)兩級之間的備件周轉(zhuǎn)期均為120天，采用的修理方式為換件維修，裝備備件相關(guān)參數(shù)如表1所示,其中C為各倉庫站點配置一個備件的費用(單位為元)；D為各倉庫站點關(guān)于備件的年需求量；MTTR為各維修機構(gòu)關(guān)于備件的平均修復(fù)時間(單位為天)。

改進的邊際優(yōu)化算法的優(yōu)點在于保持模型精度的同時可有效降低算法的迭代次數(shù)，為驗證本文算法的效率，且不失一般性，將控制參數(shù)取不同值，得到多種不同條件下模型的優(yōu)化結(jié)果，并與同等條件下傳統(tǒng)邊際優(yōu)化算法進行對比。

圖2　改進邊際優(yōu)化算法流程圖Fig.2　Flow chart of the improved marginal algorithm

圖3　某裝備保障系統(tǒng)結(jié)構(gòu)圖Fig.3　Supply network of the equipment support system

站點e=0n=1e=1n=1e=1n=2e=2n=1e=2n=2e=2n=3e=2n=4e=2n=5e=2n=6C757575100125100125100125D7003002001251751257512575MTTR903030303030303030

本文采用的備件配置模型為METRIC模型，該模型的控制參數(shù)為備件配置費用C、備件需求率λ、系統(tǒng)可用度A0，其中備件需求率λ可由備件年需求量D求得。首先將前2個控制參數(shù)取不同值，取值的原則是用(0，-，+)分別表示控制參數(shù)取原值不變，原值減小50%，原值增加50%，于是可以得到9種不同的條件。在此基礎(chǔ)上，令優(yōu)化模型的約束條件，即系統(tǒng)可用度要求A分別取0.90，0.95，0.99，同時取γ=0.25，EBOmin=30。利用改進的邊際優(yōu)化算法計算得到系統(tǒng)的配置總費用，以及算法的迭代次數(shù)如表2所示，其中系統(tǒng)迭代次數(shù)由ITER表示，系統(tǒng)配置總費用由Cs表示。

表2　改進邊際優(yōu)化算法計算結(jié)果

由傳統(tǒng)邊際優(yōu)化算法計算得到結(jié)果如表3所示。

表3　傳統(tǒng)邊際優(yōu)化算法計算結(jié)果

由表1和表2計算結(jié)果對比可知，改進的邊際優(yōu)化算法可在保持優(yōu)化結(jié)果精度的前提下，大幅降低算法的迭代次數(shù)，提高計算效率。計算結(jié)果對比如圖4所示，其中曲線ITER1，ITER2，ITER3分別表示可用度要求在0.90，0.95，0.99時，改進算法與傳統(tǒng)算法在9種條件下達到最優(yōu)解的迭代次數(shù)之比；曲線C1,C2,C3分別表示可用度要求在0.90,0.95,0.99時，改進算法與傳統(tǒng)算法在9種條件下達到最優(yōu)解之比。

圖4　計算結(jié)果對比Fig.4　Experiment results of various algorithms

從圖4可以看出，當γ取0.25，在9種不同參數(shù)組合的條件下，改進的邊際優(yōu)化算法求得最優(yōu)解的迭代次數(shù)最多為傳統(tǒng)邊際優(yōu)化算法迭代次數(shù)的30%，而改進算法與傳統(tǒng)算法求得的最優(yōu)解精度誤差保持在0.8%內(nèi)。因此，改進的邊際優(yōu)化算法明顯提高了運算效率，且保證了求得最優(yōu)解的精度。

改進的邊際優(yōu)化算法通過引入備件短缺系數(shù)γ，提高了運算效率，而γ的取值對于算法至關(guān)重要。因此，需分析不同γ值對算法優(yōu)化效果的影響。取γ分別為0.25,0.5,0.75，且保持算例其他參數(shù)不變，得到9種條件下優(yōu)化結(jié)果與傳統(tǒng)算法優(yōu)化結(jié)果的比率，如圖5所示。圖中計算結(jié)果(包括迭代次數(shù)和最優(yōu)解)的均值比率由I-Ave和C-Ave表示、計算結(jié)果中最小值的比率分別由I-Min和C-Min表示，以及最大值的比率分別用I-Max和C-Max表示。

圖5　不同γ值下計算結(jié)果對比Fig.5　Experiment results with various γ

由圖5分析可知，隨著γ從0.25增至0.75，所求得最優(yōu)解的迭代次數(shù)由傳統(tǒng)邊際算法迭代次數(shù)的20.3%逐漸降至4%，計算效率逐漸增加，而且當γ取0～0.5時，計算效率提升效果比γ取0.5～1時更加明顯。在最優(yōu)解求解精度方面，隨著γ從0.25增至0.75，精度逐漸下降；當γ=0.25和0.50時，改進邊際優(yōu)化算法得到的最優(yōu)解均值與傳統(tǒng)邊際算法的偏差均控制在1%以內(nèi)；但當γ增至0.75時，偏差增大到43.8%，明顯高于γ=0.25和0.50時的計算結(jié)果。綜上所述，γ的取值應(yīng)根據(jù)計算時間和計算精度的要求進行權(quán)衡。在對精度要求不高，而時間要求較高的工程領(lǐng)域，γ可取0.50～0.75之間的數(shù)值；若對計算精度要求較高，則γ應(yīng)取0～0.50之間的數(shù)值。從以上分析來看，對計算時間和精度均有較高要求時，γ取0.50附近的數(shù)值最為合理，以本文結(jié)果為例，計算時間和精度偏差的均值分別控制在6%和1%，優(yōu)化效果明顯。

5結(jié)束語

本文采用系統(tǒng)優(yōu)化效能優(yōu)化思想，在基于METRIC模型的基礎(chǔ)上構(gòu)建了以系統(tǒng)可用度為約束條件，以系統(tǒng)備件配置總費用為優(yōu)化目標的裝備備件多級配置模型，并提出了改進的邊際優(yōu)化算法。算例表明了改進邊際優(yōu)化算法在適用于多級備件保障系統(tǒng)的同時，明顯提升了運算效率，其有效性和實用性得到增強。未來可進一步分析該算法在其他條件下備件配置模型應(yīng)用的可行性，例如考慮同級倉庫間橫向調(diào)撥、備件串修的情況等。

參考文獻：

[1]任敏，陳全慶，沈震．備件供應(yīng)學(xué)[M]．長沙：國防工業(yè)出版社，2013：140-145.

REN Min, CHEN Quan-qing, SHEN Zhen. The Theory of Spare Parts Supplies [M]. Changsha: National Defense Industry Press, 2013: 140-145.

[2]王乃超，康銳．基于備件保障概率的多級庫存優(yōu)化模型[J]．航空學(xué)報，2009，30(6)：1043-1047.

WANG Nai-chao, KANG Rui. Optimization of Multi-Echelon Repariable Item Inventory Systems with Fill Rate as Objective [J]. Acra Aeronautica ET Astronautica Sinica, 2009, 30(6): 1043-1047.

[3]郭強,張振友,黃立坡,等．基于METRIC理論的防空武器系統(tǒng)備件配置優(yōu)化[J]．火力與指揮控制，2011，36(8)：100-106.

GUO Qiang, ZHANG Zhen-you, HUANG Li-po, et al. Research on Optimization of Disposition of Spare Parts for Air Denfence Weapon System Based on Metric Theory[J]. Fire Control & Command Control, 2011, 36(8): 100-106.

[4]SHERBROOKE CRAIG C. Optimal Inventory Modeling of Systems: Multi-Echelon Techniques[M]. New York: Springer Science Business Media, 2004.

[5]周偉，劉亞杰，郭波，等．基于兩級供應(yīng)關(guān)系的武器裝備貴重件初始配置模型[J]．系統(tǒng)工程理論與實踐，2011，31(6)：1056-1061.

ZHOU Wei, LIU Ya-jie, GUO Bo, et al. Initial Configuration Model About the Valuable Parts of Weapon System Based on Two-Class Supply Relationship [J]. System Engineering- Theory & Practice, 2011, 31(6):1056-1061.

[6]付興方，李繼軍，李宗植．基于兩級供應(yīng)關(guān)系的可修復(fù)航材存儲策略模型研究[J]．系統(tǒng)工程理論與實踐，2004，24(2)：111-115.

FU Xing-fang, LI Ji-jun, LI Zong-zhi. A Stock Strategy Model for Restorable Air Material Based on Two-level Providing Condition [J]. System Engineering- Theory & Practice, 2004, 24(2): 111-115.

[7]張琳，趙杰，唐超，等．可維修備件庫存模型研究[J]．兵工學(xué)報，2009，30(11)：90-94.

ZHANG Lin, ZHAO Jie, TANG Chao, et al. Research on the Echelon Inventory Model of the Repairable Spares [J]. Acta ArmamentarII, 2009, 30(11): 90-94.

[8]阮旻智，李慶民，李承，等．改進的分層邊際算法優(yōu)化備件的初始配置方案[J]．兵工學(xué)報，2012，33(10)：1251-1257.

RUAN Min-zhi, LI Qing-min, LI Cheng, et al. Improved-Layered-Marginal Algorithm to Optimize Initial Spare Part Configuration Project[J]. Acta ArmamentarII, 2012, 33(10): 1251-1257.

[9]趙建忠，李海軍，葉文，等．改進系統(tǒng)備件滿足率約束下的備件優(yōu)化配置建模[J]．兵工學(xué)報，2013，34(9)：1187-1192.

ZHAO Jian-zhong, LI Hai-jun, YE Wen, et al. Optimization Configuration Modeling of Spare Parts Under Constraint of Improved System Spare Part Fill Rate[J]. Acta ArmamentarII, 2013, 34(9): 1187-1192.

[10]LEE H L. A Multi-Echelon Inventory Model for Repairable Items with Emergency Lateral Transshipments [J]. Management Science, 1987, 33(10): 1302-1316.

[11]AL-RIFAI M H, ROSSETTI M D. An Efficient Heuristic Optimization Algorithm for a Two-Echelon (R, Q) Inventory System[J]. International Journal of Production Economics, 2007，109(2): 195-213.

[12]SARANGA H, KUMAR U D. Optimization of Aircraft Maintenance Support Infrastructure Using Genetic Algorithms-level of Repair Analysis[J]. Ann Oper Res, 2006, 143(1): 91-106.

[13]劉少偉，金榮，張琳．用粒子群算法優(yōu)化裝備初始備件量[J]．空軍大學(xué)學(xué)報:自然科學(xué)版，2008，9(1)：46-49.

LIU Shao-wei,JIN Rong, ZHANG Lin. The Optimization of Initial Spare Parts Based on Particle Swarm Optimization Algorithm[J]. Journal of Air Force Engineering University:Natural Science ed, 2008, 9(1): 46-49.

[14]劉剛，鐘小軍，董鵬．基于遺傳算法和神經(jīng)網(wǎng)絡(luò)的艦船電子裝備備件優(yōu)化模型研究[J]．艦船科學(xué)技術(shù)，2008，30(5)：138-142.

LIU Gang, ZHONG Xiao-jun, DONG Peng. Research on Warship Electronic Equipment Spare Parts Optimize Model Based on Genetic Algorithm and Neural Network[J].Ship Science and Technology, 2008, 30(5): 138-142.

[15]蔡澤明，康銳，龍軍．面向系統(tǒng)優(yōu)化的備件動態(tài)配置方法[J]．系統(tǒng)工程與電子技術(shù)，2010，32(11)：2363-2366.

CAI Ze-ming, KANG Rui, LONG Jun. System Optimization-Oriented Dynamic Spares Configuration Method[J]. System Engineering and Electronics, 2010, 32(11): 2363-2366.

[16]RAPPOLD J A, TCHERNEV N. Designing Multi-Echelon Service Parts Networks with Finite Repair Capacity[J].European Journal of Operational Research, 2009, 199(3): 781-792.

Improved Marginal Algorithm for Spare Parts Configuration

DONG Qi1a, XU Ting-xue1b, YANG Ji-kun2, ZHAO Jian-zhong1b

(1．Naval Aeronautical and Astronautical University, a. Graduate Students’ Brigade,b.Department of Ordnance Science and Technology,Shandong Yantai 264001，China；2.PLA，No. 92493 Troop, Liaoning Huludao 125000, China)

Abstract:An improved marginal algorithm for spare parts configuration is proposed to overcome the traditional marginal algorithm of poor efficiency in spare parts configuration. The improved marginal algorithm that introduced fraction of the EBO (expected backorder) of qualified spare parts is proposed, and the computational efficiency is improved. The detailed design and optimization of the proposed algorithm is given, and the optimization efficiency is analyzed in theory. The calculated result of an example shows that the efficiency of improved marginal optimization algorithm is much higher than that of traditional algorithm with high accuracy. The research result can provide guidance for spare parts optimization configuration in engineering application.

Key words:spare part; spare optimization; marginal optimization algorithm; system availability; expected backorder(EBO) index; inventory system

中圖分類號：E92；TP391.9

文獻標志碼：A

文章編號：1009-086X(2015)-05-0198-07

doi:10.3969/j.issn.1009-086x.2015.05.032

通信地址：264001山東省煙臺市芝罘區(qū)二馬路188號206教研室E-mail：lance0627@163.com

作者簡介：董琪(1986-)，男，河南平頂山人。博士生,研究方向為裝備綜合保障建模與仿真。

*收稿日期：2014-09-17；修回日期：2015-02-06