A method for composing tour schedules adaptive to weather change

People do sightseeing in their spare time to relax, and sightseeing is an important industry for some regions. The satisfaction of tourists critically depends on weather during their tours. In order to give people maximum satisfaction, we have to take care of the weather when planning a schedule. However, if there are many possible patterns for weather changes, the number of possible schedules will be very large, and in this case, it is difficult to find a good schedule. In this paper, we formulate the problem to compose schedules for probabilistically changing weather when the probability of future weather is given. We also propose an approximation algorithm for this problem based on the greedy search and the neighborhood search techniques. To evaluate the proposed method, we compare our method with Brute force method and a greedy method for an instance of Beijing sightseeing. As a result, the proposed method found the optimal solution in 6 sec, while the Brute force method took 16 hours. The proposed method composed a schedule whose expected satisfaction is 17.9 composed by the greedy method, for an instance with 20 destinations.