情報基盤アルゴリズムとして のメタヒューリスティクスの 研究 茨木俊秀、巳波弘佳、藤原洋志、 千葉英史、関口良行（関西学院大 学）、 藤重悟（京都大学）、 柳浦睦憲（名古屋大学）、 野々部宏司（法政大学）、 梅谷俊治（電気通信大学）
メタヒューリスティクスの枠組 ( 初期解生成） 初期解 x を生成 ( 局所探索） x を ( 一般化 ) 局所探索によって改善。 ( 反復） 終了条件がみたされれば、暫定解を出力 して 終了； さもなければ初期解生成へ戻る。 初期解生成： ランダム。過去の良質解を記憶しておき、 それら を変形。交叉あるいはパス再結合。 終了条件： 計算時間。改善状況の利用。
局所探索 (Local Search) 適当な初期解 x (1) から出発 x (i) の近傍 N(x (i) ) 内に改善解が存在すればそれ に置き換えるという操作を、変化が生じなく なるまで反復する
局所探索の設計 近傍： サイズと改善能力、問題固有の構 造 の有効利用。 近傍内の探索順序： ランダム、固定順序 。 移動先： 最初の改善解、最良解、改悪解 も許 す。確率的移動（確率のパラメータ調 節）。 目的関数： ペナルティの利用、適応的変 形。 その他： 複数の近傍の利用、近傍サイズ の 組織的制御、タブーリスト。
メタヒューリスティクスの実現 タブー探索 アニーリング法 遺伝アルゴリズム 反復局所探索 ・・・
箱詰め問題 与えられた n 個の図形（たとえば長方形 ）を重ねずに小さな領域に詰める。 長方形の方向： 固定、９０度回転可能
メタヒューリスティクスによる 解法 長方形の相対的位置の指定 順序対その他の方法 良い順序対の探索は局所探索で 近傍の設計 与えられた順序対の下での最適配置 動的計画法、線形計画法、非線形計 画法 などの利用
計算例 利用領域の最小化 計算例１ 計算例２ 配置制約下の最小化
箱詰め問題（変形１） 長方形のサイズは可変 高さの上下限、幅の上下限 長方形の面積、周長の上下限 ９０度回転：有、なし 領域の高さは指定、幅を最小にする Strip Packing
Area minimization
箱詰め問題（変形２） 長方形には重さがある すべての長方形を領域に詰める 全体の重心を領域の中心へ置く 重心周りのモーメントを最小にする
箱詰め問題（変形３） 一般の形をした n 個の多角形 詰める領域は長方形 多角形の回転角度 : 固定、自由
配送計画問題 最小コストの配送計画を求めよ depot 顧客集合 V={1,2,…,n}, 距離行列 D=(d ij ), 負荷量 q i, 車両 M={1,2,…,m}, 容量 Q k, 移動時間行列 T=(t ij ).
標準タイプ VRP 問題例 時間枠制約付き問題例 Example 1 ExampleExample 2 計算例
一般化、変形、実用化 時間枠制約：単枠、複枠、一般化 所要時間の可変性 集配と配達（ Pickup and delivery ） 応用からのさまざまな制約条件 確率的モデリング
NP 困難 手に負えない 少々手ごわい、 しかし何とかなる （ただし近似解） 結論、今後の課題 現実の多くの問題を解決できる可能性 アルゴリズムの開発の困難さ 標準問題による汎用アルゴリズム