TY - GEN
T1 - Selection and ordering of points-of-interest in large-scale indoor navigation systems
AU - Werner, Martin
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/80055022390
U2 - 10.1109/COMPSAC.2011.71
DO - 10.1109/COMPSAC.2011.71
M3 - Conference contribution
AN - SCOPUS:80055022390
SN - 9780769544397
T3 - Proceedings - International Computer Software and Applications Conference
SP - 504
EP - 509
BT - Proceedings - 35th Annual IEEE International Computer Software and Applications Conference, COMPSAC 2011
T2 - 35th Annual IEEE International Computer Software and Applications Conference, COMPSAC 2011
Y2 - 18 July 2011 through 21 July 2011
ER -