Efficient Approaches for Multi-requests Route Planning in Urban Areas

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.