Optimal Allocation of Protective Resources in Shortest-Path Networks
Optimal Allocation of Protective Resources in Shortest-Path Networks
复制标题
DOI：
10.1287/trsc.1100.0340
复制
发表时间：
2011-02
期刊：
影响因子：
--
通讯作者：
P. Cappanera;M. P. Scaparra
中科院分区：
文献类型：
--
作者：
P. Cappanera;M. P. Scaparra
本文介绍了一种博弈论方法，用于在网络组件之间分配保护资源，以最大限度地提高网络对外部干扰的鲁棒性。具体来说，我们考虑的是最短路径网络，在这种网络中，中断可能会导致受影响组件的交通流延迟，甚至导致某些组件完全丢失。提出了一种多层程序，在某些未受保护的部件出现最坏情况时，确定需要加固的部件集，以使供应节点与需求节点之间的最短路径长度最小。在此基础上，提出了一种隐式枚举算法来求解多级问题。该方法通过在枚举树的每个节点上启发式地解决低级拦截问题，并使用一些变量固定规则来降低低级问题的维数，从而简化了该方法。全面的计算研究表明，所提出的解决方法能够识别最优保护策略的网络显著规模。最后，研究了求解方法对问题参数变化的敏感性，如破坏程度和保护资源以及电弧长度和延迟的分布。
This article introduces a game-theoretic approach for allocating protection resources among the components of a network so as to maximize its robustness to external disruptions. Specifically, we consider shortest-path networks where disruptions may result in traffic flow delays through the affected components or even in the complete loss of some elements. A multilevel program is proposed to identify the set of components to harden so as to minimize the length of the shortest path between a supply node and a demand node after a worst-case disruption of some unprotected components. An implicit enumeration algorithm is then developed to solve the multilevel problem to optimality. The approach is streamlined by solving the lower-level interdiction problem heuristically at each node of an enumeration tree and by using some variable fixing rules to reduce the dimension of the lower-level problems. A thorough computational investigation demonstrates that the proposed solution method is able to identify optimal protection strategies for networks of significant size. The paper is concluded with a study of the sensitivity of the solution approach to variations of the problem parameters such as the level of disruption and protective resources and the distribution of the arc lengths and delays.