DocumentCode :
3481478
Title :
Selection and Ordering of Points-of-Interest in Large-Scale Indoor Navigation Systems
Author :
Werner, Martin
Author_Institution :
Mobile & Distrib. Syst. Group, Ludwig-Maximilians Univ. Munich, Munich, Denmark
fYear :
2011
fDate :
18-22 July 2011
Firstpage :
504
Lastpage :
509
Abstract :
Indoor navigation systems guide users through complex buildings, which they do not know in advance. The complexity of public buildings such as airports, train stations or hospitals leads to new variants of well-studied NP-hard optimization problems such as the Traveling Salesman Problem, where most of the classical approximations are not directly applicable for fundamental geometric reasons. Fortunately we are able to solve the upcoming small instances of these problems to optimality in a very short timeframe. With this paper we define the Partially Ordered Traveling Salesman Problem, explain how it comes up in indoor navigation applications and present two algorithms, which solve or approximate the Partially Ordered Traveling Salesman Problem for small and medium size instances in a timeframe of less than one second and hence allow for a real time and context-aware indoor navigation experience. We then evaluate both algorithms using realistic data modelling the public area of Munich airport spanning nearly 200.000 square meters.
Keywords :
computational complexity; data models; graph theory; navigation; optimisation; travelling salesman problems; ubiquitous computing; Munich airport; NP-hard optimization problem; context-aware indoor navigation; data modelling; partially ordered traveling salesman problem; points-of-interest selection; public building complexity; Airports; Approximation algorithms; Approximation methods; Biological cells; Genetics; Navigation; Traveling salesman problems; Combinatorial Optimization; Geospatial Information; Indoor Navigation;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Software and Applications Conference (COMPSAC), 2011 IEEE 35th Annual
Conference_Location :
Munich
ISSN :
0730-3157
Print_ISBN :
978-1-4577-0544-1
Electronic_ISBN :
0730-3157
Type :
conf
DOI :
10.1109/COMPSAC.2011.71
Filename :
6032388
Link To Document :
بازگشت