Efficient approaches for multi-requests route planning in urban areas

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

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

5 Scopus citations

Abstract

In recent years, with the rapid developments of wireless technologies, researches on Location-Based Services (LBSs) have attracted extensive attentions and one active topic among them is constraint-based route planning on a Point-Of-Interest (POI) network. Although a number of studies on this topic have been proposed in literatures, most of them primarily consider the geographic properties of the POIs in planning a route. In fact, the motivation of a user to visit a POI is frequently due to that the POI can provide some services meeting the user's needs. Hence, user requests should be considered in route planning, especially in an urban area where a POI may provide various kinds of services. Besides, the efficiency of route planning is critical in such kind of real-time LBS applications. In this paper, we address a novel route planning problem named Multi-Requests Route Planning (MRRP) and propose four approaches, namely kNN-MS, kMD-MS, EMB and kRA-MS to efficiently plan a time-saving route based on the user-specific requests. Furthermore, we propose two refinement mechanisms, three pruning strategies and two caching techniques to further enhance the route quality and planning efficiency for MRRP, respectively. To the best of our 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. Through extensive experimental evaluations, our approaches were shown to deliver excellent performance.

Original languageEnglish
Article number6569120
Pages (from-to)36-45
Number of pages10
JournalProceedings - IEEE International Conference on Mobile Data Management
Volume1
DOIs
StatePublished - 11 Sep 2013
Event14th International Conference on Mobile Data Management, MDM 2013 - Milan, Italy
Duration: 3 Jun 20136 Jun 2013

Keywords

  • Data Mining
  • Location-Based Service
  • Route Planning
  • Urban Computing

Fingerprint Dive into the research topics of 'Efficient approaches for multi-requests route planning in urban areas'. Together they form a unique fingerprint.

Cite this