编者按：

电商物流网络正在变得越来越灵活：商品种类多、单品销量小、需求变化快，企业不一定自建仓库，而是更倾向于租赁仓储空间或使用第三方物流节点。这意味着，传统“起点和终点已知、只决定 hub 位置和路径”的枢纽选址模型，已经很难完整刻画电商企业的真实决策。本文研究的Flow Hub Location Problem（流枢纽选址问题，FHLP） 正是从这一背景出发：它不仅决定哪些 hub 要租、货物流如何运输，还同时决定每类商品从哪个供应商发出、送到哪个客户区域附近的履约点。为了求解这一大规模混合整数规划问题，作者提出了一个机器学习增强的 Benders 分解算法，让机器学习不再是黑箱替代优化，而是作为一种**“可解释的变量筛选工具”嵌入到精确优化**过程中。

1.引言

过去的Hub Location Problem（枢纽选址问题，HLP）通常假设：每一票货的起点和终点已经确定，企业只需要决定中间经过哪些枢纽、如何路由。但电商企业的逻辑并不完全一样。

对于中小型电商平台来说，同一类商品可能有多个供应商，不同客户区域附近也可能有多个可选履约点。由于商品销量相对分散，企业没有必要长期绑定某一个固定仓库；相反，租赁仓库或第三方物流空间让它们可以更频繁地调整物流网络。这样一来，网络设计问题就不再只是“选哪些枢纽并规划路线”，而变成了一个更综合的问题：

• 哪些供应商负责哪些商品？
• 哪些履约点服务哪些客户区域？
• 哪些仓库或枢纽值得租？
• 货物流应该经过一个枢纽，还是两个枢纽？

这正是本文提出 Flow Hub Location Problem（流枢纽选址问题，FHLP）的出发点。传统 HLP 通常假设货流的起点和终点已知，只需决定 hub 选址和路径分配；但在电商物流网络中，企业往往需要同时调整供应商、履约点、仓储节点和运输路径。为刻画这种更灵活、可重构的履约网络，FHLP 将起终点选择、枢纽租赁和货流分配放在同一个模型中联合优化。也正因为如此，FHLP 的问题规模和求解难度都显著高于传统 HLP（两个模型的区别见图1）。

2.研究问题

本文要解决的核心问题FHLP可以概括为：在电商物流网络中，如何同时决定每类商品的供应商（起点）、履约点（终点）、仓储枢纽以及运输路径，并在大规模候选节点和商品流下高效求解这一联合优化问题。

从模型上看，本文将电商物流网络表示为一个有向网络$G=(N,A)$。其中，$H$表示候选枢纽集合，$K$表示商品流集合。对每一类商品流$k\in K$，其需求量为$w_k$，可选供应商集合为$O_k$，可选履约点集合为$D_k$。也就是说，商品$k$并不是从固定起点发往固定终点，而是需要在一组候选起点和终点中进行选择。模型中的关键决策变量决包括三类：商品流如何经过一个或两个 hub 运输，是否租用某个枢纽，以及某个商品是否选择某个起点/终点，具体如下：

$x_{od{h}_1{h}_{2}k}$：商品$k$有多少比例沿着$o\to h_1\to h_2\to d$的路径运输；

