网络阻断问题是一种资源最优分配的网络优化问题，是运筹学、数学、经济学和计算机科学的重要分支。网络阻断是一类带有博弈特点的优化决策问题，该问题在军事战略、交通运输、基础设施保护等领域得到了广泛的应用。最短路径阻断是网络阻断问题中的一类经典问题，通常被建模成双层混合整数规划模型，以进行优化决策。以前的研究大多数仅针对在有限的阻断资源条件下，使得目标节点对之间的最短路径最大化，但很少研究如何通过对网络中的边进行阻断（扰动边或删除边），使得指定目标路径成为最短路径的问题，而这类问题在路径选择控制、最短路径匿名化等应用中具有重要的研究意义。因此，本文基于目标路径的最短路阻断问题，分别通过对路径扰动（扰动边）和路径攻击（删除边）的两种阻断方式设计了相应算法，对于扩展网络阻断问题的研究提供了重要的理论基础。本文主要的研究内容包括模型建立和算法设计，具体如下: 1）基于最少边-最小成本的双目标最短路径扰动问题的建模与算法设计。以扰动边的最短路径阻断问题为基础，在该问题中引入“边权扰动上限”的约束，通过建立基于最少边-最小成本的最短路径扰动模型，来优化网络阻断过程中的资源分配。同时，在经典的约束生成算法和强制路径算法的基础上，提出了最少边扰动算法来求解该类双目标混合整数规划模型，该算法能够减少阻断所需的扰动边数，从整体上优化阻断资源的消耗。最后，对该算法进行实验并对比分析了求解结果，实验表明:最少边扰动算法平均降低了27％的扰动边数，使得最短路径阻断问题更具有隐蔽性和可行性。 2）基于子图的最短路径攻击问题的建模与算法设计。以删除边的最短路径阻断问题为基础，在该问题中引入“有用子图”的图剪枝技术，通过建立基于子图的最短路径攻击模型，并提出了基于子图的路径攻击算法求解该模型，来优化在大规模网络阻断问题中算法的时间效率。其中，该算法通过利用图剪枝的动态优化特性，在保证最优解的前提下，可以有效地减少由于问题规模增大所导致运行时间过长的问题。最后，对该算法进行实验并对比分析了求解结果和运行效率，实验表明:基于子图的路径攻击算法改进策略相对原有算法的求解效率有着显著提升，从而扩展了可求解问题的规模。 综上，本文主要研究了基于目标路径的最短路径阻断问题，通过优化扰动和攻击的两种边阻断方式为该问题的研究提供了理论基础，充实了网络阻断的研究内容。
NETL
