Stamina-Aware Sightseeing Tour Scheduling Method

観光においては，ユーザの好む観光スポットをより多く回るスケジュールを立案することが望ましい．しかし各観光スポットにつき，観光方式や観光時間によって必要な体力が異なり，ユーザの体力がスケジュールを遂行できない場合がある．本論文では，観光中に休憩を適宜に行うことで体力の範囲内で最も満足度が高くなる観光スケジュールを求める問題を取り扱う．本問題はNP困難であり，問題例の規模が大きいときには，実用時間で最適解を算出することは困難である．実用時間で準最適解を得るため，ヒューリスティックな探索法である捕食法に基づいて複数の観光スポットを回る休憩なしのスケジュールを求めたうえ，局所探索を用いて適宜に休憩を差し挟むことで解を求める．提案手法を評価するため，異なる観光地候補数を有する複数のインスタンスを用いてシミュレーション実験を行った．その結果，候補数10の場合，提案手法は全探索で得られた解の95.65%の満足度を有するスケジュールを13秒で得られることを確認した．Tour schedules are required to include multiple sightseeing spots taking into account the user's preference, but the stamina of tourists may be depleted during sightseeing. In this paper, we formulate the sightseeing scheduling problem to maximize the user's satisfaction taking stamina into account. In this problem, break times are allocated in schedules to hold constraint of stamina. This problem is NP-hard, and thus it is difficult to be solved in practical time. In order to obtain a semi-optimal solution in practical time, we propose a method that derives a schedule visiting multiple sightseeing spots with no break times based on a predatory search technique and then allocates the break times in the schedule using a local search technique. To evaluate the proposed method, we compared our method with conventional methods through computer simulations for several different instances containing 10 sightseeing spots. As a result, the proposed method composed the schedule whose expected satisfaction is 95.65% of the optimum solution in 13 sec