﻿ 基于改进树搜索方法的库存系统优化
 文章快速检索
 同济大学学报(自然科学版)  2019, Vol. 47 Issue (12): 1831-1836.  DOI: 10.11908/j.issn.0253-374x.2019.12.020 0

### 引用本文

MU Gang, SUN Yongchao, XU Chenglong. Inventory System Optimization Based on Improved Tree Search Method[J]. Journal of Tongji University (Natural Science), 2019, 47(12): 1831-1836.   DOI: 10.11908/j.issn.0253-374x.2019.12.020

### 文章历史

1. 同济大学 数学科学学院，上海 200092;
2. 上海财经大学 数学学院，上海 200433

Inventory System Optimization Based on Improved Tree Search Method
MU Gang 1, SUN Yongchao 1, XU Chenglong 2
1. School of Mathematical Sciences, Tongji University, Shanghai 200092, China;
2. School of Mathematics, Shanghai University of Finance and Economics, Shanghai 200433, China
Abstract: Propose an algorithm to optimize the strategy for an inventory system, minimize the storage cost with constraint of satisfying service level. Abstract the inventory system optimization problem into a stochastic optimization problem, combine Kriging regression and Monte Carlo tree search to solve the stochastic optimization problem efficiently. Apply this method into a real world example and get positive feedback.
Key words: supply chain management    inventory optimization    Kriging interpolation    Monte Carlo tree search

