多周期供应链库存-路径优化：分裂-后优化启发式的多约束配送场景智能求解
一、研究背景与问题提出
库存路径问题（Inventory Routing Problem，IRP）结合了库存控制与车辆路径规划，传统模型多假设同质车队和固定需求。现实应用中，车辆类型、运输成本和需求随时期变化，配送批量必须是客户规定的整数倍，传统算法难以直接解决。
作者提出的异构库存路径问题与批量交付（HIRP‑BS）的特点为：
异构车辆：每种车辆有不同容量、固定/变动成本，且各时期可用车辆数不同。 批量交付：每个客户的交付数量必须是预设批量的整数倍，避免频繁发货。 时期依赖的需求与成本：客户需求和库存持有成本在不同时期取值不同。 多期多辆车的联合决策：决定何时配送、配送数量和路线以最小化库存持有成本和运输成本。
作者在文中通过数学模型刻画HIRP‑BS，并提出Split‑Embedded Metaheuristic with Post‑Optimization（SEMPO）求解框架，既能处理车辆异质性和批量约束，又能高效求解大规模实例。
1.1 研究意义
供应链协同：HIRP‑BS反映供应商需要协调库存补货和车辆调度的现实场景，可为供应链决策提供定量依据。 算法创新：结合分割（Split）算法构建可行解、进化局部搜索（ELS）增强全局探索、后优化阶段利用模型求解局部最优，形成三阶段的元启发式算法。 实例贡献：作者提出80个全新基准实例，考虑真实城市距离、异构车辆和时期依赖参数，为后续研究提供测试平台。
二、模型与数学 formulation
2.1 符号与变量
集合： 为客户集合（）， 包含供应商 ； 为时间周期集合，； 为第 个周期可用的车辆类型集合。
参数： 为客户或供应商在周期的单位库存持有成本；、 为车辆类型在周期的固定成本和单位行驶成本； 为客户的最大库存容量； 为客户的批量大小； 为客户在周期的需求； 为周期车辆类型的可用数量。
决策变量：
：若车辆类型在周期从节点驶向节点则为1； ：在周期由车辆配送给客户的货量； ：客户在周期的批次数； ：周期客户或供应商结束时的库存水平； ：在弧上运载的货量，用于检查载重约束。
2.2 目标函数
目标最小化所有时期的库存持有成本、车辆使用的固定成本及运输行驶成本：
其中第一项为客户和供应商库存持有成本；第二项为各车类型在周期从供应商出发的固定成本；第三项为每条弧的运输成本。
2.3 库存与配送约束
库存动态及配送决策满足以下约束：
初始库存
供应商库存平衡
客户库存平衡
库存容量
车辆容量与访问关联
批量约束
2.4 车辆流与载重约束
车辆流守恒
禁止同周期分割配送：每个客户在一个周期只能由一辆车服务
车辆供应限制
无货不访约束（如配送量为零则不造访）
载重流平衡：每个客户的车辆载重变化等于所配送的货量
载重与路径关联
变量域
通过上述约束，模型不仅考虑了车辆流的平衡，而且保证了配送量与访问决策的一致性以及客户批量交付要求。
三、分割‑嵌入元启发式（SEMPO）框架
为求解HIRP‑BS，作者提出了三阶段的Split‑Embedded Metaheuristic with Post‑Optimization（SEMPO）算法，如图所示（图1取自Fig.1）：
3.1 分割算法（Split）: 巨型环生成与分割
3.1.1 巨型环生成
为处理多期决策，作者采用了一个多期巨型环（giant tour）概念：将所有计划要访问的客户按时间顺序串接成一个序列，其中每个元素为三元组，表示在时期向客户发送货量。生成步骤包括：
计算最晚发货时刻：从最早时期到期末，估计若不配送时客户库存何时会变负，确定每个客户必须配送的最晚时期。
左移调整（left-shifting）：当某些时期的配送使库存超过上限时，将部分配送量左移到较早时期，以满足库存上限约束。
左移的单位为批量的整数倍，并确保不引起早期断供。
生成巨型环时还需随机化客户顺序以便后续分割操作寻找较低运输成本的解。为了在巨型环中让同一客户在相邻时期的配送尽量相邻放置，算法将上一时期集合 与当前时期集合 （）的交集 中的每个客户，以概率 插入到巨型环 在当前时期段的前 个可用位置（从左到右依次尝试，若失败则顺延；若到达最后一个位置仍失败，则回到第一个可用位置继续尝试）；其余客户以均匀概率随机插入。这样能更可能产生如图3所示的节约运输成本场景。 其中 。
图2展示在3个周期中5个客户的安排：第1条路径在第1期配送客户C；第2条路径属于提前配送场景，将客户D和A的发货提前到第1期；第3条路径将第2和第3期对客户E的需求合并于第2期配送一次，减少运输频次但增加库存成本。
图3描绘了将连续期服务的同一客户放在巨型环相邻位置所带来的成本节约。
3.1.2 巨型环分割
有了多期巨型环后，分割算法将其切分为多条具体路线并为每条路线分配车辆。其核心是利用带资源约束的最短路思想：在辅助有向图上，每个弧对应从巨型环第个客户到第个客户的一段连续访问，弧的权重包含固定成本、运输成本和库存成本。算法中使用标签（label）记录当前路线的信息，包括：
当前路段的起止客户以及分配的时期； 每个客户和供应商在该阶段的库存水平； 当前累计的运输和库存成本； 使用的车辆类型及其剩余车辆数； 二元指标标记客户在当前时期是否已服务。
标签在图中通过扩展操作生成并传播。为了避免组合爆炸，作者限制每个节点保留的标签数量，并按成本升序维护标签列表。
标签扩展中主要有两种情形：
同期插入：新客户与当前路线所处时期相同，则需更新路径成本：将旧的收尾段替换为通过的两条新弧；库存成本按式(24)–(29)调整，更新客户与供应商库存以及车辆使用情况。 跨期插入：当新客户在未来时期时，又分为客户尚未出现在当前路线和已出现两种情况（图4、图5、图6）。若客户未出现，更新方式与同期插入类似；若客户已在路线中，则无需新增运输弧，仅更新库存和提前发货的费用。
以下三幅图描述了不同情况下的插入操作：
算法对每个节点循环遍历可行标签并扩展所有可能的车辆类型，直到全部节点处理完毕。如果某个节点的标签列表达到上限，算法会丢弃成本最高的标签以控制计算量。分割完成后，依据标签中的父节点和索引可追溯出一组完整的路线。
3.2 进化局部搜索（Evolutionary Local Search）
分割算法得到的解可能距离最优还有差距，因而作者设计了进化局部搜索（ELS）阶段：
变异：随机选择同一时期的个客户在巨型环中重新排列，以保持库存平衡，产生新巨型环。 评估：对每个新的应用Split算法得到解。 局部搜索：在解中利用重插入（reinsertion）和2‑opt两种邻域操作改进路线，既可在同一路线内部，也可在不同路线之间；为控制搜索效率，不考虑跨时期操作。 自适应调整：四种邻域操作通过概率动态选取，若某个操作产生改进，其概率增加，其他操作概率相应减少，保证搜索集中于有效邻域。
ELS重复执行，直到在连续若干次迭代中没有改进为止。
3.3 后优化阶段 (Post-Optimization)
ELS 取得的最优解 可能仍有改进空间，作者提出后优化模型以小规模修改路线求得更优解。关键思想包括：
固定现有路径结构设
其中 为 ELS 最优解对应的二元参数（若 则 ，否则为 0）， 为各期各客户的配送量。在线性模型中 为决策变量。
引入新的二元变量 表示二者差异的绝对值，用以下线性约束替代 （式 (36)）：
限制修改幅度设置自由度 ，用所有弧变更量之和来度量允许的修改范围：
在第 次迭代，将可行区域限制为区间
其中 为上一迭代的最大弧变更数， 为本次允许的增量；若某一迭代无可行解，则在下一迭代加倍允许偏差（例如 ），以扩大搜索空间（见 图 7）。
迭代求解以 ELS 最优解 为初始解，逐步增加自由度进行 MILP 求解，获得序列解 ；若到达给定的最大距离 （相对 ）或迭代/时间上限 (、) 则终止。整个过程中 固定不变，搜索空间始终围绕起始解并在每次迭代由 进行约束与收缩。
该阶段结合模型的精确性和ELS解的启发性，在局部邻域内进一步降低成本。
四、遇到的困难与应对策略
异构车辆与批量交付导致模型复杂。车辆类型不同，批量交付使配送量必须为固定批次，需求与库存成本随时间变化，传统IRP的Dominance规则无法直接裁剪搜索空间。
应对策略: 作者采用巨型环分割方法将问题分解为一系列单车路径问题，并使用标签记录各客户的库存水平和车辆余量，从而同时考虑库存和车辆约束。 巨型环搜索空间巨大。客户在多期多次出现，若不加限制，标签数量会指数增长。
应对策略: 在分割算法中限制每个节点的标签数量，只保留成本较低的标签，并通过概率插入将可能在相邻时期服务的客户相邻放置，减少潜在扩展的分支。 局部搜索可能陷入局部最优。
应对策略: 引入进化局部搜索与自适应邻域选择，当某个邻域操作带来改进时，提高其选择概率，这种机制类似学习型元启发式，可有效平衡探索与利用。 全局最优难以保证。MILP求解器在大实例中难以求得最优解。
应对策略: 后优化阶段结合固定解和有限幅度修改，通过逐步扩大自由度探索邻域，找到比ELS更优的解，同时将计算时间限制在合理范围。
五、算例与结果分析
5.1 新基准实例构建
文章在Github发布了80个HIRP‑BS实例，主要特征包括：
规模分组：分为小规模（13个实例）、中规模（57个实例）和大规模（10个实例），客户数从19到183不等。 时间跨度：每个实例的周期数分别为7、14、21或28。 数据来源：城市之间的距离采用Duhamel等人（2012）提出的真实法国城市距离矩阵；库存持有成本参考Archetti等人（2007）的IRP实例；车辆类型各具固定和可变成本以及容量限制。 特性比较：与传统IRP实例相比，本研究实例考虑时期依赖的需求和库存成本、异构车队以及固定批量，见表2（文章）。
5.2 小规模实例比较
作者对Archetti等人（2007）的经典IRP实例进行测试，发现SEMPO算法提供的解与最佳已知解间平均差距仅2%，且平均求解时间约11秒，远快于MILP模型的33分钟。例如实例abs(5,30,3,1)的最优值9773.90在0.2秒内即被SEMPO找到。
对于自行构造的小规模HIRP‑BS实例，SEMPO与MILP模型的比较表明：MILP在一小时内仅对部分实例求得可行解，而SEMPO对所有实例均能在850秒内找到高质量解，平均最优解成本与MILP线性松弛解的差距约0.31%，且四个实例的解优于MILP。图8展示了SEMPO算法与MILP模型在两个典型实例上的收敛过程：某些实例中MILP最终找到稍好解（图8a）；而在另一些实例中SEMPO在整个求解过程中都优于MILP（图8b）。
5.3 中大型实例分析
对于中等规模实例（57个），MILP模型无法在限定时间内找到任何可行解，因而作者仅比较SEMPO与MILP线性松弛解。结果显示SEMPO提供的解与松弛下界平均差距仅8.53%，平均约20分钟即可找到最优解。这表明SEMPO在大规模异构IRP中具有较强的求解能力。
对于大型实例，SEMPO仍能在合理时间内找到可行解。由于后优化阶段对大实例计算量较大，作者仅使用分割和ELS阶段，仍取得满意结果。
图9比较了不同场景（是否考虑批量约束和是否使用异构车辆）下MILP求解上界和下界随时间演化的情况。可以看出在有异构车辆和批量约束时模型收敛速度最慢，而取消批量约束或考虑同质车队可加快收敛。
六、研究结论与管理启示
研究贡献：本文提出的HIRP‑BS模型同时考虑异构车队、批量交付及时期依赖的需求与成本，是对经典IRP的重要扩展。通过严谨的MILP模型和创新的SEMPO算法，作者展示了如何将多阶段库存和车辆决策有效耦合，并开发出高效求解策略。大量算例验证了SEMPO在求解效率和解质量上的优越性，尤其是在MILP无法在合理时间内求得解的大规模实例中。
管理启示：
批量策略的权衡：批量配送可减少车辆启用次数和固定成本，但会增加客户库存持有成本。SEMPO算法显示适度提前配送能显著降低运输成本。 车辆异构的重要性：现实供应链往往拥有不同载重和成本的车辆。本研究模型表明根据需求匹配合适的车辆组合，可有效减少固定和变动运输成本。 算法应用：SEMPO框架为企业在面对复杂库存路径决策时提供了一个可行的优化工具，特别适用于需求和成本随时间波动且配送批量有限制的场景。其分割与进化局部搜索相结合的方法也为其他组合优化问题提供了启示。
未来工作可以考虑将不确定需求和多级供应链加入HIRP‑BS模型，并进一步提升后优化阶段的效率。此外，开放的基准实例为社区提供了进一步改进算法的基础。
文章须知
推文编辑：单子叶
责任编辑：弓仪长
原文链接：https://doi.org/10.1016/j.ejor.2025.05.044
