An efficient algorithm for the evacuation problem in a certain class of networks with uniform path-lengths
An efficient algorithm for the evacuation problem in a certain class of networks with uniform path-lengths
复制标题
DOI：
10.1016/j.dam.2009.04.007
复制
发表时间：
2009-10
期刊：
影响因子：
--
通讯作者：
Naoyuki Kamiyama;N. Katoh;A. Takizawa
中科院分区：
文献类型：
--
作者：
Naoyuki Kamiyama;N. Katoh;A. Takizawa
本文研究了一类由有向图组成的网络中的疏散问题，该网络的弧上具有通行时间和通行能力。该问题可用Hoppe和Tardos [B. Hoppe，美国最快转运问题，数学。Res. 25（1）（2000）36 - 62]中。然而，它们的运行时间是高阶多项式，因此通常不实用。因此，有必要设计一个更快的算法，这个问题的一个听话的和实际有用的子类。本文考虑一个具有汇点s的网络，使得（i）对于每个顶点v ∈ s，从v到s的任何路径上的弧的渡时之和取相同的值，（ii）对于每个顶点v ∈ s，最小v-s割由从v可达的与s相关联的弧决定。Kamiyama，N. Katoh，A.张文龙，等容弧动态网络中人员疏散问题的一种有效算法，北京交通大学学报，2001。E89-D（8）（2006）2372 - 2379]。我们提出了一个有效的算法，这个网络问题。
In this paper, we consider the evacuation problem in a network which consists of a directed graph with capacities and transit times on its arcs. This problem can be solved by the algorithm of Hoppe and Tardos [B. Hoppe, É. Tardos, The quickest transshipment problem, Math. Oper. Res. 25(1) (2000) 36–62] in polynomial time. However their running time is high-order polynomial, and hence is not practical in general. Thus, it is necessary to devise a faster algorithm for a tractable and practically useful subclass of this problem. In this paper, we consider a network with a sink s such that (i) for each vertex v≠s the sum of the transit times of arcs on any path from v to s takes the same value, and (ii) for each vertex v≠s the minimum v-s cut is determined by the arcs incident to s whose tails are reachable from v. This class of networks is a generalization of grid networks studied in the paper [N. Kamiyama, N. Katoh, A. Takizawa, An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity, IEICE Trans. Infrom. Syst. E89-D (8) (2006) 2372–2379]. We propose an efficient algorithm for this network problem.