求解硬时间窗约束下随机需求库存-路径问题的优化算法

Solving Stochastic Demand Inventory Routing Problem with Hard Time Windows

随机需求库存-路径问题(Stochastic Demand Inventory Routing Problem,SDIRP)即考虑随机需求环境下供应链中库存与配送的协调优化问题,是实施供应商管理库存策略过程中的关键所在,也是典型的NP难题之一。文章以具有硬时间窗约束的随机需求库存-路径问题(Stochastic Demand Inventory Routing Problem with Hard Time Windows,SDIRPHTW)为研究对象,将SDIRPHTW分解为直接配送的随机库存-路径问题和具有硬时间窗约束的路径优化问题两个子问题,并以最小化系统运行成本和用车数量为目标,设计了一个基于(s,S)库存策略和修正C-W节约法的启发式算法。最后,通过相应的数值算例验证了算法的有效性。

The Stochastic Demand Inventory Routing Problem（SDIRP）is a kind of typical NP-hard problem. To consider the coordination and optimization problem of inventory and distribution in the supply chain is the key to implementing vendor managed inventory. This paper explores the stochastic demand IRP with hard time windows （SDIRPHTW） , and decomposes SDIRPHTW into two sub-problems： stochastic inventory routing problem with direct distribution and vehicle routing problem with hard time windows. Then, with the objective to minimizing the system cost and the number of vehicles, we present a heuristic algorithm based on（s,S）inventory policy and modified C - W saving algorithm, and analyses the efficiency of the algorithm through a numerical example.