動的フローネットワークにおける避難施設配置問題

• Item type: SIG Technical Reports(1)
• 公開日: 2025-01-07
• タイトル: 動的フローネットワークにおける避難施設配置問題
• タイトル / 言語: en
• タイトル: Sink Location Problems in Dynamic Flow Networks
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: University of Hyogo
• 著者所属: University of Hyogo
• 著者所属: University of Hyogo
• 著者所属: University of Hyogo
• 著者所属(英): en
• 著者所属(英): University of Hyogo
• 著者所属(英): en
• 著者所属(英): University of Hyogo
• 著者所属(英): en
• 著者所属(英): University of Hyogo
• 著者所属(英): en
• 著者所属(英): University of Hyogo
• 著者名: 西井, 彩乃; 照山, 順一; 戸國, 友貴; 東川, 雄哉
• 著者名(英): Ayano, Nishii; Junichi, Teruyama; Yuki, Tokuni; Yuya, Higashikawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 動的フローネットワークは，各頂点に避難者数を示す供給量，各辺に容量と移動時間が与えられた有向グラフで定義される．動的フローネットワークの頂点上あるいは辺上に避難施設を配置すると，すべての避難者が避難施設に到着可能な最小時間，すなわち避難完了時間が定義できる．避難施設配置問題とは，避難完了時間を最小化する施設の配置を求める問題である．この問題については，これまでパス [1]，[2]，[3]，サイクル [1]，木[4]，[5]，[6] など限定されたネットワークに対する多項式時間アルゴリズムが知られている．また，ごく最近，東川ら [7] がグリッドネットワークにおける施設配置問題に対する多項式時間アルゴリズムを提案した．本稿では，辺の容量が一定である一般のネットワークにおいて，単一施設配置問題が多項式時間で解けることを示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A dynamic flow network consists of a directed graph, where nodes called sources represent locations of evacuees, and nodes called sinks represent locations of evacuation facilities. Each source and each sink are given supply representing the number of evacuees and demand representing the maximum number of acceptable evacuees, respectively. Each edge is given capacity and transit time. Here, the capacity of an edge bounds the rate at which evacuees can enter the edge per unit time, and the transit time represents the time which evacuees take to travel across the edge. The evacuation completion time is the minimum time at which each evacuees can arrive at one of the evacuation facilities. Given a dynamic flow network without sinks, once sinks are located on some nodes or edges, the evacuation completion time for this sink location is determined. We then consider the problem of locating sinks to minimize the evacuation completion time, called the sink location problem. The problems have been given polynomial-time algorithms only for limited networks such as paths [1], [2], [3], cycles [1], and trees [4], [5], [6]. Very recently, Higashikawa et al. [7] have studied the case with grid networks and proposed polynomial time algorithms. In this paper, we prove that the 1-sink location problem can be solved in polynomial-time when the input network has uniform edge capacity.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2025-AL-201, 号 8, p. 1-8, 発行日 2025-01-07
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会