複数日の観光スケジュール作成機能を提供するパーソナルナビゲーションシステム
木下 隆正 (0451047)
近年，目的地への経路案内を目的とした，様々なパーソナルナビゲーションシス
テムが実用化されている．
パーソナルナビゲーションシステムの主な用途として観光案内が考えられる．
我々の研究グループでは，複数の観光スポットを時間
制約および重要度を考慮しつつ効率よく巡回するスケジュールの作成機能，およ
び，作成したスケジュールに従って利用者に次の目的地へ経路案内する機能を持っ
たパーソナルナビゲーションシステムP-Tourを提案している．
本研究では，P-Tourで利用可能な，
複数日にわたる観光のためのスケジュール作成機能を提案する．
複数日にわたるスケジュールは，(i) スケジュールそのものが長くなるため巡回する目
的地の組合せ数が多くなり，
また，(ii) 宿泊地など日ごとに必ず立ち寄る必要がある地点を含む，
という特徴を持つ．
そのため，複数日の観光スケジュールを実用時間で計算するには工夫を要する．
提案手法では， (i)に対し，観光対象エリアを幾つかの部分エリアに分割し，
各観光日における宿泊地を部分エリア単位でユーザに指定させ，
また，一日の観光経路におけるエリア境界の越境回数を制限するという方法を採用する．
これにより，各観光日に巡回する対象目的地の組み合せ数を減少させ，計算量を削減する．
また，(ii)に対しては，経路を探索するために遺伝的アルゴリズムを使用し，
日ごとの観光スケジュールを染色体として表し，
各染色体の末尾に対立遺伝子を宿泊地に限定した遺伝子座を持たせる方法を採用する．
これにより，日ごとに宿泊地をただ一つ含む経路の作成が可能になる．
さらに，本研究では，一度の計算でユーザが満足するスケジュールが
得られない場合でも，得られたスケジュールの一部を再計算させることで，段階
的に満足するスケジュールを作成するための機能の提案を行い，P-Tourに組み込
む．提案手法を評価するために，東北エリアの電子地図（国土地理院数値地図
25000）を対象に，複数日の観光スケジュール作成の実験を行い，数十秒で準最
適なスケジュールを作成できることを確認した．