The Mixed Evacuation Problem
The Mixed Evacuation Problem
复制标题
混合疏散问题
DOI：
10.1007/978-3-319-48749-6_2
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
A. Takizawa
中科院分区：
文献类型：
--
作者：
Y. Hanawa;Y. Higashikawa;N. Kamiyama;N. Katoh;A. Takizawa
Ford和Fulkerson引入的动态网络是一个有向图，其弧线上有容量和运输时间。快速转运问题是动态网络中最基本的问题之一。在这个问题中，我们已知源和汇。那么这个问题的目标是找到一个最小的时间限制，这样我们就可以将适量的流从源发送到汇。在本文中，我们引入了该问题的一个变体，称为混合疏散问题。这个问题模拟了一种紧急情况，在这种情况下人们可以步行或开车疏散。我们的目标是组织这样的混合疏散，以实现有效的疏散。本文从理论和实践两个角度对这一问题进行了研究。在第一部分中，我们证明了该问题在源汇数量不大的情况下的多项式时间可解性，并证明了其变量在整数约束下的多项式时间可解性和计算难度。在第二部分中，我们将模型应用于日本和歌山县南边镇的案例研究。
A dynamic network introduced by Ford and Fulkerson is a directed graph with capacities and transit times on its arcs. The quickest transshipment problem is one of the most fundamental problems in dynamic networks. In this problem, we are given sources and sinks. Then the goal of this problem is to find a minimum time limit such that we can send the right amount of flow from sources to sinks. In this paper, we introduce a variant of this problem called the mixed evacuation problem. This problem models an emergent situation in which people can evacuate on foot or by car. The goal is to organize such a mixed evacuation so that an efficient evacuation can be achieved. In this paper, we study this problem from the theoretical and practical viewpoints. In the first part, we prove the polynomial-time solvability of this problem in the case where the number of sources and sinks is not large, and also prove the polynomial-time solvability and computational hardness of its variants with integer constraints. In the second part, we apply our model to the case study of Minabe town in Wakayama prefecture, Japan.