The mixed evacuation problem

• Hanawa, Yosuke

  京都大学

• 東川, 雄哉

  中央大学 科学技術振興機構戦略的創造研究推進事業

• 神山, 直之

  九州大学マス・フォア・インダストリ研究所 科学技術振興機構さきがけ

• 加藤, 直樹

  関西学院大学 科学技術振興機構戦略的創造研究推進事業

• 瀧澤, 重志

  大阪市立大学 科学技術振興機構戦略的創造研究推進事業

抄録

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 ow 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.

収録刊行物

• Journal of Combinatorial Optimization

  Journal of Combinatorial Optimization 36 (4), 1299-1314, 2017-12-14

  Springer

キーワード

• dynamic network flow
• evacuation problem

詳細情報

• CRID: 1050580007680905472
• NII論文ID: 120006998855
• NII書誌ID: AA11120156
• ISSN: 15732886
• ISSN: 13826905
• HANDLE: 2324/4363021
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles