メンバの分離・合流を許したコスト効率の良いグループ観光スケジュールの作成機能の提案
永田 宗伸 (0451086)
従来からVehicle Routing問題や巡回セールスマン問題など，複数の目的地を
コスト最小で巡回する経路を求める様々な問題が定式化されてきた．これらの
問題は組み合わせ最適化問題であり，最適解を求めることは困難である．
これらの問題を実用時間で解く近似アルゴリズムが多数提案されてきた．
我々の研究グループでも，希望する複数の目的地を与えられた時間制約を満たし，
かつ，できるだけ小さなコストで巡回する経路を算出
する近似アルゴリズムを遺伝的アルゴリズム（以下，GA と呼ぶ）に基づき開
発し，観光のためのパーソナルナビゲーションシステムP-Tour に搭載してい
る．一方，今日の観光では，団体ツアーなど，費用の点で有利なグループによ
る観光の人気が高い．グループ観光は予め決められた経路を巡回するのが基本
であり，参加メンバの細かな嗜好や制約を反映するといった柔軟性はない．
本論文では，訪れたい観光地が少しずつ異なる複数のメンバがグループで観光
する際に，メンバ間で部分的にスケジュールを共有することで，各メンバの希望を満た
こと，トータルの観光コストを小さくすること，の両方を同時にできるだけ満
足するスケジュールを算出する問題を定義し，それを実用時間で計算するGAを
用いた近似アルゴリズムを提案する．グループで観光を行う際には，(1)時間が
許す限りメンバ全員で観光したい，(2)メンバごとに希望が異なる場合には別行動を許可したい，
(3)複数の観光地を与えられた時間内に効率よく回りたい，
といった要求がある．これらの要求をすべて満たすスケジュールを算出する問題では，
メンバの数や巡回候補地の数に応じて，
スケジュール中の単独行動とグループ行動の間の分岐・合流地点の組み合わせ
が爆発的に増える．GAのコーディングでは，解候補における合流・分岐地点を
"参照遺伝子"と呼ばれるワイルドカードで表し，解候補の評価値を計算する際
に，複数メンバのスケジュールをワイルドカードを介して結合するという手法
を採用した．これにより，解候補の符号化，交叉，評価が簡単化されるととも
に致死個体が減少し，広大な解空間を効率よく探索することが可能になっ
た．提案アルゴリズムを実装し，評価実験を行った結果，メンバ数3〜9の実用規模
のグループ観光に対し，高速に準最適な解を得られることを確認した．