$$z_h=\{\begin{array}{ll}1,& \text{如果租用 hub }h,\\ 0,& \text{否则，}\end{array}$$

$$y_{ok}=\{\begin{array}{ll}1,& \text{如果选择节点 }o\text{ 作为商品 }k\text{ 的 origin，}\\ 0,& \text{否则，}\end{array}$$

$$u_{dk}=\{\begin{array}{ll}1,& \text{如果选择节点 }d\text{ 作为商品 }k\text{ 的 destination，}\\ 0,& \text{否则。}\end{array}$$

目标是最小化总成本，包括枢纽租赁成本、运输成本，以及起点/终点的分配成本。约束主要包括：每类商品的需求必须被完全满足；只有被租用的枢纽才能被货流经过；商品从被选中的起点发出、送往被选中的终点；同时，起点和终点的服务量不能超过各自容量限制。具体模型如下：

3.求解方法

首先，作者利用 FHLP 路径结构做变量删减，把原始运输变量$x_{od{h}_1{h}_{2}k}$改写为基于hub edge的$x_{odek}$。文中定义$E$为所有包含一个或两个枢纽的子集：如果只包含一个枢纽，则 e={e1}e=\{e_1\}e={e1​}；如果包含两个枢纽，则 e={e1,e2}e=\{e_1,e_2\}e={e1​,e2​}。因此，作者利用问题的成本结构和路径支配关系，提前删除不可能出现在最优解中的运输路径变量。例如，如果经过两个 hub 的路径成本高于只经过其中一个枢纽，则该 two-hub path 可以直接排除。

本文的主算法是 Learning-empowered Benders Decomposition（机器学习增强的 Benders 分解，LEBD）。它的基本思路仍然是传统Benders分解，将“离散选址/分配决策”和“连续货流运输决策”分开处理，主问题只保留$z_h,y_{ok},u_{dk}$，也就是决定租哪些枢纽、选择哪些起点和终点；在这些选择给定后，子问题再决定连续运输变量$x$。但传统Benders分解也有一个问题：随着 cuts 不断加入，主问题会越来越大，收敛速度可能变慢。

本文的关键创新在于引入机器学习来提前判断：哪些枢纽在最优解中很可能不会被使用？

作者使用 logistic regression 估计每个候选枢纽变量在最优解中取 1 的概率，即该枢纽被租用或打开的可能性。对于预测值较低的枢纽，算法将其视为低价值候选节点，并结合 learning-empowered elimination tests 和 variable reduction procedures 缩小主问题和子问题规模。其中训练数据来自小规模实例，获得最优解、拉格朗日松弛结果、Benders 过程信息以及其他问题特征。模型训练好之后，就可以在大规模实例中给出枢纽被关闭的可能性，然后指导消除检验（elimination test）和变量删减（variable reduction）。关键在于，模型没有用机器学习替代优化，而是让机器学习帮助优化模型缩小搜索空间，从而提升 Benders 分解的效率。

除此之外，作者还使用了基于聚类的多商品流Benders重构，即将起点/终点结构相似的商品分成若干类别（见图2），不再为每个商品都单独生成 Benders cuts，而是按商品类别生成 cuts，从而减少主问题规模并提升收敛效率；还通过拉格朗日松弛快速生成较好的初始解，为 Benders 分解提供更好的初始上界，从而加快后续迭代。

4.数值实验

为了验证LEBD算法在求解 FHLP 中的有效性，作者基于 Australia Post（AP）数据生成了一系列不同规模的测试算例。该数据来源于澳大利亚悉尼的邮政配送网络，包含 200 个代表邮政区域的节点；当测试规模超过 200 个节点时，作者进一步外推节点坐标，以构造更大规模的算例。实验主要关注两个问题：第一，文中提出的各类加速技术如何提升 Benders 分解的效率；第二，与 CPLEX、自动 Benders 分解以及传统 elimination-test 方法相比，LEBD 是否能够在不同规模和参数设置下取得更好的求解表现。

4.1 算法增强技术实验

作者首先测试了不同算法增强技术对 Benders 分解性能的影响。基础版本为不加入任何增强的标准 Benders 分解（BSC），随后逐步加入拉格朗日松弛初始解、初始割平面（IC）、基于聚类的多商品流Benders重构（CMC）、Pareto-optimal cuts、机器学习增强的消除检验（LET）以及变量删减 (LVR)等模块。

实验结果表明，拉格朗日松弛可以略微改善初始解质量并缩短计算时间；IC对高容量算例更有效；CMC能明显减少迭代次数；LVR的作用最突出，在加入该模块后，测试算例均能求到最优解。最终，作者将包含 LGBD（集成拉格朗日松弛的 Benders 分解方法）、IC、CMC、LET 和 LVR 的组合确定为推荐版本，即 LEBD。统计检验也表明，该组合在 optimality gap 上显著优于其他组合。

4.2 参数敏感性与调参实验

为了进一步分析算法在哪些场景下更有效，作者构造了 SET1 测试集，共包含 390 个算例，覆盖不同容量水平、枢纽租赁成本、运输成本、需求水平、起点/终点候选数量等参数设置。结果显示，低容量、低枢纽成本、起点/终点候选集合较大的算例更难求解；高运输成本、低规模经济效应的算例也会增加求解难度。相比之下，运输成本的变化对算法性能影响较小。

作者进一步测试了一个关键参数：在 LEBD 第一阶段，机器学习模块应提前移除多少比例的候选枢纽（见图3）。实验发现，当第一阶段移除约 60% 的枢纽 时，算法整体表现最好。原因在于，这一比例既能显著缩小主问题规模，又不会明显增加误删风险。此时，被错误移除、但实际上应出现在最优解中的枢纽比例平均只有约 0.6%。如果继续提高移除比例，虽然模型会变得更小，但误删重要枢纽的可能性也会增加，反而可能影响最终解的质量。因此，LEBD 的关键不在于尽可能多地删除枢纽，而是在减少模型规模和避免误删关键枢纽之间取得平衡。

4.3 SET1 算法对比实验

在 SET1 的 390 个测试算例上，作者将 LEBD 与五类 benchmark 方法进行比较，包括 greedy heuristic（GRD）、直接调用 CPLEX（CPX）、CPLEX automatic Benders decomposition（ABD）、traditional elimination test（TET）以及 combinatorial elimination test（CET）。由于 GRD 无法提供下界，作者使用 LEBD 得到的 lower bound 来计算其 optimality gap。

从结果来看，LEBD 的表现最好。在 optimality gap 上，LEBD 的平均 gap 约为 0.02%，其他方法则在 0.1% 到 0.53% 之间。GRD 的表现最差，说明如果先聚合起点/终点再做枢纽选址，虽然计算更快，但容易牺牲整体系统成本。CPLEX automatic Benders 明显优于直接使用 CPLEX，说明 Benders cuts 对 FHLP 这类问题确实有帮助；但与 LEBD 相比，ABD 不能在求解过程中主动删除枢纽，主问题会随着 cuts 增加而变大，因此在大规模算例上收敛速度受到限制。

4.4 大规模算例实验

为了测试算法在更大规模场景下的稳定性，作者进一步构造了 SET2。该测试集包含不同节点规模的算例，其中一部分为低容量、中等枢纽租赁成本设置，另一部分为低容量、高枢纽租赁成本设置。

结果显示，在节点规模增大时，LEBD 依然保持了最好的总体表现。特别是在高枢纽租赁成本场景下，LEBD 的优势更加明显：对于 10 个节点规模在 225 到 450 之间的测试实例，LEBD 平均在 20 分钟内即可求到最优解；相比之下，CPLEX automatic Benders 在 1 小时内仍有约 2% 的平均 optimality gap。

这一结果也解释了 LEBD 为什么适合 FHLP。高枢纽租赁成本场景下，很多枢纽在最优解中确实不会被使用，因此机器学习模块可以较早识别并删除一批低价值枢纽。随着这些枢纽被移除，主问题和子问题同时变小，Benders cuts 生成速度加快，上下界差距缩小，进而又有助于进一步删除枢纽，形成一个良性循环。

总体来看，数值实验传递出的核心结论是：对于 FHLP 这类大规模、强耦合的电商物流网络设计问题，单纯依赖商业求解器或启发式方法都不够理想。LEBD 的优势来自“优化主导 + 机器学习辅助”的组合机制：Benders 分解负责保证模型求解的结构化推进，机器学习则帮助算法更早识别低价值 hub、缩小搜索空间，从而在保证解质量的同时显著提升求解效率。

5.结论

本文的价值不仅在于提出了面向电商物流场景的 FHLP 模型，也在于展示了一种较清晰的 ML + OR 融合思路：机器学习不直接替代优化决策，而是学习问题中的结构性信息，并将其用于变量缩减和剔除检验，从而帮助 Benders 分解更快收敛。与此同时，文章也强调了电商物流网络中联合优化的重要性。供应商选择、履约点选择、枢纽选址和运输路径高度耦合，若将这些决策割裂处理，可能得到局部合理但整体成本较高的方案；而 FHLP 将这些决策纳入同一优化框架，有助于更系统地权衡不同网络配置下的成本与效率。

参考文献：

Wu, T., Chen, W., Cordeau, J.-F., & Jans, R. (2025). Machine learning-empowered Benders decomposition for flow hub location in e-commerce. INFORMS Journal on Computing.