基于改进蚁群优化算法求解应急物资库存路径问题

周丹 邱玉琢

摘要：建立以预测需求为导向进行补货的应急物资库存路径问题的模型作为应急物资库存路径问题的通用模型。模型中采用预测需求函数作为补货的基础，避免单独使用OU补货政策导致补货过度僵化脱离实际。运用改进蚁群优化算法对模型进行求解，在蚁群优化算法中结合遗传算法中的多种操作，避免蚁群优化算法过早陷入局部最优，扩大其搜索域从而提高算法的性能。大量算例的计算表明，所提出的改进的蚁群优化算法能够在短时间内收敛;模型中各参数的敏感性分析结果表明：库存持有成本的增加一般会增加目标函数值，缺货成本的陡增不仅会增加目标函数值还会增加计算难度。

关键词：应急物资;库存路径;蚁群优化;预测需求函数;补货策略

中图分类号：O227文献标识码：ADOI：10.16465/j.gste.cn431252ts.20210617

2020年初爆发的大流行传染病COVID-19昭示了当前社会对应急储备物流优化的迫切需求。突发性事件具有高度的突发性和紧急性，事件发生地区的物资储备的种类及数量往往不能满足事件发生地区的需求。应急物资一旦出现供需失衡，就会产生不可估量的后果，因此，必须要对应急物资进行有效且高效的管理。

自Dantzig和Ramser于1959年对著名的旅行商问题（TSP）进行推广后得到了卡车调度问题以来，车辆路径问题（Vehicle Routing Problem，VRP）已经发展了50多年。第一次明确地将库存问题和路径问题结合起来考虑是Federgruen等[1]，从而引出了如今的库存路径问题的研究（Inventory Routing Problem，IRP）。Archetti等[2]将供应商管理库存的思想与路径选择相结合，在库存计算和模型条件里面同时考虑了供应商的库存和顾客的库存。经过30 多年的发展，目前IRP被大多数学者接受的定义为：供应商向多个地理位置分散的客户交付产品，可以通过同时优化库存管理、车辆路径和交付计划来提供集成的物流解决方案;从而确定何时为给定的客户提供服务，在提供服务时给该客户的交付量，以及由客户和供应商组成的车辆路线。

目前IRP文献中的供应商的补货政策最常见的是订单至最大库存水平策略（Order-up-to-level policy，OU策略）[3]。OU政策可以闡释为：如果在一个周期访问了一个零售商，则运送给该零售商的产品数量要使该零售商的库存水平达到其最大库存水平。OU补货策略是一种非常受欢迎，已经在许多IRP文献中使用;但它同时又是相当僵化的库存管理策略;而更灵活的补货政策可能会产生大量的库存费用。本文将以预测需求为导向，结合OU补货策略对各个需求点进行补货。

IRP的应用大多集中在海运、化工、石油和天然气的运输当中，也有许多文献在汽车零部件、易腐品、油罐等产品中研究了路径问题;但这些产品的研究很多仅仅是研究了它的车辆路径，并没有涉及库存问题决策。在IRP当中考虑应急产品的文献其实是相对较少的，大多数的应急产品是血液制品。查阅的众多文献中关于通用应急物资物流方面的研究主要还是在VRP的研究中，将IRP应用到通用的应急物资产品中的文献较少;所以本文的主要目的是提供一个通用的应急物资IRP问题的模型，并通过改进的蚁群优化算法为模型找到一个相对较好的上限。

到目前为止，求解IRP的方法一般分为两类：精确算法和元启发式算法。关于求解IRP的精确算法的文献相对较少，且精确算法的类型较少;分支- 定价、分支-切割平面算法成为求解IRP的精确算法的主流。与精确算法相比，使用元启发式算法的IRP文献相对较多，如蚁群优化、混合启发式算法、禁忌搜索算法、粒子群优化、遗传算法等。学术界对各种算法的改进正在增加，但ACO近10年来在IRP方面取得的改进相对较少。

本文的主要目的是将IRP的应用拓宽至应急物流领域，证明应急物资库存路径问题的可建模性与可求解性。本文采用预测需求函数作为补货的基础，避免单独使用OU补货政策导致补货过度僵化脱离实际。将IRP中客户需求以规律的（能够使用模型进行预测的）需求预测模型代替了以往研究中确定的需求或随机性的需求（不规律的）。

