运筹与管理 ›› 2014, Vol. 23 ›› Issue (1): 26-32.

• 理论分析与方法探讨 • 上一篇    下一篇

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

赵达1, 李军2, 马丹祥3, 李妍峰2   

  1. 1.海南大学 经济与管理学院,海南 海口 570228;
    2.西南交通大学 经济管理学院,四川 成都 610031;
    3.河北联合大学 建筑工程学院,河北 唐山 063009
  • 收稿日期:2012-05-17 出版日期:2014-01-25
  • 作者简介:赵达(1980-),男,河北保定人,博士,讲师,研究方向:物流系统优化;李军(1967-),女,四川资阳人,教授,博士生导师,研究方向:博弈论,物流系统优化;
  • 基金资助:
    国家自然科学基金资助项目(71361006,71271178,71001005);中央高校基本科研业务费专项资金资助(SWJTU11CX087);中西部高校综合能力提升计划项目资助;海南大学科研启动基金项目(KYQD1303)

Solving Stochastic Demand Inventory Routing Problem with Hard Time Windows

ZHAO Da1, LI Jun2, MA Dan-xiang3, LI Yan-feng2   

  1. 1. School of Economics and Management, Hainan University, Haikou 570228, China;
    2. School of Economics and Management, Southwest Jiaotong University, Chengdu 610031, China;
    3. College of Civil and Architectural Engineering, Hebei United University, Tangshan 063009, China
  • Received:2012-05-17 Online:2014-01-25

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

关键词: 库存-路径问题, 随机需求, 硬时间窗, (s,S)策略, 修正的C-W节约法

Abstract: The Stochastic Demand Inventory Routing Problem(SDIRP)is a kind of typicalNP-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.

Key words: inventory routing problem, stochastic demand, hard time windows, (s,S)policy, modified C-W saving algorithm

中图分类号: