コロナ禍で重要になる最適化モデル（５）制約最適化

コロナ禍における避難計画

コロナ禍でも災害はやってきます．避難所で集団感染が発生することが危惧されていますが，ダンボールなどでパーティションを作る程度の対処法しか提案されていません．

このようなパンデミック下での大規模避難計画は，従来の研究もほとんどなく，不可能と思われており，政府や自治体も有効な対策を出せないでいます．弊社では，この困難な問題に対する解決法として，最適化を用いた避難所割当を提案します．

まず，避難を希望する人たちは，アプリに以下のような情報を入力します．

１．家族データ

名前
年齢
性別
平熱
熱
心拍数
既往症　
呼吸不全の有無
息切れの有無

この情報から，感染率と感染時の死亡率を計算します．これは，統計的機械学習の手法を用います．実際のデータと計算例は，MITのCOVIDAnalyticsのページで公開されています．

２．避難データ入力

住所
車の台数
予算

基本データとして，避難所，宿泊施設，病院のデータベースを整備します．そこでは，感染者の受け入れの可否や災害時に使用可能か否かなどの諸情報を管理します．避難所の位置と収容人数の情報は，国土交通省のページなどで公開されていますが，東日本大震災後に整備されたもので不十分です．弊社では，政府に頼らない避難所wikiの整備を早急に行うことを提案しています．

感染率と死亡率から最適な避難施設（たんなる避難所ではなく部屋ごとに考えます；また自宅で待機などの1つの施設と考えます）を計算し，アプリ上に表示します．人iが避難施設kに避難した場合に1になる0-1変数 x[i,k] を使うと，問題は2次の目的関数をもつ整数最適化問題として定式化できます．

D[k,l]: 避難施設kとlの間に定義される伝染危険率；施設が近いときに大きくなります．

W[i,j]: 人i,jでの伝染危険率；感染率の差の自乗と以下の量の重み付き和とします．

max(jの感染率 – iの感染率,0)・iの死亡率 + max(iの感染率 – jの感染率,0)・ jの死亡率 

最小化  W[i,j] D[k,l] x[i,k] x[j,l]の合計

すべての人 iに対して，x[i,k]の施設kに対する合計 = 1   

すべての施設kに対して，x[i,k] の人に対する合計が施設kの容量以下   

制約最適化

上の問題は非常に難しいため，通常の整数最適化ソルバーでは解くことができません．弊社の制約最適化ソルバーSCOPでは，以下の変数を用いて定式化します．

X[i] : 人iが避難する施設を表す変数；施設の集合（自宅待機も含む）を領域とする．

これによって変数のサイズが大幅に削減できます．

最小化  W[i,j] D[k,l] (X[i]=k) (X[j]=l)の合計

すべての施設kに対して，X[i]=k の人に対する合計が施設kの容量以下 

さらに，SCOPではメタヒューリスティクスを採用しているため，大規模問題でも高速に実行可能解を算出します．実際には，ユーザーの割当はオンラインで行う必要があり，高速な応答が必要になるため，SCOPによる最適化は必須です．

制約最適化ソルバーSCOPの詳細については，こちらをご参照ください．