避難所間における物資の共有のための運搬経路決定手法
理学専攻・情報科学コース 1840661 佐藤 沙央

1

はじめに構築していく．

近年，大規模災害により通信インフラが被害を受けたことでインターネットへのアクセスができなくなることが頻発している．緊急時には情報の交換・共有が必要不可欠にも関わらず通信を行う上で中断や切断が多発したり，大きな伝送遅延が生じたりする劣悪な環境になる可能性がある．現在提供されている災害に備えたサービスの多くは，インターネットへのアクセスが前提で考えられているため，劣悪な環境に陥ると使えなくなってしまうため，災害対策として提供されているにも関わらず有用な利活用ができない．
そこで本研究では，大規模災害によって地域的にインターネットが機能しないような劣悪な環境においても，部分的に稼働しているエッジサーバと Delay/Disruption Tolerant Network (DTN) 技術 [1] を利用した災害時通信システムを利用し，被災者のニーズを集約する仕組みをアプリケーションで構築し，さらに各避難所にある物資の過不足情報を集約し，避難所間で過不足を解消するための物資の運搬経路の決定手法を提案する．ここでは後半の物資の運搬経路の決定手法について述べる．

23システムの形態

図 1: システムの形態
各指定避難所には平時からエッジサーバが設けられおり，インターネットが生きている状況では，各エッジサーバがクラウドに接続して稼働していると想定する．
発災後インターネットとの接続が途切れ，通信が困難になった場合は，各エッジサーバは Wi-Fi で通信して互いにリンクを生成しデータを共有してアップデートする．さらに一部でリンクを生成できなかった，あるいは遮断されてしまった場合には DTN 技術を用いて自動で別のリンクを利用して，データをホップさせていくことで，遠回りをしてもいずれ全てのエッジサーバにデータが共有される．
被災者や指定避難所の管理者がエッジサーバにアクセスして物資のニーズや過不足情報を登録する．登録された情報は前述の方法によって共有される．また，リンクが途絶えエッジサーバが孤立しており，データのホップができない場合は，車を中継ノードとして物理的に接続して他のエッジサーバに共有する．その際車に物資を積めば情報と同時に運搬することができると考えている．さらにエッジサーバでデータを蓄積することにより，通信遅延などですぐに共有することができないという時間的不連続性にも対応することができる．

救援物資提供の現状

東日本大震災や熊本地震では家屋が多く倒壊し，大勢の被災者が避難所へ身を寄せることになった．復興庁によると，東日本大震災のピーク時には 2417 箇所も設けられ，長期間の避難が必要となった [2]．その間
避難者には救援物資が提供されるが，避難所のキャパシティを超える避難者がおり，当時は物資の不足や混乱があった．また様々な救援物資が大量に近隣の広い一時的な保管所に一度に集められ，そこから各指定避難所に分配されて届けられる．しかし，指定避難所ではなくその一時的保管所にもらいに行く被災者が出てきてしまい，各避難所に送る物資を仕分けるだけでなく，被災者に渡さなければならず， 現場が混乱してしまったという報告が上がっている [3]．
さらに，届いた救援物資がニーズの変化等で避難所で滞留してしまうことも問題となっている．災害が発生すると国や地方自治体から救援物資が届く．まず一次物資集積拠点に救援物資が集められ，仕分けられ，自治体が管理する各二次物資集積拠点に輸送される．
さらにそこで仕分けられ各避難所へと輸送される流れが基本となっている．一方で個人や民間企業が直接避難所に救援物資を届けることも多い．その場合は国や自治体のコントロール下にないため需要以上の物資が届き在庫を抱えてしまうケースがある．他に需要のある物資があるにもかかわらず，救援物資管理場所の不足・混乱や，余分な物資の管理という作業の増加といった問題が出てきてしまう．しかし一方で，ある避難所では余っている物資も，他の避難所では必要な可能性がある．本研究ではその点に注目し，一次物資集積拠点等を通さず，末端の避難所間で既に届いた物資の需要と供給を満たすことを考えた．物資の過不足情報とニーズを避難所間で共有し，余っている物資を需要のある最適な避難所へと分けることが可能なシステムを

4

最適な経路の決定手法

本論では，事前に各避難所の緯度経度と各間の実際の距離・所要時間を Google Cloud Platform を利用し取得した．さらにそれらの情報を用いて荷物を回収・提供しながら各避難所を一度だけ通るような最適な経路を決定する．巡回セールスマン問題の解決法を用い，以下の条件を設定してコスト関数を作成し，そのコストが最小となる経路を最適とする．現状のコストは経路の総距離または総所要時間である．また物資の余剰を持つ避難所を Depo と呼ぶこととする．1.Depo からスタートし，他の避難所をすべて一度だけ通り最初のDepo に帰る．2. Depo 以外の避難所を一つ通ると荷物を一つ下す．3. 車の最大積載量を設定し，それ以下であれば車に荷物がまだあっても Depo を通った際に車に載せる．4. 車の荷物が全て無くなった避難所から最寄りの Depo に取りに行く．5. 必ず全ての避難所に荷物を下すことができる．

