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

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

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). New York NY USA: Association for Computing Machinery (ACM). https://doi.org/10.1145/3274895.3274938
Salgado, Chaluka ; Cheema, Muhammad Aamir ; Taniar, David. / An efficient approximation algorithm for multi-criteria indoor route planning queries. 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. editor / Farnoush Banaei-Kashani ; Erik Hoel ; Ralf Hartmut Guting ; Roberto Tamassia ; Li Xiong. New York NY USA : Association for Computing Machinery (ACM), 2018. pp. 448-451
@inproceedings{befe0352603e47ce9771eb7e98db4904,
title = "An efficient approximation algorithm for multi-criteria indoor route planning queries",
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.",
keywords = "Category aware, Dominance, Indoor query, Route planning",
author = "Chaluka Salgado and Cheema, {Muhammad Aamir} and David Taniar",
year = "2018",
doi = "10.1145/3274895.3274938",
language = "English",
pages = "448--451",
editor = "Farnoush Banaei-Kashani and Erik Hoel and Guting, {Ralf Hartmut} and Roberto Tamassia and Li Xiong",
booktitle = "26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2018)",
publisher = "Association for Computing Machinery (ACM)",
address = "United States of America",

}

Salgado, C, Cheema, MA & Taniar, D 2018, An efficient approximation algorithm for multi-criteria indoor route planning queries. in F Banaei-Kashani, E Hoel, RH 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. Association for Computing Machinery (ACM), New York NY USA, pp. 448-451, ACM International Conference on Advances in Geographic Information Systems 2018, Seattle, United States of America, 6/11/18. https://doi.org/10.1145/3274895.3274938

An efficient approximation algorithm for multi-criteria indoor route planning queries. / Salgado, Chaluka; Cheema, Muhammad Aamir; Taniar, David.

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. ed. / Farnoush Banaei-Kashani; Erik Hoel; Ralf Hartmut Guting; Roberto Tamassia; Li Xiong. New York NY USA : Association for Computing Machinery (ACM), 2018. p. 448-451.

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

TY - GEN

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

AU - Salgado, Chaluka

AU - Cheema, Muhammad Aamir

AU - Taniar, David

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Category aware

KW - Dominance

KW - Indoor query

KW - Route planning

UR - http://www.scopus.com/inward/record.url?scp=85058614602&partnerID=8YFLogxK

U2 - 10.1145/3274895.3274938

DO - 10.1145/3274895.3274938

M3 - Conference Paper

SP - 448

EP - 451

BT - 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2018)

A2 - Banaei-Kashani, Farnoush

A2 - Hoel, Erik

A2 - Guting, Ralf Hartmut

A2 - Tamassia, Roberto

A2 - Xiong, Li

PB - Association for Computing Machinery (ACM)

CY - New York NY USA

ER -

Salgado C, Cheema MA, Taniar D. An efficient approximation algorithm for multi-criteria indoor route planning queries. In Banaei-Kashani F, Hoel E, Guting RH, Tamassia R, Xiong L, editors, 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. New York NY USA: Association for Computing Machinery (ACM). 2018. p. 448-451 https://doi.org/10.1145/3274895.3274938