Nowadays, traveling seems necessary for individuals to relieve boredom from daily activities and leave a busy routine. In general, tourists take several days to travel and visit places they have never visited. Thus, a system is needed to automatically recommend optimal tourist routes for several days so that the travel plan is as expected. Several previous studies have developed recommendation systems to determine tourist travel routes, but most of these studies still assume the problem is a TSP. However, the Traveling Salesman Problem (TSP) is typically used to plan single-day travel routes, making it less suitable for multi-day trip planning. Therefore, this study proposes the Vehicle Routing Problem (VRP) analogy, an extended form of TSP. In addition, this research also considers several criteria based on user preferences, such as the number of destinations visited, cost minimization, popularity of places, and duration of travel. It is considered a multi-criteria decision-making problem, which can be solved using the Multi-Attribute Utility Theory (MAUT). This research uses a combination of the K-Means and Simulated Annealing algorithm. This study compared the KSA VRP algorithm with KSA TSP, Firefly VRP, and Firefly TSP. The evaluation was based on four key metrics: fitness value, total cost, total duration, average rating, and running time. Based on the experimental results, the KSA algorithm outperforms the KSA TSP, Firefly VRP, and Firefly TSP algorithms in terms of fitness value, average rating, total duration, and running time.