求解多周期库存路由问题的三阶段数学启发式算法

作者：李春根; 黄施豪; 苏宙行; 吕志鹏

来源：自动化学报, 2020, 1-20.

DOI：10.16383/j.aas.c200244

• 数学启发式
• 禁忌搜索
• 库存路由
• 库存管理
• 车辆路由

库存路由问题(Inventory Routing Problem, IRP)研究供应链中库存管理和车辆路由的联合优化, 属于NP-hard问题. 该问题需要在多个配送周期调度单个车辆对若干客户进行合理配送, 在保证所有客户均不断供的前提下, 使库存成本与路由成本的总和最小. IRP问题的解需要确定每个配送周期访问哪些客户并为其配送多少产品, 以及每个周期的配送路线. 本文提出了一种三阶段数学启发式(Three-Stage Matheuristic, TSMH)算法求解IRP问题. 第一阶段通过修复无子回路消除约束的松弛解生成合法初始解, 并利用惰性约束收紧松弛模型继续提升初始解的质量. 第二阶段求解一系列部分配送周期内的决策变量被固定的子问题, 以实现对当前解的结构性调整. 第三阶段迭代地执行基于解的禁忌搜索过程, 对当前解进行细粒度优化. 在220个标准算例上对TSMH算法进行测试, 实验结果表明, 该算法同文献中最高效的算法相比具有明显优势. 具体而言, TSMH算法找到了160个小规模算例中的145个最优解以及60个大规模算例中的46个已知最优上界, 表明该算法求解IRP问题的有效性和高效性. 此外, 通过对比实验分析了算法的参数设置和收敛特性, 并验证了TSMH算法中第二阶段的局部格局调整过程和第三阶段的双层邻域筛选策略两个关键组件对算法求解效率的重要性.

• 单位
  华中科技大学