基于貪婪算法的車輛器材倉庫保障水平優(yōu)化研究

張志鵬，張大鵬，王鳳忠

（1.軍事交通學(xué)院 學(xué)員旅，天津 300161；2.軍事交通學(xué)院 軍用車輛系，天津 300161）

基于貪婪算法的車輛器材倉庫保障水平優(yōu)化研究

張志鵬1，張大鵬2，王鳳忠2

（1.軍事交通學(xué)院 學(xué)員旅，天津 300161；2.軍事交通學(xué)院 軍用車輛系，天津 300161）

重點分析了庫存器材保障率和車輛器材倉庫保障水平的相關(guān)概念，構(gòu)建了車輛器材倉庫保障水平優(yōu)化模型，并采用蒙特卡洛仿真結(jié)合貪婪算法得出了相對最優(yōu)解。對解決車輛器材倉庫采購策略和庫存優(yōu)化問題有重要的參考意義和應(yīng)用價值。

器材保障率；車材倉庫保障水平；蒙特卡洛仿真；貪婪算法

1 引言

車輛器材倉庫保障水平是實現(xiàn)我軍車輛器材有效保障及提升部隊?wèi)?zhàn)斗力的關(guān)鍵因素。而車輛器材倉庫保障水平的高低由倉庫庫存結(jié)構(gòu)是否合理來決定。目前，全軍車輛器材庫存結(jié)構(gòu)不合理的問題十分嚴(yán)峻，而且造成這種現(xiàn)象的原因是多方面的[1]，同時對車輛器材優(yōu)化控制理論和方法的研究也十分缺乏。因此，對車輛器材倉庫保障水平進行研究，具有十分重要的意義。

2 相關(guān)概念的辨析

2.1 庫存器材保障率

庫存器材保障率是指一件隨機的車輛器材需求得到滿足的概率的期望值，這是基于對車輛器材倉庫的保障水平評價提出的，并不涉及庫存器材在車輛上的關(guān)系。這個指標(biāo)不僅能夠有效地反映車輛的可靠度，還能夠反映車輛器材倉庫的保障水平[2-3]。通常情況下，庫存器材的保障率用車輛器材倉庫的保障水平來計算：

2.2 器材保障水平

表1 器材的需求密度函數(shù)及實際請領(lǐng)數(shù)密度函數(shù)

則其保障水平L為：

因此，整個車輛器材倉庫的保障水平為：

顯然，車輛器材倉庫的保障水平WL也是一個隨機變量，對于求解隨機變量WL的期望值只能依據(jù)各器材的需求密度函數(shù)進行大量仿真，用保障水平的平均值作為期望值的估計值。其保障水平的期望值為：

3 車輛器材倉庫保障水平優(yōu)化模型的構(gòu)建

3.1 確定優(yōu)化目標(biāo)

車輛器材倉庫保障水平優(yōu)化的目標(biāo)是在費用約束的條件下，盡可能地提高各類器材的保障水平，即實現(xiàn)車輛器材倉庫保障水平的最大化。由于經(jīng)費限額的原因，在進行車輛器材庫存優(yōu)化時，對于不同種類的器材必須采取不同的控制方式，器材的重要度越高，對車輛器材保障水平影響也越大[4]。

3.2 模型建立條件

（1）本文中的車輛器材庫存優(yōu)化是在經(jīng)費一定的情況下，使車輛器材的保障水平實現(xiàn)最大化。

（2）本文中所提及的某種器材備件數(shù)是指在實現(xiàn)車輛器材保障水平最大化的條件下需要購買的器材數(shù)量，即優(yōu)化后應(yīng)儲存量或者優(yōu)化后的庫存量。

（3）根據(jù)調(diào)研資料統(tǒng)計，對于數(shù)量只占庫存總量約10%，而其價值卻占庫存總價值70%的此類器材，其壽命服從指數(shù)分布，需求量服從泊松分布。本文重點研究的也是此類器材。

3.3 建立優(yōu)化模型

假設(shè)在一定的經(jīng)費預(yù)算內(nèi)，要實現(xiàn)車輛器材倉庫保障水平最大化，這里的車輛器材倉庫保障水平就是庫存器材的保障率。對于某個車輛器材倉庫來說，就是要在費用約束的條件下使保障率達(dá)到最大。首先確定車輛器材倉庫每一種器材的最低庫存，通過不斷增加購置備件費用，使車輛器材倉庫保障水平得以增加。把器材資金的分配問題抽象為線性約束最優(yōu)化問題，即：

式中，i=1,2,…,n，Pi—第i種器材的價格，是已知常數(shù)；

δ—單件器材保障率，k1,k2—是給定的已知常數(shù)。由于車輛器材倉庫保障水平是隨機變量，因此本模型為不確定規(guī)劃中的隨機期望值模型，而且也是多變量線形約束的組合優(yōu)化。

車輛器材倉庫保障水平期望值E( ) WL是衡量倉庫庫存是否優(yōu)良的重要參數(shù)。由于表達(dá)式比較復(fù)雜，而且還存在隨機變量，很難運用解析的方法來計算。因此，利用隨機模擬技術(shù)蒙特卡洛仿真來求得相對最優(yōu)解。

蒙特卡洛仿真是一種通過隨機變量的統(tǒng)計試驗和隨機模擬仿真來求解數(shù)學(xué)、物理等技術(shù)問題近似解的數(shù)值方法，它是依據(jù)概率論和數(shù)理統(tǒng)計為基礎(chǔ)的處理方

法。蒙特卡洛方法的求解步驟如下：

（1）構(gòu)造概率模型；

（2）實現(xiàn)從已知概率分布的抽樣；

（3）建立各種統(tǒng)計量的估計。

利用蒙特卡洛模擬技術(shù)意味著在比較兩個可行解時，要通過大量的模擬才能得出哪一個是更接近最優(yōu)的可行解[5]。理想的解法是把所有的可行解例舉出來，但是對于組合優(yōu)化問題，隨著系統(tǒng)規(guī)模的擴大，例舉次數(shù)成倍增長，工作量無法估計。因此，本文運用貪婪算法來解決這一問題。

4 基于貪婪算法的車輛器材倉庫保障水平優(yōu)化

在貪婪算法中采用逐步構(gòu)造最優(yōu)解的方法。在每個階段，都做出一個看上去最優(yōu)的決策。決策一旦做出，就不能進行更改，做出貪婪決策的依據(jù)稱為貪婪準(zhǔn)則[6]。

在本文所研究的問題中，貪婪準(zhǔn)則按如下做出：當(dāng)增加一個第i種的器材備件時，車輛器材倉庫保障水平的期望值就會增加，其與備件價格的比值為：

進行選擇時，優(yōu)先選擇對車輛器材倉庫保障水平影響大同時價格低廉的器材備件。我們稱式（7）為搜索方向函數(shù)。

4.1 起始點的選擇

對于本文的優(yōu)化模型，起始點的選擇應(yīng)該考慮實際車輛器材倉庫的需求。一般認(rèn)為存在一個單件器材最低保障率，這個也是模型的約束條件之一，所以起始點應(yīng)該選擇其泊松累積分布值大于單件器材最低保障率的點。這樣既能節(jié)約大量搜索時間，也能更好地滿足車輛器材倉庫的需求。

4.2 搜索路徑的選擇

貪婪算法的核心是向最優(yōu)解逼近的搜索路徑的選擇，每一步的決策都要面對很多選擇。對于本文來說，就是選擇當(dāng)前要購買哪一種器材，確定之后，接著再選擇下一個要購買的哪種器材。由于的計算公式比較復(fù)雜，很難運用解析的方法來計算。所以本文用仿真的方法來解決此問題。依據(jù)每種器材需求量的泊松參數(shù)先產(chǎn)生大量的需求仿真，以此需求為參考來比較每一步方案的優(yōu)劣[7]。也就是單位資金對的增長影響最大的器材即為當(dāng)前的最優(yōu)決策，即按照式（7）通過大量仿真來選擇最優(yōu)路徑。

4.3 求得最優(yōu)解

4.4 數(shù)據(jù)仿真

利用隨機模擬仿真技術(shù)要通過大量的模擬才能比較出哪一個解是更接近最優(yōu)的可行解。理想的解法是把所有的可行解例舉出來，再對需求量做大量仿真。計算出各個可行解的車輛器材倉庫保障水平的平均值，將其作為期望值的估計值。其泊松參數(shù)可以根據(jù)式（8）計算得出[8]，即：

4.5 泊松流的產(chǎn)生

依據(jù)泊松分布規(guī)律，即：

其中，對于N=i當(dāng)且僅當(dāng)：

依據(jù)上式，第i個泊松事件到達(dá)發(fā)生在時刻l之前，而第i+1個泊松事件到達(dá)發(fā)生在時刻l之后。通過不斷產(chǎn)生指數(shù)到達(dá)時間間隔，再依次相加[9]。如果i+1個到達(dá)的時間間隔之和大于1的話，則N=i。

