2026-03-10T13:51:56Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00241896 2025-01-19T07:30:17Z 1164:2592:11887:11888

動的フローネットワークにおける避難施設配置問題 Sink Location Problems in Dynamic Flow Networks 西井, 彩乃 照山, 順一 戸國, 友貴 東川, 雄哉 Ayano, Nishii Junichi, Teruyama Yuki, Tokuni Yuya, Higashikawa 動的フローネットワークは，各頂点に避難者数を示す供給量，各辺に容量と移動時間が与えられた有向グラフで定義される．動的フローネットワークの頂点上あるいは辺上に避難施設を配置すると，すべての避難者が避難施設に到着可能な最小時間，すなわち避難完了時間が定義できる．避難施設配置問題とは，避難完了時間を最小化する施設の配置を求める問題である．この問題については，これまでパス [1]，[2]，[3]，サイクル [1]，木[4]，[5]，[6] など限定されたネットワークに対する多項式時間アルゴリズムが知られている．また，ごく最近，東川ら [7] がグリッドネットワークにおける施設配置問題に対する多項式時間アルゴリズムを提案した．本稿では，辺の容量が一定である一般のネットワークにおいて，単一施設配置問題が多項式時間で解けることを示した． 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. 情報処理学会 2025-01-07 jpn technical report https://ipsj.ixsq.nii.ac.jp/records/241896 2188-8566 AN1009593X 研究報告アルゴリズム（AL） 2025-AL-201 8 1 8 https://ipsj.ixsq.nii.ac.jp/record/241896/files/IPSJ-AL25201008.pdf application/pdf 935.8 kB 2027-01-07