An Efficient Framework for Multirequest Route Planning in Urban Environments
- 20 October 2016
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Intelligent Transportation Systems
- Vol. 18 (4) , 869-879
Abstract
In recent years, research on location-based services has received a lot of interest, in both industry and academia, due to a wide range of potential applications. Among them, one of the active topic areas is the constraint-based route planning on a point-of-interest (POI) network. Most of the previous studies on this topic primarily consider the geographic properties of the POIs in planning a route. However, we consider that the reason that a user visits a POI is that it provides some services that the user needs. In particular, in urban environments, a POI may provide various kinds of services. Hence, the user's requests should be considered. In this paper, we address a novel problem, which is called multirequest route planning, and propose a novel framework to efficiently plan a route for serving multiple user-specified requests. The framework consists of two major modules: planning module, in which four approaches with pruning and caching strategies are proposed for planning a preliminary route, and refinement module, in which two refinement mechanisms are proposed for further enhancing the quality of the route. To our best knowledge, this is the first work on route planning that considers multiple services provided by a POI and multiple requests specified by a user, simultaneously. Finally, we perform an extensive experimental evaluation based on three real-world POI data sets and deliver excellent performance.Keywords
Funding Information
- Ministry of Science and Technology of Taiwan (104-2221-E-006-205-, 104-2221-E-009-128-MY3)
This publication has 22 references indexed in Scilit:
- Efficient Trip Planning for Maximizing User Satisfaction2015
- Discovery of Path Nearby Clusters in Spatial NetworksIEEE Transactions on Knowledge and Data Engineering, 2014
- Trip-Mine: An Efficient Trip Planning Approach with Travel Time Constraints2011
- Interactive itinerary planning2011
- A Framework for Personal Mobile Commerce Pattern Mining and PredictionIEEE Transactions on Knowledge and Data Engineering, 2011
- The Dilemma of On-Street Parking Policy: Exploring Cruising for Parking Using an Agent-Based Model2010
- TSP with neighborhoods of varying sizeJournal of Algorithms, 2005
- An Effective Heuristic Algorithm for the Traveling-Salesman ProblemOperations Research, 1973
- A Formal Basis for the Heuristic Determination of Minimum Cost PathsIEEE Transactions on Systems Science and Cybernetics, 1968
- A note on two problems in connexion with graphsNumerische Mathematik, 1959