被災者の減少を考慮した避難所割当問題
The Shelter Allocation Problem with consideration of the Decrease in Evacuees∗1

清水 仁 ∗1∗2

諏訪 博彦 ∗2

安本 慶一 ∗2

Hitoshi Shimizu

Hirohiko SuwaKeiichi Yasumoto

NTT コミュニケーション科学基礎研究所
NTT Communication Science Laboratories∗2

奈良先端科学技術大学院大学

Nara Institute of Science and Technology

In the event of a disaster, evacuation shelters are necessary. Shelters have been planned to minimize the cost ofevacuation. However, in a major disaster, the cost of operating shelters becomes non-negligible. When the numberof evacuees declines, it is possible to reduce the cost of operating shelters by having people relocate from one shelter
to another. However, relocation between shelters is a heavy burden on the evacuees. If we had information on wheneach evacuee would return home, we could reduce the number of relocations by gathering those who stay for a longtime in one place. In this study, we formulate a shelter allocation problem that takes into account the decrease in
the number of evacuees. The optimal solution of this formulation allocates evacuees to shelters to minimize thesum of the cost of moving evacuees and the cost of operating shelters.

1.

はじめに災害時には避難所が運営される．東日本大震災の際に多数の帰宅困難者が発生した事例 [朝日 11] があるため，各都市で避難所が整備されている [秋田 15]．被災者の負担を考慮すると，なるべく被災者の位置の近くに避難所が開設されることが望ましく，たとえば東京都では，避難距離 3km 以内を目標として避難所を整備している [東京 13]．
しかし避難所の運営にはコストがかかる．たとえば阪神淡路大震災では，避難所の空間コストとして 100 億円程度かかったという試算がある [大塚 16]．また，計画した避難所の容量に不足があると，追加で設営する必要が生じる場合もある [本塚 19]．
さらに，避難所に被災者が滞在する期間が長期化すると，運営のコストも増大する．一方で，避難所の数と比較して，被災者の人数が少ない場合もある [NHK 21]．そこで，可能であれば効率的に被災者を避難所に割り当てて，運営コストを小さくすることも重要である．
本研究の課題の要点を説明すると，以下のようになる．図 1のように，避難所 A がすでに開設されている状況において，被災者 3 の収容先として避難所 A,B どちらを選択するべきだろうか？避難所 A を選択すると避難所 B の運営コストを節約できるが，被災者 3 の避難コストが避難所 B を選択する場合よりも増加してしまう．一方，避難所 B を選択すると被災者 3の避難コストを小さくできるが，避難所 B の運営コストが増加してしまう．このように，避難所の運営コストと，被災者の避難コストの両方を考慮して，新規に避難所 B を開設するかどうか，判断する必要がある．また，図 2 のように，避難所B の被災者が帰宅するなどで減少した状況において，残った被災者 3 に避難所 A へ移転してもらうべきだろうか？移転してもらうと避難所 B の運営コストを節約できるが，被災者 3 の移転コストがかかってしまう．一方，避難所 B に被災者 3 が滞在し続けると移転コストは小さくできるが，避難所 B の運営コストを削減することができない．
以上のように，被災者の移動コストを削減したいという要望と，避難所の運営コストを削減したいという要望は，相反するものである．災害発生時において，避難所開設のコストだけ

図 1: 避難所開設の判断

図 2: 避難所閉設の判断でなく避難所閉設のコストも考慮しなければ，最適解を求めることができない．本研究では，被災者の移動に対するコストと避難所の運営に対するコストを入力として，コストの和を最小にする割当を求める問題を定式化する．

2.

問題設定

N 人の被災者全員が避難所に避難する状況を想定する．被災者 n は，帰宅時刻 τn までの各時刻において，いずれかの避難所に滞在する必要がある．ただし時刻は，災害発生時を t = 0として離散化した整数 t で表現し，T = maxn τn とする．以降では単位時間を 1 ステップとよぶ．被災者は災害発生時にM 箇所の地点のいずれかにいて，被災者 n が災害発生時にいる地点を m̃(n) とする．地点 m に避難所を開設した場合，避難所 m には最大で Cm 人の被災者を収容できる．ただし，避難所候補地ではない地点は Cm = 0 とする．また，被災者全∑員を避難所に収容可能となるように， m Cm ≥ N とする．
地点 m から m′ の移動には移動コスト dtmm′ がかかり，任意連絡先: 清水仁，hitoshi.shimizu.kg@hco.ntt.co.jp

