A recommender system is currently applied in many different domains, seeking to provide users with recommendation services according to their personalized preferences to relieve rising online information congestion. As the number of mobile phone users is large and growing, mobile tourist guides have attracted considerable research interest in recent years. In this paper, we propose an optimal travel route recommender system by analyzing the data history of previous users. The open dataset used covers the travel data from thousands of mobile tourists who visited Jeju in a full year. Our approach is not only personalized to users’ preferences but also able to recommend a travel route rather than individual POIs (Points of Interest). An association rule mining-based approach, which takes into account contextual information (date, season and places already visited by previous users), is used to produce travel routes from the large dataset. Furthermore, to ensure the reasonability of the recommendation, a genetic algorithm optimization approach is proposed to find the optimal route among them. Finally, a mobile tourist case study is implemented in order to verify the feasibility and applicability of the proposed system. This application embeds a graphic map for plotting the travel route and provides detailed information of each travel spot as well. The results of this work indicate that the proposed system has great potential for travel planning preparation for mobile users.