避難計画問題：講演記事（2015年）その１

21世紀に入り、大規模な地震・津波、豪雨、ハリケーンなどの自然災害が急増している。2011年3月に発生した東日本大震災では、津波によって多くの被害が発生したことは、記憶に新しい。2015年において、今後30年間に南海トラフ地震が発生する確率が60%～70%と言われており、東海地方、紀伊半島、大阪湾、四国、九州の沿岸地域では巨大な津波に備える必要がある（地震調査研究推進本部地震調査委員会、「南海トラフの地震活動の長期評価（第二版）について」、p.13, 表2, https://www.jishin.go.jp/main/chousa/13may_nankai/nankai2_shubun.pdf）。

防災対策は、事前や応急、事後対策のフェーズに分けられるが、事前や応急対策で、計算機科学や数理科学に基づく情報通信技術の活用場面が被害を最小化するという意味で、重要である。しかし、これらのフェーズでは、大規模な空間データ、災害シナリオの多様性、情報の不確実性、リアルタイム性などが要求されるので、学問的にも挑戦的な課題を内包している。本稿では、事前対策の部分でとくに重要な「避難」の問題に着目して、数理最適化技術がどのように適用可能であるかについて、最近、われわれのグループで行ってきた研究成果について、2回にわたって解説をおこなう。1回目は、背景と最適化技術適用に至るまでの基本的な考え方について述べる。

東日本大震災の教訓として、防波堤、防潮堤などの物理的対策の対策に頼るだけでは、津波に備えるのは限界があることが露呈した。その結果、ソフト対策、なかでも「避難」の問題が注目されるようになり、これまで遅々として進まなかった津波避難ビルの指定が加速化している。また、多くの自治体で、大規模災害に備えて、これまで以上に、具体的な避難計画の立案が進展している。避難計画問題とは、できるだけ多くの避難対象者に可能な限り、速やかかつ安全に、安全な場所に避難させることである。

避難所には、避難所（災害時に一時の間、過ごす場所としての一時避難所と長い間避難生活をおこなう長期避難所がある）、広域避難所（大規模な公園、大学などで一時的に身体を危険から守る場所で避難生活をする位置づけはない）に分類される。

上記の速やかな避難を実現する計画を立てる問題は、まさしく最適化問題である。そこでは、速やかな避難を実現する経路を求める問題や避難場所の立地や割当を求める問題がある。前者は、ネットワーク最適化問題、後者は、最適施設配置問題として、考えることができる。

ここで、避難計画問題の難しさについて述べておこう。それは、いくつかの不確定性から生じている。一つは、災害の種類、大きさ、災害発生場所、時間、季節などの災害発生の不確定性である。それに起因するものとして、人口分布の不確定性がある。大都市のオフィス街や繁華街では、曜日や時間帯によって、人口分布が大きく異なる。このため、事前に非常に多くのシナリオに対して、避難計画を立てておく必要があり、高速計算が求められる。また、住民の避難計画は、各自治体が立案するものなので、汎用のPCで手軽に計算できる必要がある。都市の規模によっては、データサイズも大きくなり、計算の高速化の効果は大きい。これまでの避難計画を立てるための方法として、計算機シミュレーションが主流であった。たとえば、マルチエージェントシミュレーションでは、避難者一人一人をエージェントとして捉え、避難者行動に関する意思決定の詳細な規範をエージェントの行動規範としてモデル化している。一つのエージェントの次の時刻における行動が、そのエージェントの周辺のエージェントの行動から影響を受けて決定されるようなモデル化が行われる。一般に、シミュレーション手法は、あらかじめ用意したシナリオの元で、避難時間の検証や、渋滞の発生等を確認することができ、実際に策定した避難計画の検証をする際には極めて有効であるが、一方で詳細なシミュレーションは一回当たりの計算量が多く、検討することのできるシナリオの数が限られてくるため、避難の前提部分のパラメータを最適化することは困難である。さらに、大都市レベルの避難シミュレーションを、マルチエージェントモデルでおこなうことは計算時間の観点から不可能である．

したがって、大都市規模の避難計画を立案するのに有益な情報を提供するには、シミュレーション手法とは異なる高速計算を実現する必要がある。高速計算をおこなうには、アルゴリズム、ソフトウエアの適切な組合せが必要である。われわれのグループでは、最近の10年間にわたって、避難計画への数理的なアプローチとしてネットワークフローモデルに基づく最速避難計画に関する研究を手掛けてきた。ここでは、モデル化の概要と適用例について、概要を述べる。

