考虑时变需求的汽车零部件库存-路径问题：一种机器学习增强的分支定价方法
原文及链接见文末
一、研究背景与问题陈述
装配型制造业（如汽车生产）要求供应商在特定的时间窗内向整车厂的入库仓库送货，并满足装配线的动态零件需求。如果供应商的供应节奏不能与工厂需求吻合，就会引起库存成本和运输成本的矛盾，影响生产效率。在实际业务中：
需求随时间波动：装配线按计划批量消耗零件，不同周期的需求量差异很大，且存在提前期。 包装数量固定：零件以特定包装箱或托盘运输，数量离散，不能按连续变量自由分割。 多供应商与多车次：一条运输路径往往同时服务多个供应商，车辆可在一天中多次往返。
传统的车辆路径问题（VRP）仅关注配送路线，忽略了入库仓库的库存动态；而库存‑路径问题（Inventory‑Routing Problem, IRP）通常假设需求确定且平稳，包装可分割，不符合零件配送特点。本文提出 动态需求与固定包装的多周期库存‑路径问题（下称“问题”），旨在决定在有限的时间窗内如何安排车辆路线、发运批量以及库存补货，使仓库的 库存成本与运输成本之和最小。
文章通过示意图描述了动态需求和补货节奏：图 1 展示了某零件在不同时间段的需求曲线、包装批量以及补货节点，需求具有明显的波峰波谷；图 2 用例子展示了供应商与仓库之间的发货、库存波动以及多车多次路线。
二、数学模型与目标函数
2.1 主要决策变量
：第 辆车在周期 是否访问供应商 到 。 ：在周期 从供应商 发出的零件包装数。 ：周期 结束时仓库中来自供应商 的零件库存。 ：第 辆车在周期 是否派车（0/1）。
2.2 目标函数
综合考虑库存持有成本和运输成本，目标函数为最小化下面两部分之和：
其中 为存储供应商 零件的单价持有成本， 和 分别是库存成本系数与运输成本系数， 为派遣第 辆车的固定成本， 为车辆从 到 的行驶成本。该目标函数强调运输里程、派车次数与库存水平三者之间的平衡。
2.3 关键约束
库存动态约束：满足收支平衡关系：
其中 为周期 的需求。
分批包装约束： 只能为特定包装的整数倍。
容量与装载约束：每辆车每次访问供应商的装载量不能超过车辆容量。
路径连通约束：各车辆路线必须从仓库出发并返回仓库；每次线路满足单源多目的或多源多目的结构，不允许子巡回路径。
时间窗与多车多次约束：同一天中可启用多辆车，每辆车可执行多次配送。
模型由以上目标函数和约束组成，可视为一个包含 非线性固定费用、整数变量和复杂路径结构的混合整数规划。传统求解方法难以直接求解大规模实例。
三、求解算法：融合机器学习的分支定价法（BPL）
3.1 为什么选择分支定价
由于车辆路径的组合数量巨大，将模型直接转化为整数规划求解效率极低。本文采用 Dantzig–Wolfe 分解 将原问题拆分成主问题与若干子问题，利用 列生成（pricing） 方法逐渐加入有价值的车辆路径变量，再在分支定界框架下逼近整数解。该策略属于“分支定价‑割平面”（Branch‑and‑Price with Cut）。
主要流程如下（见图 3）：
初始化：构建可行初始列集（可能来自启发式生成的一组配送路径）。 求解主问题：固定当前列集求解线性松弛主问题得到影子价格。 定价问题：通过影子价格求解若干子问题（最短路径问题），找出负约化成本的路线；如果存在，则加入主问题列集。 若无可行列，则进入 整数分支：根据未整数变量进行分支，将问题拆分为若干子问题，递归求解。
3.2 引入机器学习提高效率
传统分支定价面临的一个难点是 搜索树的截枝效率，尤其在复杂约束下难以快速判断节点的优劣。为此，作者在分支定价框架中嵌入 在线回归模型 预测子问题的上界（图 4）。其关键思想包括：
特征选择：每个子问题可以抽取若干特征（例如当前库存状态、剩余需求、车辆数等）。 训练数据：在求解过程中不断积累已求解节点的真实上界与特征，对模型进行在线更新。 上界预测：对新节点预测其最优成本，提前判断是否值得继续扩展，以此决定 动态截枝。
这一机器学习模块既可以过滤掉明显不优的分支，也可以指导列生成优先引入潜力较大的路径，从而显著加速计算。
3.3 关键算法难点及其处理
图 5 比较了所提出的 预测上界 与真实上界之间的误差曲线，可见预测结果相当准确，误差很小。
四、实验设计与结果分析
4.1 数据和对比方法
作者基于 随机生成实例 和 某汽车制造厂真实数据 进行实验，实例规模从 5 天到 16 天不等，供应商数量从 10 到 65 个，车辆数从 1 到 3 辆。
对比算法包括：
CPLEX 商业求解器：直接求解整数规划的基准方法。 传统分支定价法（BP）：不含机器学习与混合策略。 本文提出的 BPL：分支定价 + 在线回归模型 + 混合分支策略。
性能指标包括计算时间、相对误差（近似解与最优解差距）和解决率等。
4.2 结果与讨论
算法效率：BPL 在大多数实例上显著减少了求解时间，相对于传统 BP 与 CPLEX，可在可接受误差范围内快速获得近似最优解。图 6 展示了不同分支策略的计算时间对比，混合策略（HBP）耗时最少。
图6 不同分支策略性能比较 库存/运输成本权衡：通过调节库存成本系数 与运输成本系数 ，总成本呈不同变化趋势。图 7 显示 增大时，系统倾向于减少库存而增加运输成本；图 8 显示 增大时，系统倾向于减少运输次数，导致库存上升。这说明选择合适的权重对结果影响显著。
图7 不同库存成本系数下的总成本变化 
图8 不同运输成本系数下的总成本变化 车辆配置与运营成本：实验还分析了 可用车辆数量 对总成本的影响（图 9）。车辆数增加可以降低运输频次并减少库存高峰，但车辆过多会使固定成本上升，表现为一个凸形的总成本曲线。适度的车辆配置能在成本和服务水平之间取得平衡。
图9 不同车队规模下的总成本与路线特征 对真实案例的适用性：在真实数据集上，BPL 能够在较短时间内给出与人工方案相似甚至更优的配送计划，显示出实际应用潜力。
五、总结与展望
本文针对汽车零部件供应链中的 动态需求与固定包装的库存‑路径问题 建立了新的数学模型，并提出了融合机器学习的 分支定价算法。研究的主要贡献可总结为：
问题创新：首次在 IRP 中考虑多周期、时间变需求与离散包装，共同优化库存与路径。 算法创新：基于 Dantzig–Wolfe 分解和列生成的分支定价框架，引入在线回归模型预测上界和混合分支策略，显著提升求解效率。 实验充分：在大量随机实例和实际案例上验证方法优越性，开展敏感性分析揭示成本权衡规律。
从结果来看，BPL 方法在保证解质量的同时大幅缩短计算时间，适用于中等规模的工业实例。未来研究方向包括：
将模型拓展到 不确定需求与路线时间窗，引入鲁棒或随机优化； 研究 动态学习机制，提高上界预测准确度； 推广到 跨工厂配送、共享车辆 等更复杂的供应链网络。
本文为制造业供应链中的库存‑路线优化提供了有价值的方法论和应用示范，对实践具有指导意义。
