Improved max-flow min-cut algorithms in a circular disk failure model with application to a road network
Improved max-flow min-cut algorithms in a circular disk failure model with application to a road network
复制标题
改进的圆盘故障模型中的最大流量最小切割算法及其在路网中的应用
DOI：
10.1016/j.ejor.2015.07.035
复制
发表时间：
2016
影响因子：
6.4
通讯作者：
and Kazuo Murota
中科院分区：
文献类型：
--
作者：
Kensuke Otsuki;Yusuke Kobayashi;and Kazuo Murota
在网络可靠性评估中，其目标是对网络可靠性进行合理的建模，并在实际时间内进行计算。我们可以考虑各种网络可靠性模型，Bienstock（1991）首先介绍了一种地理故障模型，其中每个故障由一个二维区域表示。在该模型中，我们考虑的情况下，地理网络，如道路网络可能会受到外部造成的灾害，这种灾害可能会破坏网络的几个环节同时，而不是每个环节独立。最近，Neumayer-Efrat-Modiano（2012）研究了圆盘失效模型下的最大流问题和最小割问题，其中每个失效的形状被限制为圆盘。在这个模型下，Kobayashi-Otsuki（2014）给出了多项式时间算法来找到这两个问题的最优解。在本文中，我们改进的算法，并评估其性能的计算实验。虽然我们的改进仅在最大流值等于最小割值时才起作用，但这个条件几乎在所有实际情况下都成立。由于这些改进，我们可以在一个现实的时间内找到最大流问题和最小割问题在大型网络的圆盘故障模型下的最优解。作为一个现实的例子，我们分析了在纽约的道路网络由264,346个节点的可靠性。
In the evaluation of network reliability, the objectives are to model reliability of networks appropriately and to compute it in a realistic time. We can consider various models of reliability of networks, and Bienstock (1991) first introduced a geographical failure model where each failure is represented by a 2-dimensional region. In this model, we consider the situation that geographical networks such as road networks may be damaged by externally caused disasters, and such disasters may destroy several links of the networks simultaneously, rather than each link independently. Recently, Neumayer–Efrat–Modiano (2012) investigated the max-flow problem and the min-cut problem under the Circular Disk Failure Model, in which the shape of each failure is restricted to be a disk. Under this model, Kobayashi–Otsuki (2014) gave polynomial time algorithms to find optimal solutions of these two problems. In this paper, we improve the algorithms and evaluate their performance by computational experiments. Although our improvements work only when the max-flow value is equal to the min-cut value, this condition holds in almost all practical cases. Owing to the improvements, we can find in a realistic time optimal solutions of the max-flow problem and the min-cut problem in large networks under the Circular Disk Failure Model. As a realistic instance, we analyze reliability of a road network in NewYork consisting of 264,346 nodes.