TY - JOUR
T1 - The mixed evacuation problem
AU - Hanawa, Yosuke
AU - Higashikawa, Yuya
AU - Kamiyama, Naoyuki
AU - Katoh, Naoki
AU - Takizawa, Atsushi
N1 - Funding Information:
Acknowledgements This research was the result of the joint research with CSIS, the University of Tokyo (No. 573) and used the following data: Digital Road Map Database extended version 2013 provided by Sumitomo Electric Industries, Ltd and Zmap TOWN II 2008/09 Shapefile Wakayama prefecture provided by Zenrin Co. Ltd. Yuya Higashikawa, Naoki Katoh, and Atsushi Takizawa were supported by JSPS Grant-in-Aid for Scientific Research(A) (25240004) and by JST CREST Grant Number JPMJCR1402, Japan. Naoyuki Kamiyama was supported by JST PRESTO Grant Numbers JPMJPR14E1, Japan.
Funding Information:
This research was the result of the joint research with CSIS, the University of Tokyo (No. 573) and used the following data: Digital Road Map Database extended version 2013 provided by Sumitomo Electric Industries, Ltd and Zmap TOWN II 2008/09 Shapefile Wakayama prefecture provided by Zenrin Co. Ltd. Yuya Higashikawa, Naoki Katoh, and Atsushi Takizawa were supported by JSPS Grant-in-Aid for Scientific Research(A) (25240004) and by JST CREST Grant Number JPMJCR1402, Japan. Naoyuki Kamiyama was supported by JST PRESTO Grant Numbers JPMJPR14E1, Japan. An earlier version of this paper has appeared in Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), volume 10043 of Lecture Notes in Computer Science, pages?18?32, 2016.
Publisher Copyright:
© 2017, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2018/11/1
Y1 - 2018/11/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85038108196&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85038108196&partnerID=8YFLogxK
U2 - 10.1007/s10878-017-0237-7
DO - 10.1007/s10878-017-0237-7
M3 - Article
AN - SCOPUS:85038108196
SN - 1382-6905
VL - 36
SP - 1299
EP - 1314
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
IS - 4
ER -