面向联合补货-配送问题的ε-最优算法和对偶下界  

An e-optimal algorithm and a dual lower bound for the joint replenishment and delivery problem

作　　者：王思睿 王林[1] 吴彬溶 张金隆[1] WANG Si-rui;WANG Lin;WU Bin-rong;ZHANG Jin-long(School of Management,Huazhong University of Science and Technology,Wuhan 430074,China)

机构地区：[1]华中科技大学管理学院,武汉430074

出　　处：《管理科学学报》2025年第2期85-101,共17页Journal of Management Sciences in China

基　　金：国家社科基金资助重大项目(20&ZD126);中央高校基本业务费资助项目(2021WKFZZX014)。

摘　　要：针对多物品库存系统中常见的联合补货-配送问题,挖掘了其数学模型中的一系列性质,并提出了一种ε-最优算法和一个对偶下界.实验结果表明,本文设计的算法效果超过了现有研究中表现最好的几种元启发式算法,对目标值的提升幅度最高能达到31%,对偶下界与最优值的偏差较小,平均不超过0.84%.新算法运算效率较高,100个商品的算例平均运算时间不超过23秒.此外,本文还对算法时间复杂度进行了分析,在实际应用环境中,该算法能够达到O(n)级多项式时间复杂度,这一结论可为联合补货-配送问题的算法设计理论提供有益的补充.最后,对协同配送策略的效益进行了分析.实验发现,只有当中心仓库的库存管理水平相比零售商处的库存管理水平有较大优势时,协同配送才能够取得较高的成本节约效益.This paper addresses the common joint replenishment and delivery(JRD)problem that occurs in a multi-item inventory system.An s-optimal algorithm and a dual lower bound are proposed via deeply analyzing the mathematical properties of the model.The randomized numerical experiments show that the proposed s-optimal algorithm outperforms the existing meta heuristics both in terms of both accuracy and efficiency,and the largest increase in accuracy can reach 31%.The dual lower bound is very tight,with the gap averaging below 0.84%.Moreover,the proposedε-optimal algorithm is also very fast,and a 100-item instance can be solved in twenty-three seconds.In addition,the time complexity of the 8-optimal algorithm is analyzed.The-optimal algorithm can achieve O(n)polynomial-time complexity under real-world situations,which enriches the algorithmic design theory of the JRD research.Finally,the effect of coordinated delivery is analyzed.Experiments show that coordinated delivery can achieve cost reduction when the inventory management level of the central warehouse is higher than that of the retailers.

关 键 词：联合补货-配送 Lipschitz优化 ε-最优 定界启发式算法 对偶下界 

分 类 号：F274[经济管理—企业管理] F224[经济管理—国民经济]