A Tabu Search Approach to the Comida Di Buteco Routing Problem with Soft Time Windows and User Preferences

This work investigates a personalized gastronomic routing problem formulated based on the Personalized Tourist Trip Design Problem (PTTDP) and applied to the 2025 edition of the Comida di Buteco event in Belo Horizonte. The problem considers multiple days, different starting bases, user food preferences, and soft time windows handled through penalties. The utility of each establishment is defined by combining its public rating with the degree of adherence of its dish to the preferences provided by the user.
To solve the problem, a randomized greedy heuristic is used to construct initial solutions, which are subsequently refined by a Tabu Search metaheuristic. A deterministic greedy heuristic is employed as a baseline. The approach is evaluated in ten scenarios with different temporal, geographical, and preference configurations, with ten independent runs of the stochastic methods performed for each scenario.

The results show that the combination of randomized greedy construction and Tabu Search achieved a lower average cost than the baseline in eight out of ten scenarios and outperformed the deterministic solution in 80\% of the one hundred runs performed. The experiments also highlight the trade-off among utility, travel time, and temporal violations in route composition. Regarding
computational cost, Tabu Search accounts for most of the processing time, with a more pronounced increase in scenarios with larger routes. Overall, the results indicate the applicability of the approach to personalized route planning in a real gastronomic context.