An efficient approximation algorithm for multi-criteria indoor route planning queries

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

3 Citations (Scopus)

Abstract

A route planning query has many real-world applications and has been studied extensively in outdoor spaces such as road networks or Euclidean space. Despite its many applications in indoor venues (e.g., shopping centres, airports), almost all existing studies are specifically designed for outdoor spaces and do not take into account unique properties of the indoor spaces such as hallways, stairs, escalators, rooms etc. We identify this research gap and formally define the problem of category aware multi-criteria route planning query, denoted by CAM, which returns the optimal route from an indoor source point to an indoor target point that passes through at least one indoor point from each given category while minimizing the total cost of the route in terms of travel distance and other relevant attributes. We show that CAM query is NP-hard. We propose an efficient approximation algorithm which generates high-quality results. We provide an extensive experimental study conducted on the largest shopping centre in Australia and compare our algorithms with alternative approaches. The experiments demonstrate that our algorithm is highly efficient and produces quality results.

Original languageEnglish
Title of host publication26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2018)
Subtitle of host publicationTuesday November 6 - Friday November 9, 2018 — Seattle, Washington, USA
EditorsFarnoush Banaei-Kashani, Erik Hoel, Ralf Hartmut Guting, Roberto Tamassia, Li Xiong
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Pages448-451
Number of pages4
ISBN (Electronic)9781450358897
DOIs
Publication statusPublished - 2018
EventACM International Conference on Advances in Geographic Information Systems 2018 - Seattle, United States of America
Duration: 6 Nov 20189 Nov 2018
Conference number: 26th
https://sigspatial2018.sigspatial.org/

Conference

ConferenceACM International Conference on Advances in Geographic Information Systems 2018
Abbreviated titleSIGSPATIAL 2018
CountryUnited States of America
CitySeattle
Period6/11/189/11/18
Internet address

Keywords

  • Category aware
  • Dominance
  • Indoor query
  • Route planning

Cite this

Salgado, C., Cheema, M. A., & Taniar, D. (2018). An efficient approximation algorithm for multi-criteria indoor route planning queries. In F. Banaei-Kashani, E. Hoel, R. H. Guting, R. Tamassia, & L. Xiong (Eds.), 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2018): Tuesday November 6 - Friday November 9, 2018 — Seattle, Washington, USA (pp. 448-451). Association for Computing Machinery (ACM). https://doi.org/10.1145/3274895.3274938