避難所割りあて2 目的最小化問題のZDD を用いた厳密解法:非サポート解の存在領域を抽出する高速アルゴリズムの開発

摘要

東日本大震災以降，どこに避難すればよいかという問い合わせが自治体に多く寄せられたため，地区と避難すべき避難所を対応付けることを検討する自治体が出てきている．筆者はZDD1)と呼ばれる離散データのための圧縮データ構造を用いて，いくつかの制約を満たす避難場所の割りあてのパターンを全列挙し，その中から移動距離と収容率和を最小化するパレート解をすべて抽出する方法を提案した2)．パレート解は図1 のように，凸包の頂点を構成するサポート解と，それ以外の非サポート解に分けられる．サポート解は，目的関数の重みをHand proving oracle と呼ばれる計算幾何学の方法によって求めて二つの目的関数値をスカラー化し，ZDD 上のBoole 線形計画法として，解の個数分だけ繰り返し問題を解いて効率的に求められることを既報2)で確認した．一方非サポート解についても，上記の方法で探索を続けて求めたが，図1 の直線L のように，非サポート解の存在領域以外の解も探索してしまい無駄が多かった．そこで本研究では，非サポート解の存在領域の解のみを抽出し，それらについてパレート解の判定を行うことで，従来法よりも高速に非サポート解を求める方法を提案し，大阪市3 区のデータで検証を行う．