在需求不明确的情况下，一个新的鲁棒容量限制枢纽拦截问题及其Benders分解方法

《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》：A new robust capacitated hub interdiction problem under ambiguous demand and its benders decomposition

多分配中转枢纽拦截问题与需求不确定性的鲁棒优化模型研究。基于子高斯分布构建模糊集，提出双层鲁棒优化模型并转化为混合整数线性规划，设计加速Benders分解算法实现高效求解，在CAB和TR数据集验证方法优势。

　　

刘美玉|高珊珊|刘奈琪

风险管理与金融工程实验室，河北大学数学与信息科学学院，保定，071002，河北，中国

摘要

在本文中，我们研究了多分配枢纽辐射网络上的容量限制枢纽拦截问题，并将其构建为一个双层优化模型。上层模型中的理性攻击者会拦截一部分枢纽，以最大化对下层模型中防御者的损害。由于枢纽的运营能力有限，拦截将导致需求无法满足，从而产生额外的惩罚成本。然而，实际上，城市物流运输的需求往往由于其固有的非稳定性和空间相关性而表现出显著的变化。因此，我们对需求不确定性进行了建模，以做出稳健的枢纽位置和路由决策。方法上，我们使用统计方法构建了一个基于次高斯的不确定性集，该集合包含了所有与已知需求均值、方差和支持信息一致的概率分布。我们在构建的不确定性集下开发了一个分布鲁棒的优化模型，然后将其重新构建为一个混合整数线性规划模型，这有助于我们设计出一个加速的Benders分解算法。特别是，我们得出了具有先验和后验概率保证的稳健解决方案。通过对著名的CAB数据集的案例研究，证明了我们优化方法在平衡稳健性和保守性方面的优势。此外，对TR数据集的计算结果表明，我们提出的算法优于CPLEX求解器。

引言

枢纽辐射网络在现实世界的物流运输中有着广泛的应用。枢纽辐射网络的主要优势是实现了规模经济。由于直接在众多起点-终点（O-D）对之间进行路由是不可行的，枢纽可以作为中间连接点，整合、分类并重新路由运输商品。然而，枢纽的高连接性使得它们在考虑运输风险时变得非常关键且脆弱。任何针对枢纽的攻击，无论是恶意拦截（例如人为威胁）还是意外中断（例如自然灾害），都会通过导致高运输成本、运输重组和贸易政策变化来影响全球供应链（Liu等人，2026年；Zhalechian等人，2018年）。例如，Egon暴风雪对法兰克福和希思罗等主要国际机场造成了严重破坏。¹巴黎发生的一系列故意攻击导致法国对其与卢森堡和比利时的边境实施了更严格的控制，此外还使比利时的运输公司损失了350万欧元。²无论攻击是直接的还是间接的，由此造成的重大经济损失都强调了在发生中断时进行枢纽网络管理的必要性。

为了识别枢纽辐射网络中的恶意攻击漏洞，我们采用了图1所示的枢纽拦截框架。在这个框架中，攻击者（拦截者）旨在最大化对防御者网络的损害，而防御者（运营商）则通过研究拦截后的路由重组来应对拦截并运营网络。最近已经研究了无容量限制的枢纽拦截问题（Ramamoorthy等人，2024年；Ullmert等人，2020年；Yin和Zhao，2021年）。然而，在大多数现实世界的物流系统中，特别是对于物流运营经理和供应链运营商来说，枢纽容量是一个关键问题，因为它与基础设施管理和商品运输都有关（Bhatt等人，2024年）。正是这种理想化模型与实际限制之间的关键差距激发了我们对容量限制枢纽拦截问题（CHIP）的研究。当枢纽因恶意攻击而中断时，剩余的运营枢纽的容量不足以满足之前通过被拦截枢纽路由的额外O-D需求。因此，运营商必须考虑由于服务能力下降而导致的未满足需求的惩罚成本（Bansal等人，2024年）。此外，由于容量限制，通过最有效的路线运输商品是不切实际的，特别是通过最近的可用枢纽，这会导致运输成本增加。由于恶意攻击严重影响了运输效率并带来了运输风险，多分配网络可以有效减少拦截的负面影响，从而实现更可靠的物流运输（An等人，2015年）。对于这样的网络，O-D需求从源节点发送/接收到多个枢纽，每个枢纽或路线运输有限的需求。

在拦截后的物流系统中，防御者无法及时制定响应策略，这种滞后效应可能会显著影响物流运输，进而影响需求的实现。此外，由于季节变化、经济波动等多种因素，需求通常表现出不确定性，导致与历史数据的偏差。变化的O-D需求可能导致枢纽容量利用率的明显波动，从而在不同枢纽之间造成使用不平衡。此外，短时间内不可预测的增加的交通流量可能导致枢纽容量不足，进一步导致高惩罚成本。为了制定实用且可靠的拦截后路由策略，考虑需求不确定性至关重要。在建模和优化不确定性时，随机优化（SO）方法依赖于指定的概率分布，然而，当现实世界的分布与训练集中的分布大相径庭时，可能会导致样本外性能不佳（Wang等人，2021年）。另一种常用的鲁棒优化（RO）方法构建不确定性集来模拟不确定性，但它通常会产生过于保守的决策，因为它忽略了不确定参数的分布信息（Vincent等人，2023年）。

考虑到所有上述因素，本文试图解决以下研究问题：

•

如何将需求不确定性纳入枢纽拦截中，以开发一个能够捕捉物流运输中需求特征的优化框架？

