Time-Constrained Sequenced Route Query in Indoor Spaces

Location-based services (LBSs) in indoor spaces have emerged as a new research direction. In this paper, we study a new kind of indoor LBSs that is called Time-Constrained Sequenced Route (TCSR) query. A TCSR query returns a route consisting of a sequence of indoor locations before a given deadline such that each location matches a given location type as well as a given stay-time period. Such queries are popular in indoor spaces, e.g., in a business center, people may want to first stay at a toy shop for 30 min, and then go to a coffee room for one-hour rest, and finally arrive at a cinema before 18:00 PM. Classic route-search algorithms like Dijkstra have to search a large set of possible routes and thus are inefficient for TCSR queries. In addition, they do not consider the multi-floor feature of indoor spaces. In this paper we present a two-stage approach to evaluate a TCSR query. First, we find the optimal floor sequence for a TCSR query. Next, we propose a multi-source Dijkstra algorithm to get the time-constrained sequenced locations in a single floor. We conduct experiments on a synthetic indoor space and the results suggest that our proposal is efficient and scalable.