论文作者信息：Li Meng, Wandelt Sebastian, Cai Kaiquan, and Sun Xiaoqian. Machine learning augmented approaches for hub location problems[J]. Computers & Operations Research, 2023, 154: 106188.
推文作者：李萌
编者按
针对交通、物流网络中的枢纽选址问题，创新提出了一个机器学习增强组合优化算法的求解框架。在此算法框架的基础上，为单分配枢纽中位问题（uncapacitated single allocation hub median problem, USApHMP）设计了两个基于图神经网络改进的启发式求解算法。仿真和标准数据集上的大量实验结果表明，所提出的改进算法在求解质量、计算效率的综合表现上优于传统的组合优化方法。这也是机器学习方法在轴辐式网络设计应用中的首次尝试。
1. 背景
在现代物流、交通运输系统中，运输网络结构的设计对于提高效率和降低成本至关重要。其中，轴辐式网络结构（Hub-and-Spoke）是一种常见的设计模式。在轴辐式网络中，以枢纽为轴，负责合并、分发节点之间的流量；以枢纽节点与非枢纽节点之间的运输线路为辐，通过辐线将流量转发至各个非枢纽节点。轴辐式网络通过集中处理流量，优化资源配置，在规模经济效益下产生成本折扣，降低了运输成本。此外，该网络结构减少了出发点-目的地节点（Origin-Destination, O-D）之间的连接，提高了运输系统的稳定性。
枢纽选址问题（Hub Location Problems, HLPs）涉及在轴辐式网络中确定枢纽节点，并确定每个O–D需求的所有运输路线。随着货运和客运需求的激增，枢纽选址问题受到了物流和交通运输领域的广泛关注，特别是在航空客运方面。然而，该问题涉及许多因素，如地理空间信息和O–D对之间的运输需求流量。此外，在大多数情况下，枢纽选址是NP难问题，这使得大规模问题求解变得困难。因此，迫切需要一种高效的方法来应对这一挑战。
在求解枢纽选址问题上，传统的组合优化算法多为精确算法和启发式算法。精确算法（例如Benders分解[1]、拉格朗日松弛[2]）通过不断更新上界和下界直到收敛，来获取最优解，但通常计算时间较长，不适用于求解大规模实例。启发式算法包括禁忌搜索算法[3]、模拟退火算法[4]、变邻域搜索算法[5]等，求解速度较快，但容易陷入局部最优解。
随着人工智能技术的快速发展，机器学习在组合优化领域的研究引起了广泛关注。将机器学习应用于组合优化，一方面考虑用机器学习替代计算成本高昂的操作，从而快速获取近似解；另一方面，当专家知识在组合优化问题中不够充分时，机器学习能够通过经验探索来提升现有的决策水平[6]。
2. 算法框架
该算法框架是基于机器学习的两阶段提升算法。其设计的思想为：第一阶段，利用机器学习模型输出节点被选为枢纽的概率/排序分数，从而得到一个潜在的枢纽集合；第二阶段，将枢纽的排序分数、潜在的枢纽集合嵌入到启发式算法中，以提升求解质量和运算效率。算法框架如图1所示。
图1：算法框架图
在上述算法框架下，为枢纽选址问题设计具体的算法时，有两个主要问题需要考虑：
（1）如何设计机器学习模型，使其能够输出合理的节点分数？
（2）如何将得到的枢纽排序分数/潜在的枢纽集合嵌入到启发式算法中？
作者以一类经典的枢纽选址问题：单分配枢纽中位问题（uncapacitated single allocation hub median problem, USApHMP）为具体研究对象，在上述算法框架基础上，提出了两个改进的启发式算法。
3. USApHMP：问题建模
USApHMP问题中，选择的枢纽数量需为个，每个非枢纽节点只能与一个枢纽节点连通（即，单分配），枢纽节点之间是完全连通的。该问题可建模为如下所示的混合整数规划模型，其中，节点, 表示从节点到节点的运输需求；表示两个节点之间的距离；为节点产生的总的运输需求（从运输至其他所有节点），而表示从其他节点到的运输需求之和。参数， 和 分别为枢纽之间运输、从非枢纽节点到枢纽节点，以及从枢纽节点到非枢纽节点之间运输的成本折扣系数。决策变量表示节点产生的运输需求中，经由枢纽边运输的需求量，表示节点是否分配到枢纽节点。
目标函数为最小化总运输成本。约束条件（2）表示选取的枢纽数量为；约束条件（3）保证了每个节点只能分配给一个枢纽节点；约束条件（4）表示了只有枢纽节点才能被分配；公式（5）是一个流平衡的约束；约束条件（6）和（7）定义了决策变量的取值范围。
4. USApHMP：求解算法设计
在所提出的算法框架下，作者设计了基于深度学习改进的启发式算法以求解USApHMP。算法流程如图2所示。针对轴辐式网络特性，构造了多类型图、多类型特征输入机制，并构建了基于图神经网络的深度学习模型DLHr (a deep-learning based probabilistic hub-ranker)，输出节点排序分数。该分数可反映节点被选为枢纽节点的概率，从而生成一个潜在的枢纽集合。将输出结果分别嵌入基于聚类的潜在枢纽集合算法（clustering-based potential hub sets algorithm, CBS）和变邻域搜索算法（general variable neighborhood search , GVNS）中，从而得到两个改进的启发式算法DL-CBS和DL-GVNS。
图2：基于深度学习改进的启发式算法流程图
（1）多类型图
为了捕捉运输网络中的重要信息，构建了两种类型的图：即需求-流量图和空间-距离图，分别反映了该运输系统中，节点之间的流量分布关系，和节点的地理空间分布信息。构建方法如下：
需求-流量图：为了捕捉网络中的需求流量信息，构建两个有向加权图，定义为和，分别用来描述网络中节点的需求生成量（）和需求吸引量（）。
在图中，为节点，为边，表示邻接矩阵，计算公式为：
其中，表示节点为的邻居节点。是的邻居节点集合，其大小可以由参数控制。简单来说，节点到的需求流量越大，则被判定为邻居节点的可能性越大。
同样地，在图中，为边，表示邻接矩阵，计算公式为：
其中，表示节点为的邻居节点。是的邻居节点集合，其大小同样由参数控制。节点到节点的需求流量越大，则被判定为邻居节点的可能性越大。
空间-距离图：为了捕捉网络中节点的空间分布信息，构建一个无向加权图，其中为节点，为边，表示邻接矩阵，计算公式为：
其中，表示节点为的邻居节点。是的邻居节点集合，其大小由参数控制。节点到节点的距离越近，则被判定为邻居节点的可能性越大。
（2）多类型特征
交通特征：计算每个节点聚集的运输需求流量，和其他节点到该节点的距离之和，计算公式如下：
空间特征：引入重心来生成节点的空间特征。首先，计算重心的坐标，然后计算每个节点到重心的距离，以及表示节点相对于重心的方向的变量。具体表示方式为：以重心为圆点，将网络划分为若干个扇区，判断节点在哪一个扇区内，从而估计节点相对于重心的方向信息（如图3所示）。对于特征的构造思路，来源于对枢纽选址问题最优解的分析，即枢纽节点位于重心的不同方向，且多个枢纽节点通常呈现包围重心的分布趋势。
图3：基于网络重心的划分方式示意图
（3）DLHr模型
DLHr的整体框架如图4所示。DLHr的输入为上述方法生成的多类型图和多类型节点特征。DLHr的结构可看作三个部分：编码器（Encoder）、跳跃知识层（JK layer）和解码器（Decoder）。编码器的作用是将每个节点映射到一个高维嵌入向量，这些嵌入向量能够捕捉节点的空间位置和需求分布等关键信息。在编码器中，利用门控循环单元（Gated Recurrent Unit, GRU）聚集节点特征和邻居节点的嵌入向量。JK层有助于减少模型在重复多层时可能出现的过平滑或平滑不足的问题[7]，从而提升模型的表现。解码器则将每个节点的嵌入向量映射为一个标量分数，用于节点排序。
图4：DLHr模型框架
标签生成：利用CPLEX求解器求解USApHMP问题，以生成小规模网络下的最优解。在求解每一个问题时，设置不同的参数 （枢纽的数量）和（折扣系数），统计不同参数下的所有最优解中，每个节点被选为枢纽的频率，作为该节点的枢纽排序分数。计算公式如下：
其中，，和分别为参数 （枢纽的数量）和（折扣系数）的集合。是求解每个问题的最优解中的枢纽节点集合。
损失函数计算：模型本质上学习的是节点的排序，而不是具体的分数。因此，DLHr采用了成对排序损失函数（Pairwise Ranking Loss)。给定一个节点对，节点和的标签值分别为和，满足关系。为了学习节点的相对排序，DLHr通过最小化如下所示的损失函数，来推断出。其中，为DLHr输出的节点的值。
训练伪代码：
图5：DLHr模型训练伪代码
（4）DL-CBS和DL-GVNS算法
DL-CBS：
DL-CBS算法中，用DLHr模型学习的节点排序来替换CBS算法中根据重要性指标（Imp）进行的节点排序。CBS算法[8]是基于对节点重要性排序和聚类，生成一些约束条件。将这些约束条件加到原本的数学模型上，从而缩小解空间，加快求解效率。CBS算法中，选取了几个重要性指标（例如，）对节点进行排序。因此，将DLHr模型节点排序结果应用到CBS算法中，得到改进的启发式算法，即DL-CBS算法。
DL-GVNS:
DL-GVNS可以看作用DLHr模型学习的节点排序来指导GVNS[5]的搜索过程。具体来说，首先根据DLHr模型输出的节点分数对节点进行排序，生成一个潜在枢纽集合，然后将这个枢纽集合作为GVNS的初始解。此外，在执行不同的邻域搜索时，根据节点排序顺序来进行搜索。
5. 实验分析
（1）实验数据集
实验数据集包括用于训练和测试的仿真数据集，以及用来验证DL-CBS和DL-GVNS算法表现的标准数据集。数据集和DLHr代码可从https://github.com/Koi-goodluck/AILS-instances获取。
仿真数据集：生成11,000个不同的仿真网络，用于DLHr模型的训练、验证和测试。其中，训练集包含10,000个，验证集和测试集分别为500个。每个仿真网络的节点数量，其中，节点坐标随机均匀分布，利用欧式距离公式计算任意两个节点之间的距离。对于运输需求，首先，按照幂律分布生成各节点（区域）的人口，再根据人口重力吸引模型生成任意两个节点之间的运输需求。
标准数据集：
| 数据集 | 来源 | 说明 | 规模（节点数量） |
|---|---|---|---|
| CAB | 民航 | 美国城市之间的航空客运 | 100 |
| TR | 地面交通 | 土耳其城市之间的地面交通 | 81 |
| AP | 邮政 | 澳大利亚悉尼的邮政业务 | 200 |
（2）DLHr节点排序表现
评价指标为Top-准确率，即模型所识别的前个节点占真实排名中前个节点的比率，计算公式如下：
选取逻辑回归（Logistic Regression, LR）、多层感知机（Multilayer Perception, MLP）、图卷积网络（Graph Convolution Network，GCN）、GraphSAGE和节点重要性指标（Imp）作为与DLHr模型对比的基准方法，实验结果如图6所示：
图6：节点排序评估结果对比
由实验结果可知，DLHr在枢纽节点排序任务上明显优于其他基准方法，而且在从2~10变化时，都取得了最高的Top-准确率。此外，基于图结构学习的方法（DLHr, GraphSAGE和GCN）也明显优于没有图输入的方法。
（3）DL-CBS和DL-GVNS算法的表现
在节点数量为100和200的仿真网络（SYN100、SYN200）和标准数据集上，对比了DL-CBS和CBS、DL-GVNS和GVNS算法求解USApHMP问题的实验结果。
CBS和DL-CBS在不同数据集上，对于枢纽选址问题求解质量和求解效率的对比如图7所示。其中，横坐标表示相较于CPLEX求解器，算法在求解时间上的提升百分比；纵坐标表示算法所得到的解与最优解之间的差距。图7中，蓝色的点表示CBS算法家族中的一种，例如"IR"表示文献[8]中提出的"IRCBS"算法；红色的点表示机器学习改进的算法，例如"DL-IR"表示利用DLHr节点排序结果改进的"IRCBS"算法。可以观察到，红色的点总是位于其对应的蓝色点的下方，说明改进后的算法在求解质量上有明显提升。
图7：CBS和DL-CBS实验结果对比
DL-GVNS和GVNS在不同数据集上，对于枢纽选址问题求解质量的对比如图8所示。对于的小规模实例，GVNS和DL-GVNS的性能没有明显区别，即均能快速找到最优解。然而，对于 的大规模实例，在选取枢纽数量较多的情况下（例如，），DL-GVNS表现更好，体现在它能够找到质量更好的解。如图8所示，负差距（Gap<0）表示相对于GVNS，DL-GVNS的解质量更好。
图8：GVNS和DL-GVNS实验结果对比
6. 总结
论文中，作者提出了一个用于求解枢纽选址问题的两阶段算法框架，并在此框架基础上，针对一类经典的枢纽选址问题（USApHMP）设计了两个基于深度学习改进的启发式算法。具体来说，提出了一个基于图网络的枢纽节点排序模型DLHr。根据模型输出的节点分数，可对节点进行排序，从而生成一个潜在的枢纽集合。将节点排序结果/潜在枢纽集合嵌入到启发式算法中，以提升算法的求解质量和运算效率。此外，未来研究中，可考虑在该算法框架基础上，设计求解其他类型枢纽选址问题的方法。另一方面，也可考虑应用人工智能的其他技术方法（强化学习等），指导或提升传统的组合优化算法。
参考文献：
[1] de Camargo R S, de Miranda G, O’Kelly M E, et al. Formulations and decompo- sition methods for the incomplete hub location network design problem with and without hop-constraints[J/OL]. Applied Mathematical Modelling, 2017, 51: 274 – 301.
[2] Contreras I, Díaz J A, Fernández E. Branch and price for large-scale capacitated hub location problems with single assignment[J/OL]. INFORMS Journal on Computing, 2011, 23(1): 41–55.
[3] Pamuk F S, Sepil C. A solution to the hub center problem via a single-relocation algorithm with tabu search[J/OL]. IIE Transactions, 2001, 33(5): 399–411.
[4] Azizi N, Chauhan S, Salhi S, et al. The impact of hub failure in hub-and-spoke networks: Mathematical formulations and solution techniques[J]. Computers & Operations Research, 2016, 65: 174–188.
[5] Ilić A, Urošević D, Brimberg J, et al. A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem[J]. European Journal of Operational Research, 2010, 206(2): 289–300.
[6] Bengio Y, Lodi A, Prouvost A. Machine learning for combinatorial optimization: a methodological tour d’horizon[J]. European Journal of Operational Research, 2021, 290(2): 405-421.
[7] Xu K, Li C, Tian Y, et al. Representation learning on graphs with jumping knowledge networks[C]//International Conference on Machine Learning. PMLR, 2018: 5453-5462.
[8] Peker M, Kara B Y, Campbell J F, et al. Spatial analysis of single allocation hub location problems[J]. Networks and Spatial Economics, 2016, 16(4): 1075-1101.
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
推文作者：李萌
责任编辑：缪昌昊，张云天
微信编辑：疑疑
文章由『运筹OR帷幄』原创发布
如需转载请在公众号后台获取转载须知
关注我们
FOLLOW US
