In general, it is a complicated and time-consuming task for a tourist to plan a satisfactory sightseeing tour, because he/she must take into account various factors and constraints (e.g., budget, available time, etc) at the same time. This difficulty comes from the fact that there is a trade-off between the satisfaction/experience obtained by the sightseeing tour and the resource consumed for the tour, hence the optimal solution is not unique. To help decision making, it is desirable to show the tourist a variety of solutions (i.e., tours) considering the trade-off in various ways, but to the best of our knowledge, no existing methods/systems provide such a wide variety of solutions. In this paper, we formulate the sightseeing tour recommendation as a multi-objective optimization problem with money, time and stamina consumption of a tourist and satisfaction degree obtained by the tourist as independent variables. Since this problem is NP-hard, we propose a heuristic algorithm to quickly obtain semi-pareto optimal solutions based on genetic algorithm NSGA-II. We applied the proposed method to planning tours targeting 30 tourist spots in Higashiyama-area of Kyoto, Japan. As a result, our algorithm could output semi-pareto optimal solutions in reasonable time.