以下では、断らない限り、徒歩により避難を考える。まず最初に、道路網を交差点と道路をそれぞれ点（ノード）と辺（エッジ）からなるネットワーク（グラフ）に置き換えることで、都市道路網をモデル化する。通常、ノードは交差点を表すだけでなく、それによって、交差点近傍の住民の居宅を代表させる。これにより、各ノードには、そのノードから避難する住民の数が与えられているものとする。エッジは道路を表しているので、その長さと道幅の情報を与えておく必要がある。道幅から、1分間に何人通ることができるかを求めておく（その値をエッジの容量という）。人間の歩行速度は1ｍ/秒とし、歩行する人間の占める面積は１人/㎡とモデル化する。健常な大人に比べて、お年寄りや子供は歩行速度が遅いが、それは、ここでは無視して考えることにする。この結果、そのエッジを端から端まで移動するのに必要な移動時間が求められる。また、避難所として指定されている場所は、ネットワーク上のノードとしてモデル化される（避難所は複数あってもよい）。避難所の収容人数に上限があるので、その情報もネットワークに加えておく。津波からの避難の場合、津波避難指定ビルに到着するだけでは不十分で、3階以上の安全な場所に移動する必要がある。この場合、建物内の階段を昇るため、その移動速度、通路幅もモデルに加えておく必要がある。以上のネットワークフローモデルは、動的フローモデルと呼ばれる。「動的」という言葉は、モデルに枝上の移動時間が入っているためである。

動的フローモデルによって、滞留、渋滞が表現できることに注意されたい。いま、ネットワークの枝a=(u,v)（uは始点、vは終点）を考えよう。枝aの容量をc(a), 移動時間をt(a)とする。aの点uに避難者がN人いるとして、点vが避難所とする。すべての避難者が避難を完了するのに必要な時間を計算してみよう。

時刻 t=0 にuを出発した避難者は時刻t(a)にvに到着するが、容量c(a)は枝a上を同時に移動できる人数の上限を与えている。時刻 t=0 において頂点uにいるN人は辺 (u,v) を通ってvに移動しようとしているが、単位時間当たりc(a)人しかaに入れない。[N/c(a)]グループがaを移動する（最後のグループを除いて各グループはc(a)人からなっている）。ここで、[N/c(a)]は、N/c(a) の小数点以下を切り上げた値を表す。最初のグループは時刻t(a)にvに到着し、最後のグループは時刻 [N/c(a)]+t(a)-1 に到達する。いま、P人が、点u から辺a=(u, v)、b=(v, w)を通って、点wに移動しようとしている。同時に、vにもQ人がいて、w に移動しようとしているものとする。すると、uを出発した人がvに到達したとき、もともとvにいた人が辺 b=(v,w) に入ることが完了していなくてvに何人かが残っていると、uからvに到達した人は、vで待たされる。ここで、渋滞（滞留）が発生するわけである。つまり、動的フローモデルは、渋滞による待ちを表現できることに注目していただきたい。

動的フローモデルの下で、最速避難計画を考えるわけであるが、そのために目的関数を設定する必要がある。代表的な目的関数は、避難完了時間の最小化である。避難完了時間とは、すべての避難者が避難所に到着し終える時間（つまり、最後に避難所に到着する避難者が要した時間）である。実際のデータを用いて、最速避難完了時間を求めてみると、ある地域の人々の避難時間が他の地域より大きいということがわかる。その結果から、そのような地域には避難所が不足しているとか、道路が狭いというようなことがわかる。最速避難を実現する上でのボトルネックを解消するために必要な情報が得られるのである。

さて、避難完了時間最小化問題を解くアルゴリズムについて説明しよう。この問題は、時間拡大ネットワークの線形計画問題として定式化できる。その詳細について、述べることにする。避難は時刻0から始まるものとする。この問題の変数は、各枝a=(u,v)、各時刻tに対して、点uからaに入るフローの値（避難者数）である。これをx(a,t)と記す。x(a,t)は0以上、aの容量c(a)以下の上下限制約がある。また、各点uと時刻tに着目すると、時刻0からtまでuから出て行ったフローの値（避難者数）の総和は、時刻0からtまでにuに入ってきたフローの総和（避難者数）に元々uに居た避難者数を超えない。以上の制約の下で、すべての避難者が避難所に到達する時間を最小化する問題は線形計画問題として定式化できる。

したがって、Gurobi のような高速な線形計画ソルバーを用いると、効率よく解くことができる。用いる変数の数は道路ネットワークの (点数＋枝数)×時刻ステップ数になる．ここで、時刻ステップ数とは、避難に必要な時間の上限値を単位時間（たとえば、1秒刻みで避難者の動きを見たいときは、単位時間は1秒となる）で割った数である。

そのため、点数が1万、枝数が2万、避難に必要な時間が3600秒というような大都市規模の場合、変数の数が1億になり、非常に大規模な問題となる。そのため、最高速のソルバーでも、計算時間は莫大になり、計算アルゴリズムにも工夫が必要となる。

次回では、南海トラフ地震に伴う津波浸水が予想される和歌山県の沿岸部、徳島市の沿岸地域、大阪市について、おこなった計算実験の結果を中心にお話をする。