The design and planning of group tourist itineraries is a current trend. Group planning should be done according to the maximum capacity of the site under current COVID-19 conditions, the transport flow, and the benefits associated with individual preferences. Tourists commonly express the benefits and limitations of travel in vague and imprecise linguistic terms. In this paper, a hybrid algorithm is presented that combines Greedy Randomized Adaptive Search Procedure, Variable Neighborhood Descendent, and Pareto optimality to solve the multi-objective problem of planning sustainable group tourists itineraries under uncertainty. A set of experiments is performed with real-world tourism data from Sucre, Colombia and benchmark instances from the literature to validate the algorithm’s performance. The results are compared with optimal solutions obtained by CPLEX and other algorithms from previous works. Our approach demonstrates superior performance to different multi-target algorithms and builds more realistic routes.