A stamina-aware sightseeing tour scheduling method

In general, a tour schedule is composed of multiple sightseeing spots taking into account the user' s preferences. However, during the tour, the stamina of the tourists may be exhausted. In this paper, we propose a sightseeing scheduling method that maximizes the degree of user satisfaction taking stamina into account. In our method, break times are allocated in the schedule to satisfy the stamina constraint. Since this problem implies a TSP and thus is NP-hard, it is difficult to solve in practical time. To calculate a semi-optimal solution in practical time, we propose a method that first composes a schedule visiting multiple sightseeing spots without considering stamina, and then, to recover stamina, allocates break times, based on a predatory search technique. To evaluate the proposed method, we compared our method through a simulation experiment with some conventional methods including a brute-force method. As a result, the proposed method composed a schedule in practical time whose expected degree of satisfaction was near the optimum.