修正固定分区策略下随机需求库存-路径问题的最优策略及其算法

Optimal Strategy of Stochastic Demand Inventory Routing Problem under Modified Fixed Partition Policy and Its Algorithm

随机需求库存-路径问题(Stochastic Demand Inventory Routing Problem,SDIRP)是典型的NP难题。考虑随机需求环境下,供应链中库存与配送问题的协调优化,是实施供应商管理库存策略的关键所在。对经典固定分区策略(Fixed Partition Policy,FPP)中分区内所有客户必须同时接受配送的基本假设进行了改进,提出了一种分区内按客户需求进行配送的修正FPP策略。首先根据不同分区方案对客户的配送及库存成本的影响给出了一种基于C-W节约法的客户分区算法,并证明了修正FPP策略下各客户任意阶段的最优库存策略形式。进而,设计了求解修正FPP策略下SDIRP问题最优策略的算法。最后,通过数值算例验证了算法的有效性,同时对修正FPP策略的适用性进行了分析。

The Stochastic Demand Inventory Routing Problem （SDIRP） is a kind of typical NP-hard problem. Considering the joint inventory and distribution coordination optimization problem with stochastic demand is crucial to implement Vendor Managed Inventory strategy. Based on the assumption of classical Fixed Partition Policy （FPP） that all customers in a partition are served simultaneously, this paper proposes a modified FPP under which customers in a partition are served according to their realized demands. By taking the influence of different partition policies on distribution and inventory costs into consideration, we first design a customer partition procedure based on the C-W saving algorithm, which demonstrates that under the modified FPP, the optimal inventory policy for each customer in every stage is in the （s,S） form. With this property, we further design an algorithm to solve SDIRP with modified FPP. Finally, a numerical example is presented to show the efficiency of the proposed algorithm and demonstrate the feasibility of the modified FPP.