多商品库存路径问题研究

凌镜珩

（1.西南交通大学 交通运输与物流学院，四川 成都 611756；2.深圳市城市交通规划设计研究中心，广东 深圳 518000）

1 引言

库存-路径问题（inventory routing problem，IRP）是整合了库存管理、车辆路径以及运输决策的综合性优化问题。该问题通常是指在供应商管理库存（vendor-managed inventory，VMI）模式下，考虑到诸如客户库存、运输车辆容量等约束条件，在单个的供应商与多个地理位置分散的客户组成的物流系统中，确定库存策略、配送策略（包括配送数量与路径决策）的优化问题。

在以往的实际生产经营中，库存管理环节与运输环节往往由不同的部门或个人负责。因此，传统上是单独研究对库存管理策略与运输决策的优化，没有统筹兼顾。但随着现代化产品的生命周期变短、更新加快、需求波动复杂等趋势，供应链内的需求信息容易出现传递扭曲、变形等问题，从而产生牛鞭效应（Bull-whip effect）。为了解决这个问题，供应商管理用户库存策略（Vendor Managed Inventory,VMI）应运而生。VMI 模式以系统、集成的思想去进行库存管理，削减供应商的生产与分销成本，整个供应链的成本得以降低。对供应商而言，如何对库存以及运输这两个关键的物流环节进行有效管理，做出灵活有效率的决策，成为实施VMI战略的关键。

对IRP问题的研究起源于车辆-路径问题（VRP，vehicle-routing problem）的变种。该问题最早由Bell等[1]在1983年研究在满足客户库存水平、计算运输成本、需求随机的情况下的路径规划问题。Andersson等[2]、Coelho 等[3]追溯了过去 30年间 IRP 问题的研究成果。Campbell和Savelsbergh[4]建立了一个使用供应商管理库存的模型，该模型将顾客的补货与库存控制交给供应商管理，并采用两阶段法对该模型求解；Moin，Salhi，and Aziz[5]研究了多个供应商对单个客户配送多种商品的问题，采用了遗传算法；Coelho and Laporte 等[6]使用精确算法求解了多种商品多车辆的IRP 问题。在国内，傅成红[7]、段凤华[8]两人从不同的方面，在分析库存路径问题相关文献的基础上，给出了IRP 的一般化定义，并对其进行分类。赵达等[9]以随机需求下的IRP问题为研究对象，提出了一种基于马尔科夫决策过程与修正的C-W节约算法的启发式分解算法。魏江宁，夏唐斌[10]采用模拟退火的启发式算法计算每个时间段客户的订货量，再分配车辆路径；张弈[11]研究了多周期易腐品的IRP问题；朱桂阳[12]研究了在考虑缺货的情况下，有不同腐败速率的易腐品IRP问题。

库存-路径问题将原本分别优化的库存管理，运输决策两者进行联合优化。库存管理的核心是在保证安全库存的情况下尽量减少库存积压，而运输决策却要求尽可能的减少运输成本，两者存在着“效益背反（Trade-off）”的关系。只有通过联合优化，才能从整体上控制供应链的成本。对库存-路径问题的研究，有助于在生产经营活动中实施VMI模式，协调整体供应链，降低总成本，为供应链一体化做好准备。由于IRP问题在一定程度上可视为VRP问题的延伸，其数学优化模型往往是非线性的混合整数优化模型，求解难度较大，所以对IRP问题的研究，除了在实际生产经营中有多种应用场景，还具有理论价值。

2 模型建立

2.1 问题描述

由一个配送中心和多个客户组成的仓储配送系统。该配送系统中，客户地理位置已知，接收由区域仓库中心发出的多种产品。决策者负责决策计划期内所有种类的产品是否配送、配送数量、客户库存水平、配送路径等。不同产品的库存持有成本与缺货费用均不同，但共同存储在配送中心与客户中，配送时也使用同一车队进行配送，共享车辆容量。

在每一个计划期开始前，先由区域配送中心对客户进行配送，再扣除客户的市场需求。每一种商品的库存持有成本与缺货成本是不同的，市场对每一种商品都有互相独立且随机的市场需求。计划期内未被满足的每一种商品都会被积压到下一个计划期并产生缺货惩罚。

为了方便模型的建立与求解，在实际情况的基础上做出如下假设：

（1）因配送中心的库存持有成本远小于客户，不考虑配送中心的库存容量限制与成本；

（2）运输车队一个计划期内最多进行一次以配送中心为起讫点的配送路径，路径可包括任意客户的集合；

（3）不同的商品在客户中共同存储，配送时共享同一运输车队的容量限制，不单独配送；

（4）所有的配送与装卸活动都可以在一个计划期内完成，车辆的每一次配送不会拖延到下个计划期；

（5）忽略不同计划期下的路况差异，配送路况是恒定的；

（6）在每一个计划期，先有配送中心为客户补货，再从客户的库存中扣除市场需求的量；

（7）客户的库存不满足需求时，产生缺货积压，积压记入下一计划期，并产生缺货成本。

2.2 参数与变量

根据以上问题描述与模型假设，模型涉及到的参数与变量见表1。

