An Efficient Framework for Multirequest Route Planning in Urban Environments

Eric Hsueh Chan Lu, Huan Sheng Chen, S. Tseng

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


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.

Original languageEnglish
Article number7604124
Pages (from-to)869-879
Number of pages11
JournalIEEE Transactions on Intelligent Transportation Systems
Issue number4
StatePublished - 1 Apr 2017


  • location-based service (LBS)
  • multirequest route planning (MRRP)
  • Point-of-interest (POI)
  • smart city

Fingerprint Dive into the research topics of 'An Efficient Framework for Multirequest Route Planning in Urban Environments'. Together they form a unique fingerprint.

Cite this