基于贪婪算法的车辆器材仓库保障水平优化研究

张志鹏，张大鹏，王凤忠

（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-），男，江苏盐城人，研究方向：车辆运用工程。