2.3 数学模型

根据以上参数设置与模型假设，以最小化时间平均下的配送运输费用与库存费用为目标，建立无限计划期下的多商品库存路径问题模型：

表1 参数与变量定义

约束条件：

式（1）为目标函数为最小化时间平均下的配送运输费用与库存费用；式（2）表示在客户节点内运输车辆进出顺序约束，任意运输车辆进入该客户点，也需要从该点离开；式（3）是度约束，如果该客户节点被配送，该节点的度为2，保证该节点在计划期内只被配送一次，反映了车辆运输的变量与客户配送变量之间的约束关系；式（4）是子回路消除约束（subtour elimination constraints），保证配送路径中不存在子回路；式（5）是库存的更新约束，表示现计划期的库存等于上一计划期的库存减去该计划期的客户需求量加上该计划期的配送量；式（6）、（7）是客户库存约束，限制了客户库存非负并且小于等于库存容量；式（8）表示对客户的单次配送量小于库存容量的剩余空间；式（9）表达客户配送量与对客户是否配送0-1变量之间的约束关系，不对客户进行配送，则配送量为零；式（10）表示配送中心不发出配送车辆时，所有客户的配送量为0；式（11）表示配送量的非负性；式（12）、（13）声明了变量属于0-1变量。

3 求解算法

在客户需求随机的情况下，无法预测计划期内的客户需求，所以此处采用两阶段法对该模型进行求解。第一阶段是根据客户需求服从的随机概率分布、单位库存持有费用、单位缺货成本来确定（s，S）补货策略中各个客户的最优订货点、最大库存水平。Zheng和Federgruen[13]所提出的在随机需求下计算（s，S）库存策略的算法是被广泛使用的一种标准算法，本文也采用该算法计算各客户的最优订货点与最大库存水平。

第二阶段是根据（s，S）补货策略来计算计划期内给各客户的配送数量、期望缺货数量。将原问题简化成一个车辆路径问题来计算给各客户的配送路径。该问题在小规模的情况下可作为一个线性的混合整数规划问题进行求解。

采用分支定界的方法对模型进行求解：

（1）将目标函数式（1）与约束条件（2）-（10）组成一个线性规划问题记做LP。对LP进行求解，如果解为整数解，则是原问题的最优解，如果解不是整数解则进行下一步的分支定界。

（2）LP的解作为搜索树的根节点，对出现的第一个非整数解，加上约束(11)。将0-1约束代入线性规划问题中进行重新优化，并进行计算。

（3）将根节点后的每一个分支表明求解结果，并表明不同分支结果的上下界。

（4）如果满足整数要求的最优解小于前一个搜索节点计算出的下界，则剪除此支并不再考虑。如果大于搜索节点的下界则重复步骤继续优化，直到上下界接近或者无法进行分支。

4 算例分析

为了验证模型的有效性，假设某企业的配送系统由一个配送中心与9 个零售商客户组成。配送中心对零售商客户进行某同质产品的配送服务。客户的需求服从已知的概率分布。为了更加贴近实际情况，算例中假设客户的需求服从Poisson 分布。具体客户信息见表2。

本节算例采用Matlab 2018a 计算软件，使用yalmip 工具箱调用CPLEX Optimization studio 12.8.0求解器对该线性混合整数规划问题进行求解，求解结果如下：

表2 客户基础信息表

算例以10 个计划期为一组，计算了总计100 个计划期下的库存路径配送方案，并以每10 个计划期一组的平均值与采用EOQ经济订购批量方法的解决方案进行了对比，具体如图1所示。

图1 算例计算结果与对比

从图1的对比结果中可以发现：高服务水平下的EOQ 算法（服务水平为95%）的缺货费用较低，接近于零；总体库存成本与本章算法接近，但是为了保持高服务水平频繁配送，运输成本明显高于本章算法。

低服务水平下的EOQ算法（服务水平为75%）因为运输频率低的原因，运输费用较低，但产生了显著的缺货费用，导致总库存成本比本章算法与高服务水平下的EOQ算法分别高出30.82%与29.86%。

本章算法在库存成本与配送费用之间找到了一个平衡：其缺货成本位于两种EOQ算法之间，运输成本也小于高服务水平的EOQ算法但大于低服务水平的EOQ 算法。在算例的100 个计划期内，其总的库存运输费用分别比高、低服务水平的EOQ 算法要少5.3%与12.2%。

5 结论

库存与路径问题联合优化需要考虑库存容量限制、车辆容量限制等约束条件，在单个的供应商与多个地理位置分散的客户组成的物流系统中确定库存策略、配送策略。本文所建立的混合整数规划模型的求解结果可以很好地在库存费用与配送频率之间达到平衡。联合优化的结果比分别对库存策略与配送路径进行优化的方案更节省配送系统的总成本。

本文研究还存在一定的不足之处，将作为今后进一步研究的方向。在模型的设计中为了简化计算，未考虑配送中心的库存容量限制与成本，也没有动态地对运输车辆资源进行优化。如果考虑这些因素，可以让模型更符合实际，对实际的物流配送系统更有参考价值。