1问题描述

2应急物资库存路径模型

在给出基本的IRP模型之前，首先对模型中的其他相关符号进行说明：

B₀：供应商的初始库存水平;

B_t为供应商在t期初的库存水平;

h₀：供应商的单位库存成本;

C_ij：点i（x_i，y_i）到点j（x_i，y_i）的运输成本;

s：缺货成本;

I_it：t期初需求点的实际库存水平;

Archetti等[2]在2007年提出的IRP模型是同时考虑供应商和客户的库存，以供应商管理库存为大背景，为整个供应链提供库存路径的解的混合整数规划模型。本文结合文献[3]将基础模型进行改进并整合为模型（P）：

使得：

目标函数式（1）是最小化供应商库存成本、需求点库存成本、运输成本缺货成本之和;式（2）是需求预测函数;式（3）～式（5）是根据订单水平策略结合需求预测函数进行改进的补货政策;式（6）～式（8）说明库存平衡;式（9）是车辆容量限制;式（10）要求每个周期内每位客户最多被拜访一次;式（11）表示每期每个节点和每台车辆的度约束条件;式（12）是每期每个车辆路线和每期子回路消除约束的条件;式（13）～式（16）是相应的变量约束。

3算法流程详解

3.1路线构建

在应急物资IRP中使用蚁群算法时，每只蚂蚁从仓库出发，通过增量选择客户来构建自己的路线，然后返回仓库，增量选择需求点的过程就是构建路线的过程。基于多周期，需要在每条边上构造多维信息素信息，即在不同的周期，每条边上有不同的信息素信息;搜索过程中需要维护多个信息素信息矩阵;信息素信息矩阵的数量等于规划周期。

3，2改进初始解和邻近解

本文在蚁群算法中引入单点交叉操作、变异操作和2-opt操作来探索搜索空间和防止过早陷入局部最优。在交叉操作方面，本文引用文献[4]构建的改进蚁群算法中单点交叉操作和两点交叉操作。单点交叉操作是同一周期内两个车辆路线之间的子路线交换程序。与遗传算法中的单点交叉操作一样，交叉操作可以获得两个新的路径。变异操作参照文献[5]提出的改进蚁群算法以预定的概率改变每个子代路线。该操作可以帮助ACO在搜索领域达成进一步的解决方案。变异操作的思想是随机地变异这条路线，并因此产生一个新的解决方案，这个新的解决方案离最初的解决方案不远。在本文中，变异算子以随机方式进行点交换。2-opt是对一条路线内的点进行操作，嵌入在交叉操作和变异操作中;即为交叉（变异）操作步骤的第七步。在2-opt交换中，对每台车访问的所有可能的成对客户位置交换进行测试，以查看是否可以实现目标函数的整体改进。

3.3信息素更新

信息素轨迹的更新是蚁群算法自适应学习技术和改进未来解的关键。信息素更新旨在使属于好的解决方案的组件对于在后续迭代中操作的蚂蚁来说更加理想。本文选用信息素轨迹蒸发，信息素轨迹随着时间的推移减少先前蚂蚁沉积的信息素的机制。

4算例分析

4.1实例数据构建及算法参数设置

实验的模型和算法是在计算机软件MATLAB 2017a中实现的，运行是在配置为Intel CORE九代i5-9300H，GTX1650 8G 的个人电脑上。

为了在后续的实验中不僵化整个算法参数的设置，本文根据每个实例所包含的需求点个数合理地确定种群大小（一般种群大小等于需求点个数）;a在[0.5，0.9]之间取值，点数越多，a越小;B在[0.5，7]之间取值，点数越多，取值越大;信息素蒸发系数在[0.4，0.8]之间取值来提高算法效率，实例越大取值越低;达到最大迭代次数后停止迭代，输出结果。最大迭代次数根据实例周期大小以及包含需求点个数综合确定，最大迭代时间小于等于1 000 s。

4.2计算结果

