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

張志鵬，張大鵬，王鳳忠

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

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

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

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

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

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

1 引言

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

2 相關概念的辨析

2.1 庫存器材保障率

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

2.2 器材保障水平

表1 器材的需求密度函數及實際請領數密度函數

則其保障水平L為：

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

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

3 車輛器材倉庫保障水平優化模型的構建

3.1 確定優化目標

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

3.2 模型建立條件

（1）本文中的車輛器材庫存優化是在經費一定的情況下，使車輛器材的保障水平實現最大化。

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

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

3.3 建立優化模型

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

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

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

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

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

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

（1）構造概率模型；

（2）實現從已知概率分布的抽樣；

（3）建立各種統計量的估計。

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

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

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

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

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

4.1 起始點的選擇

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

4.2 搜索路徑的選擇

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

4.3 求得最優解

4.4 數據仿真

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

4.5 泊松流的產生

依據泊松分布規律，即：

其中，對于N=i當且僅當：

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

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

兩邊同時乘以-ω，再進行相關轉化得到：

由于對任意正數x都有elnx=x，故有：

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

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

（2）產生一個隨機數Ri，并用P×Ri代替P。

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

5 實例驗證

以陜汽SX2190車型為研究對象，其部分關鍵核心器材數據見表2。

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

對此車輛器材倉庫庫存的結構進行優化，可轉化為式（6）的線性約束最優化問題：

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

表3 車輛器材倉庫部分關鍵核心器材庫存優化結果（后）

6 結論

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

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

[2]潘建.航材庫存系統優化與實現[D].天津:中國民用航空學院,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]劉傳波,等.車輛器材庫存結構優化方法研究[D].天津:軍事交通學院,2010.

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

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

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

[8]趙璞.關于泊松分布及其應用[J].遼寧省交通高等專科學校學報,2009,11(2):77-79.

[9]谷峪,于戈,等.針對泊松流的截止敏感期的復雜事件處理資源分配模型[J].計算機學報,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-），男，江蘇鹽城人，研究方向：車輛運用工程。