随机需求库存-路径问题最优策略及其算法

Optimal strategy of stochastic demand inventory routing problem and algorithms

随机需求库存-路径问题(stochastic demand inventory routing problem,SDIRP)是典型的NP难题,也是实施供应商管理库存策略过程中的关键所在.文章研究了在直接配送策略、无车辆配送能力约束的Milk-Run配送策略以及考虑该约束的Milk-Run配送策略下SDIRP的最优策略形式.首先,证明了前两类问题的最优库存策略为(s,S)形式,并在此基础上,通过引入固定分区策略将第三类问题转化为前两类问题进行研究;其次,针对前两类问题分析了最优库存策略的性质,给出了策略中各参数的上、下界,并提出了求解这两类问题最优策略的优化算法;最后,通过数值算例验证了文中算法的有效性,进而讨论了实际中常用的固定配送路径下(s,S)策略的适用范围.

The Stochastic Demand Inventory Routing Problem （SDIRP） is a typical NP-hard problem and is also the key to implementing Vendor Managed Inventory （VMI） strategy. This paper analyses the optimal strategies to SDIRP under direct delivery policy, Milk-Run delivery policy without vehicle capacity constraint, and Milk-Run delivery policy with vehicle capacity constraint, respectively. It is proved that （s, S） policy is the optimal inventory policy for the first two kinds of SDIRP. The third kind of SDIRP can be solved after be- ing transformed into the first two kinds of SDIRP via Fixed Partition Policy （FPP）. Then, the properties of the optimal strategies to SDIRP are analyzed, and the lower and upper bound of the parameters for the optimal strategy are given. An algorithm is proposed to solve the first two kinds of SDIRP. Finally, this paper presents a numerical example to analyze the efficiency of the algorithm and discusses the practical application of （s ,S） policy under the fixed route delivery policy.