With the rapid development of wireless telecommunication technologies, a number of studies have been done on the Location-Based Services (LBSs) due to wide applications. Among them, one of the active topics is travel recommendation. Most of previous studies focused on recommendations of attractions or trips based on the user's location. However, such recommendation results may not satisfy the travel time constraints of users. Besides, the efficiency of trip planning is sensitive to the scalability of travel regions. In this paper, we propose a novel data mining-based approach, namely Trip-Mine, to efficiently find the optimal trip which satisfies the user's travel time constraint based on the user's location. Furthermore, we propose three optimization mechanisms based on Trip-Mine to further enhance the mining efficiency and memory storage requirement for optimal trip finding. To the best of our knowledge, this is the first work that takes efficient trip planning and travel time constraints into account simultaneously. Finally, we performed extensive experimental evaluations and show that our proposals deliver excellent results.