•

在需求不确定性的存在下，如何做出稳健和安全的拦截后决策？

•

如何克服所提出的优化模型中的固有难点，以便其在物流运输中的实际应用？

为了回答这些问题，我们采用了一种有前景的建模和优化方法，即分布鲁棒优化（DRO）方法，来考虑具有模糊分布特征的需求不确定性。在本文中，我们在基于次高斯的不确定性集下开发了一个新颖的双层分布鲁棒容量限制枢纽拦截（DRHI）模型，该模型受到模糊机会约束的约束，并结合了可调的概率水平，以更好地符合决策者对拦截后物流运输的偏好。所提出的新颖模型使我们能够做出稳健的拦截后路由决策。通过探索DRHI模型的结构特征，我们采用了鲁棒对应近似和基于对偶的重新构建方法，将其转换为混合整数线性规划（MILP）模型，并进一步设计了一个定制的Benders分解（BD）算法，以便在其大规模枢纽辐射网络上应用。

本文的贡献包括以下三个方面：

•

带有需求不确定性的Stackelberg枢纽拦截模型。我们开发了一个新的双层DRHI模型来捕捉攻击者-防御者Stackelberg博弈。通过用上下文信息对需求不确定性进行建模，我们提出的优化模型可以在潜在的拦截风险下弥合物流运输理论与实践之间的差距。据我们所知，需求不确定性在枢纽拦截领域尚未被探索过。

•

对于次高斯不确定性的概率保证。我们利用一些共享的统计信息（例如均值、方差）来做出免疫于不确定性的稳健拦截后路由决策。在次高斯不确定性下，我们得出了具有先验和后验概率保证的稳健解决方案，以控制拦截后的成本和容量水平。特别是，先验概率保证由多面体不确定性集的鲁棒复杂性控制，而后验概率保证取决于拦截后的路由决策。所获得的结论可以扩展到非独立情况。

•

所提出优化方法的优势。我们的数值实验展示了我们提出的优化方法的优势。利用需求的模糊分布信息，我们的DRO方法可以产生比现有研究中常用的经典RO和SO方法更少保守的稳健解决方案，并具有更好的样本外性能（Kargar和Mahmuto?ullar?，2022年；Rahmati等人，2022年）。在次高斯假设下，我们采用的均值-方差联合分布信息实现了改进的概率保证和更好的稳健性，与使用单一均值分布信息相比。然而，现有的鲁棒对应近似方法通常难以为其解决方案提供这样的概率保证（Jia等人，2020年），特别是在后验概率保证方面。

本文的结构如下：第2节全面回顾了与我们的研究相关的内容。第3节介绍了不确定性的来源，并介绍了我们的主要DRHI模型。第4节分析了我们的DRHI模型，然后设计了改进策略的BD算法用于其解决方案。我们在第5节展示了实验结果，第6节基于我们的发现提供了管理见解和讨论。第7节总结了本文。为了提高清晰度，我们提供了表1来展示本文中的术语。

章节片段

文献综述

本节回顾了关于拦截和不确定性的现有研究，特别关注枢纽拦截和枢纽位置问题。随后，我们讨论了本文与现有文献之间的差异。

问题陈述

考虑一个完整的无向多分配枢纽辐射网络。设I为所有节点的集合，其中i?∈?I和j?∈?I分别表示起点和终点节点。每个起点节点i和终点节点j之间存在需求流f_ij。一组节点J?I被指定为枢纽网络，其索引分别为u?∈?J和v?∈?J。集合J中有p个枢纽，即$\left|J\right|=p$。我们的CHIP定义在这样的网络上，涉及攻击者和防御者之间的Stackelberg博弈。

模型分析

本节为DRHI模型提供了一个结构化的解决方案框架，如图4所示。我们从第4.1节开始，为模糊机会约束推导出可行的近似值，特别关注先验和后验概率保证的稳健解决方案。然后第4.2节将得到的确定性双层模型重新构建为单层公式，我们在第4.3节进一步开发了BD算法。

实际案例中的方法实现

在本节中，我们进行数值实验来评估我们提出的DRHI模型的性能和BD算法的效率。我们首先分析预算约束如何影响枢纽的生存决策和总成本。然后，我们研究不确定性集大小与模型稳健性之间的关系。为了展示分布鲁棒性的价值，我们将我们的DRHI模型与基准模型进行了比较。此外，还进行了敏感性分析以评估

管理见解和讨论

根据上述实验发现，本文还提出了以下对运营商和物流运营经理有帮助的管理见解：

•

DRHI模型在不确定性下建立了一个双层框架，以捕捉拦截者和运营商之间的Stackelberg博弈，从拦截者的角度识别出具有高运输价值的枢纽。它帮助运营商做出可靠和安全的重新分配需求决策

结论

考虑到恶意攻击对存活枢纽城市和路由决策的潜在影响，本文研究了在需求不确定性下的CHIP。方法上，由于难以获得需求的完整分布信息，我们引入了DRO框架来模拟不确定需求，并提出了一个受到模糊机会约束的双层DRHI模型。为了使用部分分布信息捕捉可能真实的分布，我们

CRediT作者贡献声明

刘美玉：撰写——原始草稿，验证，软件，数据管理，概念化。高珊珊：撰写——审阅与编辑，验证，方法论，数据管理，概念化。刘奈琪：撰写——审阅与编辑，方法论，资金获取，概念化。

利益冲突声明

作者声明他们没有已知的竞争财务利益或个人关系可能影响本文报告的工作。