1

経路を決定するにあたり，巡回セールスマン問題の解決法としてよく知られる手法である 2-opt 法と遺伝的アルゴリズム（GA）を採用した．また初期経路はランダムなものと nearest neighbor 法（NN 法）を用いたものを与えた．

5

実験結果

避難所の情報は香南市の指定避難所 48 か所の情報を利用した [4]．そのうちの 5 か所を Depo とし，車の最大積載量を 16，各避難所で得られる物資量は一定として 9 とし，以下の 4 つの手法で得た経路の計算時間とコストを比べる．

• ランダムな初期経路を与える 2-opt 法（2-opt）• ランダムな初期経路を与える GA(GA)• NN 法で作った初期経路を与える 2-opt 法 (NN+2opt)

図 3: 所要時間をエッジの重みとした 4 つの手法の最• NN 法で作った初期経路を与える GA(NN+GA)

はあるが，香南市の指定避難所においては初期経路にNN 法を使うことで良い結果が表れやすいことが分かった．一方で GA は総距離や所要時間が小さくなることが分かるが，実行時間が非常に大きくなってしまった．
実際災害時に運用するにはこの計算時間は非現実的である．GA では全通りの経路を調べるには時間が掛かりすぎてしまうため，一定の世代になったら止めるようにしている．そのためより深く調べればより小さな値は求め得る．しかし，この結果を見ると運用する際には NN+2-opt 法で経路を求めることがコストを早く適度に小さくできると考えられる．しかし GA 法の方がコストが小さくなりやすく，総距離の差が 2km ほど離れていた場合それを良しとして NN+2-opt 法を採用するかどうか議論の余地がある．
また図 2，図 3 を比較すると，距離と所要時間では同じ手法でも経路が異なることが分かる．Google Mapから実際の距離と所要時間を使うことで，その差を見つけることができた．この経路の差の原因は実際の法定速度や信号の多さ等で変化すると考えられ，最短距離が必ずしも最適ではない可能性がある．

短経路の比較

図は香南市の指定避難所を緯度経度を利用してマッピングしており，大きな赤い点が経路の始点及び終点であり，また白抜きの点が Depo となっている．各エッ
ジはある避難所 2ヵ所間の Google Map で推奨される経路の距離または所要時間が重みとなっており，グラフでは直線で表現してある．実際の経路は曲折したり山道であったりしており直線ではない．また，経路を決定する際に距離データと所要時間データでは法定速度や実際の交通状況によって経路に差が出る可能性があるためぞれぞれで実験を行う．
表 1: 手法ごとの計算時間と総距離
手法
計算時間 (sec)
総距離 (km)

2-opt
54.2
71.9

GA3867.5
68.9

NN+2-opt
13.0
69.0

NN+GA
3652.1
67.9

6

まとめと今後の課題

近年日本で多発している大規模災害時に避難生活を送る上で，避難所間で救援物資の過不足を補う必要がある．そこで本論文では実際の指定避難所間で物資を共有する際の運搬経路決定手法を提案し，比較した．
今後は Depo ごと，避難所ごとに任意の物資数を設定し，最適な経路を決定できるか実験する．また，現在は一種類の物資に限定しているが複数の種類の物資を同時に運搬するような決定手法を検討していく．

参考文献[1] 鶴正人，et al. ”DTN 技術の現状と展望” 通信ソサ
イエティマガジン，No.16[春号]，pp.57-68，2011.

図 2: 距離をエッジの重みとした 4 つの手法の最短経路の比較[2] 復興庁，”避難所生活者・避難所の推移（東日本大震災，阪神・淡路大震災及び中越地震の比較）”

表 2: 手法ごとの計算時間と所要時間
手法
実行時間 (sec)
所要時間 (分)

2-opt
57.9
220.0

GA5472.6
171.8

NN+2-opt
20.9
165.3

NN+GA
5732.3165.6[3] 内閣府防災情報のページ，”避難に関する総合的対策の推進に関する実態調査結果報告書”，平成25 年

表 1・表 2 を見ると，NN+2-opt 法が計算時間が短く，総距離・所要時間ともに小さくなることが分かる．
2-opt 法は局所的最適解に陥りやすいアルゴリズムで[4] 香南市，” 香南市地域防災計画の改訂 資料編 (P169- P330)”，2018 年
2