This paper addresses the challenging task of itinerary recommendation for tourists and proposes an approach for suggesting efficient optimal itineraries in Istanbul, based on constraints. The paper presents an enhanced version of the genetic algorithm (GA), which aims to optimize the itineraries considering various constraints and preferences of the tourists. The improvement of the GA involved suggesting a customized fitness function tailored to address the complexities of the tourism problem, considering factors such as distance, time, cost, tourists’ budget, and their desired activities and attractions. Additionally, we proposed a new crossover method, named “Copy Order Crossover” and we modified the tournament selection method beside enhancing the implementation of the swap mutation method for greater efficiency and adaptability. The enhanced GA is evaluated on the Burma dataset taken from TSPLIB, and our constructed Istanbul dataset, achieving significant enhancement rates in GA (43.89% for Istanbul, and 56.60% for Burma). This paper provides a detailed account of the proposed approach, its implementation, and the evaluation conducted. The experimental results conclusively demonstrated the superiority of the proposed approach over alternative methods in terms of time, efficiency, and accuracy. This paper finishes with an outlook with a detailed potential approach to overcome itinerary recommendation problem limitations.