Establishing theoretical foundation of optimal evacuation planning based on dynamic networkflows

建立基于动态网络流的最优疏散规划的理论基础

• 批准号: 19H04068
• 负责人: 加藤 直樹
• 金额: $ 11.07万
• 依托单位: University of Hyogo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-01 至 2023-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19H04068/
• 关键词: 最速避難流問題; 最適避難施設配置問題; 動的フローネットワーク; 汎用的数理計画モデル; 不確定的状況下での最適化

本年度は以下の結果を得た．（１）「同じ場所にいる避難者は同じ施設に避難する」という仮定を緩和した一般的なフローモデルについて，パスネットワークおよびサイクルネットワーク上の避難完了時間最小化施設配置問題に対する初の多項式時間アルゴリズムを開発した．本結果は査読付国際会議ATMOS　2021にて発表された．（２）パスネットワーク上の総避難時間最小化複数施設配置問題に対する，時間計算量がネットワークサイズに対してほぼ線形となるアルゴリズムを開発した結果について，国際論文誌Theoretical Computer Scienceに採録された．（３）試験からの一斉退館問題に対して，動的ネットワーク木，（改良）ダイクストラ法，避難安全検証法それぞれによる出口の領域分割を求め，歩行者シミュレーションソフトを用いて各分割による退館時間を比較した．その結果，動的ネットワーク木による退館完了時間が最も短くなった．（４）南海トラフ地震に起因する津波被害により，大阪市で被害を受けることが予想される約30万人の避難者のグループが2次避難場所へ徒歩で避難を開始する時刻を，スケジューリング問題で定式化・最適化した．結果として，大阪市の図上訓練で設定された避難計画よりも，スムーズに短時間で避難できることをシミュレーションにより確認した．（５）動的フローネットワークにおける複数施設配置問題に対する研究代表者らの近年の結果について概説記事を執筆し，Springerから出版された書籍「Sublinear Computation Paradigm - Algorithmic Revolution in the Big Data Era」の第5章に採録された．

The following results were obtained for the year. (1)"The same place in the middle of the evacuation of the same set of facilities for evacuation" and "fixed to ease the general situation of the evacuation of the general situation," the first time to minimize the evacuation of the installation configuration problem for the initial polynomial time to open. The results are presented at the ATMOS 2021 conference. (2) Minimizing the total refuge time on the Computer is a problem of multiple configuration. The calculation of the time is based on the calculation of the number of times. The calculation of the time is based on the calculation of the number of times. (3) To solve the problem of evacuation of the museum, we should compare the evacuation time of each partition with the time of evacuation of the museum. The shortest time to retire from the museum is the shortest possible time. (4) The South China Sea earthquake caused the destruction of Tsukuba and Osaka City. About 300,000 people were killed. The number of people who took refuge in the earthquake increased twice. The time when the evacuation began was determined and optimized. As a result, Osaka City has set up an evacuation plan for a short period of time. (5) The author of Springer's book "Sublinear Computation Paradigm -Algorithm Revolution in the Big Data Era" was collected from Chapter 5 of the book "Sublinear Computation Paradigm -Algorithm Revolution in the Big Data Era."

项目成果

Locating evacuation centers optimally in path and cycle networks

在道路和自行车网络中最佳定位疏散中心

• 发表时间: 2021
• 期刊: Proceedings of the 21th International Symposium on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS2021)
• 作者: Robert Benkoczi;Binay Bhattacharya;Yuya Higashikawa;Tsunehiko Kameda;Naoki Katoh;Junichi Teruyama
• 通讯作者: Junichi Teruyama

シミュレーションと最適化による大阪市を対象とした避難計画支援技術

利用模拟和优化的大阪市避难规划支持技术

• 发表时间: 2019
• 作者: Yuya Higashikawa;Naoki Katoh;Junichi Teruyama;Koji Watase;瀧澤重志;戸國友貴，加藤直樹，照山順一，東川雄哉，藤江哲也;戸國友貴，加藤直樹，照山順一，東川雄哉，藤江哲也;瀧澤重志;瀧澤重志
• 通讯作者: 瀧澤重志

Almost linear time algorithms for minsum k-sink problems on dynamic flow path networks

动态流路网络上最小和 k 汇问题的几乎线性时间算法

• DOI: 10.1016/j.tcs.2021.05.003
• 发表时间: 2021
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Yuya Higashikawa;Naoki Katoh;Junichi Teruyama;Koji Watase
• 通讯作者: Koji Watase

複層階を有する教育施設からの利用者の一斉退館シミュレーション

模拟所有用户离开多层教育设施的情况

• 发表时间: 2020
• 作者: Tetsuya Fujie;Yuya Higashikawa;Naoki Katoh;Junichi Teruyama;Yuki Tokuni;瀧澤重志;瀧澤重志;馬塲崇仁，瀧澤重志
• 通讯作者: 馬塲崇仁，瀧澤重志

Minsum k-Sink Problem on Path Networks

• DOI: 10.1016/j.tcs.2019.05.047
• 发表时间: 2018-10
• 期刊: Theor. Comput. Sci.
• 作者: R. Benkoczi;B. Bhattacharya;Yuya Higashikawa;T. Kameda;N. Katoh