People often query various Points of Interest (POIs) to plan their city tour itineraries using location-based services that provide reviews and ratings of various attributes of a POI. Most traditional location-based recommendation systems focus on various attributes like rating, cost, and social similarities of either POIs, users, or both but do not focus on efficient retrieval of POIs. This paper proposes a spatial index structure uR-tree (utility-based R-tree) for efficiently processing a location-based query implied in a location-aware recommender system to select multiple POIs which a user can visit in a tour. The uR-tree is constructed considering a change in static attributes like availability of parking, basic amenities, etc., and dynamic attributes like ticket price, congestion, etc., of each POI with the aim to maximize a user’s experience. At first, the utility of each POI is calculated at different points of time based on its static and dynamic attributes. A uR-tree is constructed for the systematic indexing of the utility of each POI, and an algorithm is applied for the retrieval of top-k maximum utility POI in different time-intervals. Then, we propose two Utility-based trip scheduling algorithms for distance-based travel recommendations. The experiments were conducted on real-world location-based social network data sets and show that the proposed scheme has a lower response time, Disk I/Os, and a higher query success rate as compared to state-of-the-art, R-tree index structure.