綜合式（10）和式（11）得到：

兩邊同時乘以-ω，再進行相關(guān)轉(zhuǎn)化得到：

由于對任意正數(shù)x都有elnx=x，故有：

因此，本文可以采用式（14）來產(chǎn)生泊松流N。根據(jù)式（14）產(chǎn)生泊松流的方法步驟如下：

（1）置n=0,P=1。

（2）產(chǎn)生一個隨機數(shù)Ri，并用P×Ri代替P。

（3）若P＜e-ωt，則接受N=n。否則，令n=n+1，然后返回步驟，依次反復(fù)執(zhí)行，直到生成所需要的泊松數(shù)。

5 實例驗證

以陜汽SX2190車型為研究對象，其部分關(guān)鍵核心器材數(shù)據(jù)見表2。

表2 車輛器材倉庫部分關(guān)鍵核心器材庫存情況（前）

對此車輛器材倉庫庫存的結(jié)構(gòu)進行優(yōu)化，可轉(zhuǎn)化為式（6）的線性約束最優(yōu)化問題：

本例搜索起始點選擇其泊松累積分布值大于單件器材最低保障率的點，本文取0.8。

表3 車輛器材倉庫部分關(guān)鍵核心器材庫存優(yōu)化結(jié)果（后）

6 結(jié)論

本文從車輛器材倉庫的庫存器材保障率出發(fā)，建立了車輛器材倉庫保障水平優(yōu)化模型。由于優(yōu)化模型表達(dá)式比較復(fù)雜，而且式中含有隨機變量，所以為了求得相對最優(yōu)解，利用隨機模擬技術(shù)蒙特卡洛進行仿真，并通過貪婪算法對仿真的大量數(shù)據(jù)進行求解，從而得到相對最優(yōu)解，大大地優(yōu)化了車輛器材倉庫的庫存結(jié)構(gòu)，提高了車輛器材倉庫保障水平。

[1]王亮.軍用車輛器材保障概論[M].北京:金盾出版社,2014.

[2]潘建.航材庫存系統(tǒng)優(yōu)化與實現(xiàn)[D].天津:中國民用航空學(xué)院,2004.

[3]Ascher H,Feingold H.Repairable Systems Reliablilitu-Modeling,Inference,Misconceptions and Their Causes[J].Journal of the Royal Statistical Society,1985,148(2).

[4]劉傳波,等.車輛器材庫存結(jié)構(gòu)優(yōu)化方法研究[D].天津:軍事交通學(xué)院,2010.

[5]周世軍,岳朝龍.蒙特卡洛模擬在期權(quán)定價中的應(yīng)用[J].安徽工業(yè)大學(xué)學(xué)報,2009,26(1):24-26.

[6]晏杰.Matlab中貪婪算法求解背包問題的研究與應(yīng)用[J].赤峰學(xué)院學(xué)報,2012,28(9):23-25.

[7]劉志帥,仝凌云,等.基于貪婪算法的貨位優(yōu)化模型[J].物流科技,2013,31(9):99-102.

[8]趙璞.關(guān)于泊松分布及其應(yīng)用[J].遼寧省交通高等?？茖W(xué)校學(xué)報,2009,11(2):77-79.

[9]谷峪,于戈,等.針對泊松流的截止敏感期的復(fù)雜事件處理資源分配模型[J].計算機學(xué)報,2012,35(5):37-51.

Study on Support Level Optimization of Vehicle Equipment Warehouses Based on Greedy Algorithm

Zhang Zhipeng1,Zhang Dapeng2,Wang Fengzhong2
(1.Student Brigade,Military Transportation Academy,Tianjin 300161; 2.Department of Military Vehicle,Military Transportation Academy,Tianjin 300161,China)

In this paper,we mainly analyzed the relevant concepts of inventory equipment support ratio and vehicle equipment warehouse support level,built the vehicle equipment warehouse support level optimization model and combined the Monte Carlo simulation and the greedy algorithm to obtain its relative optimal solution.

equipment support ratio;vehicle equipment support level;Monte Carlo simulation;greedy algorithm

E234;F224

A

1005-152X(2016)10-0155-04

10.3969/j.issn.1005-152X.2016.10.036

2016-09-09

張志鵬（1995-），男，江蘇鹽城人，研究方向：車輛運用工程。