1 问题描述 1.1 多级库存系统

 图 1 多级库存系统的结构 Fig.1 The structure of multi-echelon inventory system
 图 2 (r, Q)策略下库存水平变化情况 Fig.2 Dynamic of inventory system under (r, Q) strategy

 ${T_{{\rm{LD}}}} = \left\{ \begin{array}{l} {T_{{\rm{PT}}}}\;\;\;\;\;\;\;\;\;\;上级仓库有足够的{\mathit{S}_{{\rm{OHI}}}}\\ {T_{{\rm{PT}}}} + T_{{\rm{LD}}}^\prime \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;上级仓库没有足够的{\mathit{S}_{{\rm{OHI}}}} \end{array} \right.$

1.2 样本均值估计

x =(r1, r2, r3, r4, Q1, Q2, Q3, Q4), 库存系统的输入包含客户订单量和订单的运输时间等随机变量，记这些随机变量为w，总成本为C(x, w)，及时供应率为F(x, w), 供应率的限制为Fmin.需要求解的优化问题为

 $\begin{array}{l} \;\;\mathop {\min }\limits_\mathit{\boldsymbol{x}} \phi (\mathit{\boldsymbol{x}}) = {E_w}[C(\mathit{\boldsymbol{x}}, w)]\\ {\rm{s}}{\rm{.t}}{\rm{.}}\;\psi (\mathit{\boldsymbol{x}}) = {E_w}[F(\mathit{\boldsymbol{x}}, w)] \cdots {F_{\min }} \end{array}$

1.3 基于代理的模拟

2 克里金插值

 $Y(\mathit{\boldsymbol{x}}) = f{(\mathit{\boldsymbol{x}})^{\rm{T}}}\mathit{\boldsymbol{\beta }} + M(\mathit{\boldsymbol{x}})$

 $\widehat Y({x_0}) = \mathit{\boldsymbol{\lambda }}{({x_0})^{\rm{T}}}\mathit{\boldsymbol{Y}} + {\lambda _0}({x_0}).$

 $\widehat Y({x_0}) = {\beta _0} + {\mathit{\boldsymbol{ \boldsymbol{\varSigma} }}_M}{({x_0}, \cdot)^{\rm{T}}}{\mathit{\boldsymbol{ \boldsymbol{\varSigma} }}_M}^{ - 1}(Y - {\beta _0}{\bf{1}}{_m})$

3 蒙特卡罗树搜索

(1) 选择：从一个根节点出发，持续使用子节点的树搜索策略来扩展树结构.一个节点是可扩展的，如果该节点处于非终极状态并有未访问的子节点.

(2) 扩展：根据可行的动作将一个或者多个子节点加入树结构.

(3) 模拟：在新的节点根据默认策略来进行模拟，生成奖励(效用)函数的结果.

(4) 回溯：将模拟的结果回溯到选择的节点中，并更新对应节点相应的统计值.

(1) 选择：每次扩展后选择效用函数最优的子空间.

(2) 扩展：对选择的节点进行扩展，在选择的节点下生成2N个子节点.

(3) 模拟：在子空间内部进行均匀抽样并计算相应的效用函数.

(4) 回溯：将抽样计算的结果回溯到父节点，并计算相应的平均值和方差.

4 蒙特卡罗方法和克里金方法的结合

 ${f_1} = \widehat \phi (\mathit{\boldsymbol{x}}) + p \cdot {I_{{\rm{sign}}}}({\rm{max}}({F_{{\rm{min}}}} - \widehat \psi (\mathit{\boldsymbol{x}}), 0))$

 图 3 蒙特卡罗树搜索与克里金相结合的算法 Fig.3 Monte Carlo tree simulation algorithm with Kriging
5 实际案例的数值结果

 图 4 最优值与搜索时间的关系 Fig.4 Relationship of ϕ(x) and search time
 图 5 限制条件和搜索时间的关系 Fig.5 Relationship of $\overline \psi$(x) and search time

 图 6 最优解标准差和搜索时间的关系 Fig.6 Relationship of s($\left\| x \right\|$) and search time

6 结论

 [1] WASSICK J M, AGARWAL A, AKIYA N, et al. Addressing the operational challenges in the development, manufacture, and supply of advanced materials and performance products[J]. Computers & Chemical Engineering, 2012, 47: 157 [2] 黄晟.基于集中控制策略的汽车维修备件分布式多级库存研究[D].上海: 东华大学, 2013. HUANG Sheng. A study on distributed multi-Level inventory system of automobile maintenance parts in centralized control background. Shanghai: Donghua University, 2013. http://cdmd.cnki.com.cn/Article/CDMD-10255-1013161940.htm [3] CHU Y, YOU F, WASSICK J M, et al. Simulation-based optimization framework for multi-echelon inventory systems under uncertainty[J]. Computers & Chemical Engineering, 2015, 73: 1 [4] BILES W E, KLEIJNEN J P C, BEERS W C M V, et al. Kriging metamodeling in constrained simulation optimization: an explorative study[C]// Conference on Winter Simulation: 40 Years! the Best Is Yet to Come.[S.l.]: IEEE Press, 2007: 355-362. [5] 李晓军, 李培楠, 朱合华, 等. 基于贝叶斯克里金的地下空间多源数据建模[J]. 同济大学学报(自然科学版), 2014, 42(3): 406 LI Xiaojun, LI Peinan, ZHU Hehua, et al. Geomodeling with integration of multi source data by Bayesian Kriging in underground space[J]. Journal of Tongji University (Natural Science), 2014, 42(3): 406 DOI:10.3969/j.issn.0253-374x.2014.03.013 [6] ANKENMAN B, NELSON B L, STAUM J. Stochastic Kriging for simulation metamodeling[J]. Operations Research, 2010, 58(2): 371 [7] JONES D R, SCHONLAU M, WELCH W J. Efficient global optimization of expensive black-box functions[J]. Journal of Global Optimization, 1998, 13(4): 455 DOI:10.1023/A:1008306431147 [8] HUANG D, ALLEN T T, NOTZ W I, et al. Global optimization of stochastic black-box systems via sequential Kriging meta-models[J]. Journal of Global Optimization, 2006, 34(3): 441 DOI:10.1007/s10898-005-2454-3 [9] SILVER D, HUANG A, MADDISON C J, et al. Mastering the game of Go with deep neural networks and tree search[J]. Nature, 2016, 529(7587): 484 DOI:10.1038/nature16961 [10] KIM S, PASUPATHY R, HENDERSON S G. A guide to sample average approximation—handbook of simulation optimization[M]. New York: Springer, 2015 [11] RAHMANDAD H, STERMAN J. Heterogeneity and network structure in the dynamics of diffusion: comparing agent-based and differential equation models[J]. Management Science, 2008, 54(5): 998 DOI:10.1287/mnsc.1070.0787 [12] 邹林君.基于Kriging模型的全局优化方法研究[D].武汉: 华中科技大学, 2011. ZOU Linjun. A search of global optimization method based on kriging model[D]. Wuhan: Huazhong University of Science and Technology, 2011. [13] BROWNE C B, POWLEY E, WHITEHOUSE D, et al. A survey of Monte Carlo tree search methods[J]. IEEE Transactions on Computational Intelligence & Ai in Games, 2012, 4(1): 1