1

の地点間の移動は 1 ステップ内に完了するものとする．また，避難所 m を開設した場合には，運営のために 1 ステップあたり fm のコストがかかる．ただし，災害発生直後の避難コスト
dt=1,mm′ は，災害発生から時間が経過したときの移転コスト
dtmm′ , ∀t > 1 とは異なることが想定されるため，移動コスト
dtmm′ は時刻 t に依存するものとする．以降では，t = 1 での移動コストを避難コストとよび，t > 1 での移動コストを移転コストとよぶ．
そして，コストの合計を最小にする問題を，以下の 0-1 整数計画問題として定式化する．

Minimize(∑ ∑∑tmdtmm′m′∑

ztmm′ n +n∑表 1: 記号の定義)∑m

xtmn ≤ Cm ytm , ∀t ≥ 1(2)xtmn = 1, ∀t ≤ τn(3)xtmn = 0, ∀t > τn(4)定義

NMm̃(n)
CmT
τnfm
dtmm′

被災者数: n ∈ {1, · · · , N }
地点数: m ∈ {1, · · · , M }t = 0 の被災者 m の位置
避難所 m の定員考慮する時刻の最大値: t ∈ {0, · · · , T }被災者 n が帰宅する時刻
避難所 m の 1 ステップ分の運営コスト
時刻 t に被災者が避難所 m から避難所 m′ まで移動するコスト
時刻 t に被災者 n が避難所 m に滞在することの指示変数
時刻 t に避難所 m を運営することの指示変数
時刻 t に被災者 n が避難所 m から m′ に移動することの指示変数

xtmn

fm ytmytm
ztmm′ n(1)
Subject to記号n∑

よらず 5 であり，避難所 A の運営コストと同一である．すな
わち，1 ステップ分だけ避難所を閉設するために被災者が移動する行動は，最適解にならない．
移転コストを無視したときの最適解の一例を，表 3a に示す．
t > 1 においては避難所の運営コストを最小化するため，定員ギリギリだけ避難所を開設して，被災者に移転を強いる結果となった．被災者 3 が避難所 B から A に移動した後に避難所 Bへ戻る，という移転が発生しており，被災者への負担が大きい．
一方，移転コストを考慮した問題の最適解（表 3b）では，運営コストが表 3a よりも 2 だけ増加している．しかし，t > 1で移転が発生せず，被災者の負担が小さな計画となっている．
たとえば t = 3 においては，被災者 3 が避難所 B に移転すれば運営コストを節約できるが，移転コストのほうが大きくなるため，避難所 A での滞在を継続している．

m∑m(xtmn − x(t−1)mn ) − (xtm′ n − x(t−1)m′ n )≤ 2ztmm′ n , ∀t ≥ 1(5)ztmm′ n ≤ x(t−1)mn , ∀t : 1 ≤ t ≤ τn

(6)ztmm′ n ≤ xtm′ n , ∀t : 1 ≤ t ≤ τn{
1, m = m̃(n)xt=0,mn =0, m ̸= m̃(n)(7)

xtmn ∈ {0, 1}(9)ytm ∈ {0, 1}(10)ztmm′ n ∈ {0, 1}

(11)

(8)

4.

2. 章の問題設定は，混合整数計画問題のソルバーを用いて最適解を求めることができる．しかし，N, M, T が大きくなると，計算量が大きく．そこで，人工データを用いて，計算時間を評価した．人工データは，以下のように作成した．避難所の容量 Cm は 100 に固定した．避難所 m の運営コスト fmは m とした．避難所の位置を二次元領域 ([0,1],[0,1]) にランダムに設定して，地点間のユークリッド距離を行列 dtmm′ として作成した．被災者の帰宅時刻 τn は T 以下の整数からランダムに設定した．被災者の初期位置 x1mn は M 箇所の避難所からランダムに設定した．最適解を求めるための実装にはGoogle OR-Tools[Perron 19] を用いた．Intel(R) Core(TM)i7
1065G7 1.50GHz の CPU，16GB のメモリを搭載した計算機で実行したときの計算時間を表 4 に示す．
T が大きいと実行できない場合が多い．これに対して，単位時間を大きく（１日単位よりは１週間単位など）して T を小さくすると，計算量を抑えられるだろう．しかし，たとえば京都市には 100 以上の避難所数があり [京都]，帰宅困難者は 39万人と想定されている [京都 20]．このような現実の問題を解くためには，より効率的な計算方法を開発する必要がある．

式 (1) は，被災者の移動コストと避難所の運営コストの和を最小化する，という目的関数である．式 (2) は，閉鎖中の避難所には被災者が滞在できず，開設中の避難所の被災者数が定員を超えない条件である．ただし災害発生時（t = 0）においては，被災者はまだ避難所に収容されていないためこの制約は適用されない．式 (3)(4) は被災者が帰宅するまではいずれかの避難所に滞在する条件である．式 (5) は移転する被災者を集計するための条件である．式 (6)(7) は移転の前の時刻に被災者が移転元にいて，移転の後の時刻に被災者が移転先にいるための条件である．式 (8) は，被災者 n が災害発生時に所与の場所
m̃(n) にいる条件である．本稿中の記号の定義を表 1 に示す．

3.

実験

例題

2. 章の問題設定は，t = 1 で施設配置問題 [田中 13] を解いた後，t > 1 でビンパッキング問題 [Baldi 12] を繰り返し解くことで，解を求めることは可能である．しかし，その場合は，移転コストが考慮できないため，最適解が求められるとは限らない．本章では，移転コストを考慮することで，解にどのような差分が生じるかを，表 2 の例題を用いて示す．
表 2 では，3 人の被災者が 2 箇所の避難所に避難する．これらの避難所は定員とコストが異なり，避難所 A のほうが定員もコストも大きい．定員の合計は 3 人のため t = 1 で避難所は満員になる．帰宅時刻は被災者 1,2,3 の順番で遅くなり，t = 4 で全員が帰宅する．避難所 AB 間の移動コストは時刻に

5.

関連研究

被災者を収容できるように避難所を設置する問題は，施設配置問題として定式化されている [田中 13]．また，避難所の設置コストと被災者の移動コストを最小化する問題は，固定費付きの2表 2: 3 人の被災者が 2 箇所の避難所に避難する例題．
(a) 避難所の設定

避難所 A
避難所 B

(b) 被災者の設定．

fm

Cm

5
3

2
1

被災者 1
被災者 2
被災者 3

(c) 避難所間の移動コスト dtmm′

初期位置

τn

避難所 B
避難所 A
避難所 B

2
34

避難所 A
避難所 B

避難所 A

避難所 B

0550

表 3: 例題に対する解の例．たとえば，「A → B」は被災者が避難所 A から避難所 B に移動することを表し，また，「open」は ytm = 1，「close」は ytm = 0 を表す．移動コストと運営コストの和をコスト小計に，各時刻のコスト小計の和を表上部のコスト合計に示す．
(a) 移転コストを無視した場合の最適解（コスト合計＝ 21）

状態

t=1
コスト

状態

t=2
コスト

状態

t=3
コスト

被災者 1
被災者 2
被災者 3
移動コスト

B→A
A→A
B→B
-

500
5

帰宅
A→A
B→A-

-∗-

帰宅
帰宅
A→B
-

-∗
-

避難所 A
避難所 B
運営コスト

open
open
-

538openclose-

505close
open
-

03
3

コスト小計

-

13-

5-

3∗ 移転コストを考慮した場合は 5．この場合コスト合計は 31 で，表 3b よりも大きくなる．

(b) 移転コストを考慮した場合の最適解（コスト合計＝ 23）

状態

t=1
コスト

状態t=2コスト

状態

t=3コスト

被災者 1
被災者 2
被災者 3
移動コスト

B→B
A→A
B→A
-00
55

帰宅
A→A
A→A
-

000

帰宅
帰宅A→A-00

避難所 A
避難所 B
運営コスト

open
open
-

538openclose-

505openclose-

50
5コスト小計

-

13-

5-

5

輸送問題 (UFLP: the Uncapacitated FixedCharge LocationProblem) として定式化されており [Robers 76, Daskin 08]，需要が変化する動的施設配置問題（DFLP: dynamic facility
location problem）もすでに定式化されている [Van Roy 82,Nickel 19]．また，施設配置において確率的な要素を考慮した問題設定が検討されている [Correia 19]．さらに，避難所の配置計画への適用に関しても，長い研究の歴史がある [太田 79]．
また，避難所割当問題に対しては，ZDD を用いて網羅的に解候補を列挙する手法が開発されている [瀧澤 14]．しかし，避難所を閉鎖するために被災者が移転するコストを考慮できるモデルは，我々の知る限りこれまでに定式化されていない．
本研究の定式化において移動コストを無視すると，ビンパッキング問題になる．ビンパッキング問題とは，ビンのコストが最小になるように，アイテムを収容するビンの集合を求める問題である．Baldi らは，物流システムの最適化問題として，ビンに依存したアイテム利益をもつ一般化ビンパッキング問題(GBPPI: the Generalized Bin Packing Problem with bindependent Item proﬁts) を定式化した [Baldi 12, Baldi 19]．
避難所をビン，被災者をアイテムに対応させると，避難所割当問題もビンパッキング問題とみなすことができる．しかし，全アイテムのサイズが同一の場合は，本稿の定式化のほうがシンプルに扱うことができる．

6.

まとめと今後の課題本研究では，被災者の逐次的な帰宅に伴う避難所の閉鎖を考慮した避難所割当問題について，定式化を行った．今回は被災者が減少する場合のみを検討したが，増加する場合も自然な拡張として定式化可能である．この問題設定は，混合整数計画問題のソルバーを用いて解を求めることができるが，効率的な解法の検討は今後の課題とする．
本研究では被災者の帰宅時刻を所与とした．実際には，災害発生時に交通機関が復旧する時刻を予測することは困難だろう．しかし被災者の住所が近いほど帰宅が早い，などの大まかな予測をすることで，本稿のモデルは適用可能と考える．一方で，避難所の規模が大きいほど，被災者の帰宅するまでの滞在期間が長い，という報告がある [谷岡 07]．仮に本研究の手法で運営する避難所の数を減らしても，避難所の規模が増加して運営する期間が長くなると運営コストは増大するおそれがあ3表 4: 計算時間（単位：秒）．ただし，N/A は計算機で実行できなかったことを示す．

NM25T102050100102050100
200
500
1000
2000

241020202020
200.014
0.022
0.201
1.84
3.342
10.35220.19842.416

0.021
0.059
0.765
6.688
13.15832.95874.863258.998

0.125
0.102
2.011
14.77532.44798.185
N/A
N/A

0.132
0.322
4.101
34.29568.238
N/A
N/A
N/A

0.239
0.619
10.206110.399
N/A
N/A
N/A
N/A

0.287
2.343
31.605
N/A
N/A
N/A
N/A
N/A

る．適切な避難所の規模についても，今後検討が必要だろう．

[京都 20] 京都市：大規模災害時における観光客等帰宅困難者対策 (2020), https://www.city.kyoto.lg.jp/gyozai/
page/0000076886.html (2020 年 8 月 4 日掲載，2021 年
1 月 13 日アクセス)

参考文献[Baldi 12] Baldi, M. M., Crainic, T. G., Perboli, G., andTadei, R.: The generalized bin packing problem, Transportation Research Part E: Logistics and Transportation
Review, Vol. 48, No. 6, pp. 1205–1220 (2012)[秋田 15] 秋 田 県：「 観 光 客 等 の 防 災 対 策 」ガ イ ド ラ イ ン(2015), https://www.bousai-akita.jp/uploads/user/system/File/guidelines/kankoukyaku.pdf (2015 年 3
月掲載，2021 年 1 月 13 日アクセス)[Baldi 19] Baldi, M. M., Manerba, D., Perboli, G., andTadei, R.: A generalized bin packing problem for parcel
delivery in last-mile logistics, European Journal of Operational Research, Vol. 274, No. 3, pp. 990–999 (2019)[太田 79] 太田裕, 鏡味洋史：地震時避難場所の配置計画の検討 (1) 問題の定式化の試み, 地震第 2 輯, Vol. 32, No. 1,
pp. 25–39 (1979)[Correia 19] Correia, I. and Gama, Saldanha-da F.: Facilitylocation under uncertainty, in Location science, pp. 185–213, Springer (2019)[大塚 16] 大塚和徳, 越山健治：災害時に利用される空間コスト算定に関する研究, 日本都市計画学会関西支部研究発表会
講演概要集, Vol. 14, pp. 121–124 (2016)[Daskin 08] Daskin, M. S.: What you should know aboutlocation modeling, Naval Research Logistics (NRL),
Vol. 55, No. 4, pp. 283–294 (2008)[瀧澤 14] 瀧澤重志：避難計画問題への離散アルゴリズムの適用 (特集 データを読み解く技術: ビッグデータ, e-サイエンス, 潜在的ダイナミクス), 電子情報通信学会誌, Vol. 97,
No. 5, pp. 393–398 (2014)[NHK 21] NHK, : 地震 福島県内 39 人が避難 (2021),
https://www3.nhk.or.jp/news/html/20210214/
k10012865501000.html (2021 年 2 月 14 日掲載，2021 年
2 月 16 日アクセス)[谷岡 07] 谷岡亮子, 田畑良宏, 林静子, 秦朝子, 辻井靖子, 小林隆幸, 中西章夫：大きい避難所ほど被災者の減少は少ない–
阪神淡路大震災の教訓より, 滋賀医科大学看護学ジャーナル,Vol. 5, No. 1, pp. 25–31 (2007)[Nickel 19] Nickel, S. and Gama, Saldanha-da F.: Multiperiod facility location, in Location science, pp. 303–326,
Springer (2019)[朝日 11] 朝日新聞：大震災、都内の帰宅困難者は９万人以上
首都圏白書 (2011), http://www.asahi.com/special/10005/TKY201106140148.html (2011 年 6 月 14 日掲載，2021 年 1 月 13 日アクセス)[Perron 19] Perron, L. and Furnon, V.: Google OR-Tools,version 7.2 (2019), https://developers.google.com/
optimization/[田中 13] 田中健一：数理最適化入門 (4): 施設配置の数理モデ
ル (チュートリアル), 応用数理, Vol. 23, No. 4, pp. 178–183(2013)[Robers 76] Robers, P. and Cooper, L.: A study of the ﬁxed
charge transportation problem, Computers & Mathematics with Applications, Vol. 2, No. 2, pp. 125–135 (1976)[東京 13] 東京都：東京都震災対策事業計画（平成 23 年度〜27 年度） (2013), https://www.bousai.metro.tokyo.lg.
jp/taisaku/torikumi/1000061/1000364.html ((2013 年9 月掲載，2021 年 2 月 26 日アクセス))[Van Roy 82] Van Roy, T. J. and Erlenkotter, D.: A dualbased procedure for dynamic facility location, Management Science, Vol. 28, No. 10, pp. 1091–1105 (1982)[本塚 19] 本塚智貴：災害対応における空間資源マネジメントに関する研究, 地域安全学会論文集, Vol. 35, pp. 317–326(2019)[京都] 京都市：指定避難所一覧：https://www.city.kyoto.
lg.jp/gyozai/cmsfiles/contents/0000132/132312/
hinansyoR20801.pdf(2017 年 4 月 4 日公開，2021 年 1 月
7 日アクセス)4