天気の変化に対応可能な観光スケジュール群の局所探索を用いた立案手法
武 兵 (0851135)
観光では，晴天時と雨天時とでは適したスケジュールが異なり，
旅行者の満足度は天気に大きく左右される．そのため，
予め予想された天気に最適な観光スケジュールを事前に作成しておくことが重要である．
本発表では，天気が確率的にしか予測できない場合を想定した，任意の天気変化パターンに対応した
観光スケジュール群を算出する問題を取り扱う．
このスケジュール群は，出発地点を根として目的地ごとに分岐する木
（スケジュール木と呼ぶ）で表現される．
本問題の目的は，スケジュール木によって示さ
れた確率的なスケジュールの，ユーザ満足度の期待値の総和
を最大化することである．
本発表では，この問題を解くための欲張り法および局所探索法に
基づいた近似アルゴリズムを提案する．このアルゴリズムは，
まず欲張り法により初期のスケジュール木を作成し，部分木を単位とした目的地の置換
を繰り返し行うことにより，期待ユーザ満足度が高い
スケジュール木を生成する．
提案手法を評価するため，20の観光地を持つランダムに作成された
インスタンスを用いて実験を行った．
その結果，提案手法は，欲張り法のみを用いた場合と比べて
平均1.23倍の期待値を持つスケジュール木を得ることができた．