Tourism route optimization is a well-established problem that involves designing routes to enhance visitor experiences in tourist-heavy areas. In the context of complex networks such as historical medinas, this problem becomes significantly more challenging due to intricate layouts and constraints. In this work, we conduct a comparative and analytical study of four widely used metaheuristic algorithms: Genetic Algorithm (GA), Simulated Annealing (SA), Ant Colony Optimization (ACO), and Grey Wolf Optimizer (GWO). The old medina of Fez, Morocco, is used as a case study to demonstrate the strengths and weaknesses of each method, offering insights into their suitability for tourism route optimization in complex scenarios. Experiments conducted on instances of three scales: small, medium, and large, demonstrate that SA outperforms the other methods in terms of solution quality, consistently generating the best circuit across all instances, while GWO stands out as the most efficient in terms of execution time, making it scalable for time-sensitive applications.