本文对每一个实例都进行了5次计算，结果顯示：在H=3的情况下，需求点个数小于等于20个点的实例基本上5次计算都得到同一个结果，超过20个点的实例计算结果出现了上下波动的情况;说明改进蚁群算法能在3个周期20个点以内的实例中快速有效收敛到相对较好的解。但是在实例大于等于10个需求点后，计算结果就不稳定了;说明周期变长会大大增加IRP模型的复杂度，使得问题变得更难求解。在计算时，可以很明显地看出，需求影响常数对目标函数值的影响不太大。但是需要注意的是，这些实例都是在所有参数相对较小的情况下计算的;一旦参数陡增，会使计算变得更加复杂。

缺货成本陡增的情况下，计算结果在3个周期大于等于10个点时就出现了差异，在6个周期中大于等于5个点时计算结果就出现波动;说明缺货成本参数陡增同样会大大增加IRP模型的复杂度，使得问题变得更难求解。缺货成本的陡增对目标函数值的影响较大。综合来看，缺货成本的陡增不仅会增加计算难度，还会使目标函数值恶化。在缺货成本较大的情况下，小实例的计算结果会因为库存持有成本的增加而恶化。

5结论

应急物资一旦出现供需失衡，就会产生不可估量的后果，因此，必须要对应急物资进行有效并且高效的管理。本文建立了以预测需求为导向进行补货的应急物资库存路径问题的模型，并通过改进的蚁群优化算法对其进行求解;通过大量实例运算，表明了IRP运用于应急物流的可行性较好。本文通过各种实例计算后发现，模型中的有关参数会对计算结果和计算难度造成较大的影响：需求影响常数的增加对目标函数值没有太大的影响，库存持有成本的增加一般会增加目标函数值，缺货成本的陡增不仅会增加目标函数值还会增加计算难度。因此，在进行NP-hard问题求解时，要考虑相关参数的设置情况。在实践运用中，可以通过标准化参数或同时降低所有参数来降低计算复杂度。

现实生活中的应急管理问题往往更加复杂，本文建立的模型还不能很好地反映应急物流的特性。因此，后续关于应急物流库存路径问题可以考虑更多现实性的问题，比如涉及多种商品、易腐产品运输的库存路径问题等;蚁群算法除了和遗传算法进行结合外，还可以在结合遗传算法的基础上引入模拟退火公式避免过早陷入局部最优。

参考文献

[1] FEDERGRUEN A，ZIPKIN P. A combined vehicle routing and inventory allocation problem[J]. Operations Research，1984，32（5）：1019-1037.

[2] ARCHETTI C，BERTAZZI L，LAPORTE G，et al. A branch- and-cut algorithm for a vendor-managed inventory-routing problem[J]. Transportation Science，2007，41（3）：382-391.

[3] ARCHETTI C，BOLAND N，GRAZIA SPERANZA M. A matheuristic for the multivehicle inventory routing problem[J]. INFORMS Journal on Computing，2017，29（3）：377-387.

[4] YU B，YANG Z Z. An ant colony optimization model：The period vehicle routing problem with time windows[J]. Transportation Research Part E，2011，47（2）：166-181.

[5] YU B，YANG Z Z，YAO B Z. An improved ant colony optimization for vehicle routing problem[J]. European Journal of Operational Research，2009，196（1）：171-176.

Based on the Improving Algorithm of Ant Colony Optimization to Solve the Emergency Inventory Routing Problem

Zhou Dan，Qiu Yuzhuo

（School of Marketing and Logistics Management，Nanjing University of Finance and Economics，Nanjing，Jiangsu 210046）

Abstract：A model of emergency material inventory path problem based on forecast demand-oriented replenishment is established as a general model of emergency material inventory path problem. In this model，the predictive demand function is used as the basis for replenishment，so as to avoid the over-rigidity of replenishment due to the OU replenishment policy alone. The model is solved by improving the ant colony optimization algorithm，combining the crossover，variation and 2-opt operation in the ant colony optimization algorithm，avoiding the ant colony optimization algorithm falling into local optimality too early，expanding its search domain and improving the performance of the algorithm. Finally，the sensitivity and comparative analysis of the algorithm parameters and model parameters are carried out to determine the algorithm parameters of the example calculation，and to analyze the influence of the parameters in the model on the model and the solution.

Key words：emergency material，inventory routing，ant colony optimization，predict demand functions，replenishment strategy