Personalized recommendation systems recommend the target destination based on user-generated data from social media and geo-tagged photos that are currently available as a most pertinent source. This paper proposes a tourism destination recommendation system which uses heterogeneous data sources that interprets both texts posted on social media and images of tourist places visited and shared by tourists. For this purpose, we propose an enhanced user profile that uses User-Location Vector with LDA and Jaccard Coefficients. Moreover, a new Tourist Destination tree is constructed using the posts extracted from TripAdvisor where each node of the destination tree consists of tourist destination data. Finally, we build a personalized recommendation system based on user preferences, A* algorithm and heuristic shortest path algorithm with cost optimization based on the backtracking based Travelling Salesman Problem solution, tourist destination tree and tree-based hybrid recommendations. Here, the 0/1 knapsack algorithm is used for recommending the best Tourist Destination travel route plans according to the travel time and cost constraints of the tourists. The experimental results obtained from this work depict that the proposed User Centric Personalized destination and travel route recommendation system is providing better recommendation of tourist places than the existing systems by handling multiple heterogeneous data sources efficiently for recommending optimal tour plans with minimum cost and time.