{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T05:40:07Z","timestamp":1770702007892,"version":"3.49.0"},"reference-count":50,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2021,9,16]],"date-time":"2021-09-16T00:00:00Z","timestamp":1631750400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100007694","name":"Korea Agency for Infrastructure Technology Advancement","doi-asserted-by":"publisher","award":["Grant 20CTAP-C151789-02"],"award-info":[{"award-number":["Grant 20CTAP-C151789-02"]}],"id":[{"id":"10.13039\/501100007694","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>With the growing complexity of indoor living environments, people have an increasing demand for indoor navigation. Currently, navigation path options in indoor are monotonous as existing navigation systems commonly offer single-source shortest-distance or fastest paths. Such path options might be not always attractive. For instance, pedestrians in a shopping mall may be interested in a path that navigates through multiple places starting from and ending at the same location. Here, we name it as the indoor traveling salesman problem (ITSP) path. As its name implies, this path type is similar to the classical outdoor traveling salesman problem (TSP), namely, the shortest path that visits a number of places exactly once and returns to the original departure place. This paper presents a general solution to the ITSP path based on Dijkstra and branch and bound (B&amp;B) algorithm. We demonstrate and validate the method by applying it to path planning in a large shopping mall with six floors, in which the QR (Quick Response) codes are assumed to be utilized as the indoor positioning approach. The results show that the presented solution can successfully compute the ITSP paths and their potentials to apply to other indoor navigation applications at museums or hospitals.<\/jats:p>","DOI":"10.3390\/ijgi10090616","type":"journal-article","created":{"date-parts":[[2021,9,16]],"date-time":"2021-09-16T21:38:12Z","timestamp":1631828292000},"page":"616","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Indoor Traveling Salesman Problem (ITSP) Path Planning"],"prefix":"10.3390","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3140-3462","authenticated-orcid":false,"given":"Jinjin","family":"Yan","sequence":"first","affiliation":[{"name":"Qingdao Innovation and Development Center, Harbin Engineering University, Qingdao 266400, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8766-0487","authenticated-orcid":false,"given":"Sisi","family":"Zlatanova","sequence":"additional","affiliation":[{"name":"School of Built Environment, Faculty of Arts, Design and Architecture, University of New South Wales, Kensington, Sydney, NSW 2052, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4148-4115","authenticated-orcid":false,"given":"Jinwoo (Brian)","family":"Lee","sequence":"additional","affiliation":[{"name":"School of Built Environment, Faculty of Arts, Design and Architecture, University of New South Wales, Kensington, Sydney, NSW 2052, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qingxiang","family":"Liu","sequence":"additional","affiliation":[{"name":"Qingdao Innovation and Development Center, Harbin Engineering University, Qingdao 266400, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,9,16]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1186\/s13673-020-00222-0","article-title":"Indoor positioning and wayfinding systems: A survey","volume":"10","author":"Jayakanth","year":"2020","journal-title":"Hum.-Centric Comput. Inf. Sci."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Yan, J., Diakit\u00e9, A.A., Zlatanova, S., and Aleksandrov, M. (2019). Top-Bounded Spaces Formed by the Built Environment for Navigation Systems. ISPRS Int. J. Geo-Inf., 8.","DOI":"10.3390\/ijgi8050224"},{"key":"ref_3","first-page":"43","article-title":"Navigation for Indoor Location Based On QR Codes and Google Maps\u2014A Survey","volume":"4","author":"Ambareesh","year":"2017","journal-title":"Int. J. Innov. Res. Inf. Secur."},{"key":"ref_4","first-page":"21","article-title":"Indoor Human Navigation Systems: A Survey","volume":"25","author":"Fallah","year":"2013","journal-title":"Interact. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Dudas, P.M., Ghafourian, M., and Karimi, H.A. (2009, January 18\u201320). ONALIN: Ontology and algorithm for indoor routing. Proceedings of the 2009 Tenth International Conference on Mobile Data Management: Systems, Services and Middleware, Taipei, Taiwan.","DOI":"10.1109\/MDM.2009.123"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Ghafourian, M., and Karimi, H.A. (2009). CAD\/GIS Integration Issues for Seamless Navigation between Indoor and Outdoor Environments. CAD and GIS Integration, Auerbach Publications.","DOI":"10.1201\/9781420068061-c6"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Golledge, R.G. (1995). Path selection and route preference in human navigation: A progress report. International Conference on Spatial Information Theory, Springer.","DOI":"10.1007\/3-540-60392-1_14"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1287\/opre.16.3.538","article-title":"The traveling salesman problem: A survey","volume":"16","author":"Bellmore","year":"1968","journal-title":"Oper. Res."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1080\/10556780410001697695","article-title":"Branch and bound algorithms for the multidimensional assignment problem","volume":"20","author":"Pasiliao","year":"2005","journal-title":"Optim. Methods Softw."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.disopt.2016.01.005","article-title":"Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning","volume":"19","author":"Morrison","year":"2016","journal-title":"Discret. Optim."},{"key":"ref_12","first-page":"385","article-title":"A novel path planning algorithm for visually impaired people","volume":"31","author":"Nandini","year":"2019","journal-title":"J. King Saud Univ.-Comput. Inf. Sci."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Duckham, M., and Kulik, L. (2003). \u201cSimplest\u201d paths: Automated route selection for navigation. International Conference on Spatial Information Theory, Springer.","DOI":"10.1007\/978-3-540-39923-0_12"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Liu, L., and Zlatanova, S. (2013). A two-level path-finding strategy for indoor navigation. Intelligent Systems for Crisis Management, Springer.","DOI":"10.1007\/978-3-642-33218-0_3"},{"key":"ref_15","unstructured":"Andreev, S., Dibbelt, J., N\u00f6llenburg, M., Pajor, T., and Wagner, D. (2015, January 17). Towards Realistic Pedestrian Route Planning. Proceedings of the 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015), Patras, Greece."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Balata, J., Berka, J., and Mikovec, Z. (2018). Indoor-Outdoor Intermodal Sidewalk-Based Navigation Instructions for Pedestrians with Visual Impairments. International Conference on Computers Helping People with Special Needs, Springer.","DOI":"10.1007\/978-3-319-94274-2_41"},{"key":"ref_17","first-page":"155","article-title":"The digital pedestrian network in complex urban contexts: A primer discussion on typological specifications","volume":"54","author":"Cambra","year":"2019","journal-title":"Finisterra"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1044","DOI":"10.1109\/TITS.2019.2900858","article-title":"Safe Route Determination for First Responders in the Presence of Moving Obstacles","volume":"21","author":"Wang","year":"2020","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Sharker, M.H., Karimi, H.A., and Zgibor, J.C. (2012, January 6). Health-optimal routing in pedestrian navigation services. Proceedings of the First ACM SIGSPATIAL International Workshop on Use of GIS in Public Health, Redondo Beach, CA, USA.","DOI":"10.1145\/2452516.2452518"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/j.trd.2018.08.007","article-title":"A comparison of route-choice navigation across air pollution exposure, CO2 emission and traditional travel cost factors","volume":"65","author":"Alam","year":"2018","journal-title":"Transp. Res. Part D Transp. Environ."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"2020","DOI":"10.1080\/13658816.2017.1346795","article-title":"An artificial bee colony-based multi-objective route planning algorithm for use in pedestrian navigation at night","volume":"31","author":"Fang","year":"2017","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"175","DOI":"10.5194\/isprs-annals-VI-4-W1-2020-175-2020","article-title":"Two new pedestrian navigation path options based on semi-indoor space","volume":"VI-4\/W1-2020","author":"Yan","year":"2020","journal-title":"ISPRS Ann. Photogramm. Remote Sens. Spat. Inf. Sci."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1109\/34.387512","article-title":"Finding shortest paths on surfaces using level sets propagation","volume":"17","author":"Kimmel","year":"1995","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"259","DOI":"10.5623\/cig2013-052","article-title":"Pedestrian navigation services: Challenges and current trends","volume":"67","author":"Karimi","year":"2013","journal-title":"Geomatica"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1109\/TITS.2006.889439","article-title":"Developing landmark-based pedestrian-navigation systems","volume":"8","author":"Millonig","year":"2007","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Zar, M.T., and Sein, M.M. (2016). Finding shortest path and transit nodes in public transportation system. Genetic and Evolutionary Computing, Springer.","DOI":"10.1007\/978-3-319-23204-1_34"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"39","DOI":"10.3141\/1773-05","article-title":"Cycling to work in Phoenix: Route choice, travel behavior, and commuter characteristics","volume":"1773","author":"Howard","year":"2001","journal-title":"Transp. Res. Rec."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1080\/13658810801949850","article-title":"Finding shortest paths on real road networks: The case for A","volume":"23","author":"Zeng","year":"2009","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Kolavali, S.R., and Bhatnagar, S. (2008). Ant colony optimization algorithms for shortest path problems. International Conference on Network Control and Optimization, Springer.","DOI":"10.1007\/978-3-642-00393-6_5"},{"key":"ref_30","first-page":"225","article-title":"The traveling salesman problem","volume":"7","author":"Reinelt","year":"1995","journal-title":"Handb. Oper. Res. Manag. Sci."},{"key":"ref_31","first-page":"1573","article-title":"Traveling salesman problem","volume":"1","author":"Hoffman","year":"2013","journal-title":"Encycl. Oper. Res. Manag. Sci."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"3806","DOI":"10.1016\/j.asoc.2013.05.009","article-title":"The travelling salesman problem with time windows: Adapting algorithms from travel-time to makespan optimization","volume":"13","author":"Blum","year":"2013","journal-title":"Appl. Soft Comput."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1016\/j.cor.2017.06.026","article-title":"An integer programming approach for the time-dependent traveling salesman problem with time windows","volume":"88","author":"Montero","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1016\/j.cor.2007.11.008","article-title":"A comparative analysis of several asymmetric traveling salesman problem formulations","volume":"36","author":"Laporte","year":"2009","journal-title":"Comput. Oper. Res."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.omega.2004.10.004","article-title":"The multiple traveling salesman problem: An overview of formulations and solution procedures","volume":"34","author":"Bektas","year":"2006","journal-title":"Omega"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.cie.2019.01.020","article-title":"Multiple traveling salesman problem with drones: Mathematical model and heuristic approach","volume":"129","author":"Kitjacharoenchai","year":"2019","journal-title":"Comput. Ind. Eng."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/j.orl.2020.01.009","article-title":"Branch-and-bound for the precedence constrained Generalized Traveling Salesman Problem","volume":"48","author":"Salman","year":"2020","journal-title":"Oper. Res. Lett."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Werner, M. (2011, January 18\u201322). Selection and ordering of points-of-interest in large-scale indoor navigation systems. Proceedings of the 2011 IEEE 35th Annual Computer Software and Applications Conference, Munich, Germany.","DOI":"10.1109\/COMPSAC.2011.71"},{"key":"ref_39","unstructured":"Munkres, J.R. (1984). Elements of Algebraic Topology, Addison-Wesley Menlo Park."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1080\/17538947.2021.1913522","article-title":"A unified 3D space-based navigation model for seamless navigation in indoor and outdoor","volume":"14","author":"Yan","year":"2021","journal-title":"Int. J. Digit. Earth"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Idrees, A., Iqbal, Z., and Ishfaq, M. (2015, January 15\u201317). An efficient indoor navigation technique to find optimal route for blinds using QR codes. Proceedings of the 2015 IEEE 10th Conference on Industrial Electronics and Applications (ICIEA), Auckland, New Zealand.","DOI":"10.1109\/ICIEA.2015.7334197"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1093\/comjnl\/24.2.167","article-title":"Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes","volume":"24","author":"Watson","year":"1981","journal-title":"Comput. J."},{"key":"ref_43","unstructured":"Xie, D., Zhu, H., Yan, L., Yuan, S., and Zhang, J. (2012, January 24\u201328). An improved Dijkstra algorithm in GIS application. Proceedings of the World Automation Congress 2012, Puerto Vallarta, Mexico."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1273","DOI":"10.1111\/tgis.12574","article-title":"A generic space definition framework to support seamless indoor\/outdoor navigation systems","volume":"23","author":"Yan","year":"2019","journal-title":"Trans. GIS"},{"key":"ref_45","first-page":"135","article-title":"Efficient many-to-many path planning and the Traveling Salesman Problem on road networks","volume":"20","author":"Roth","year":"2016","journal-title":"Int. J. Knowl.-Based Intell. Eng. Syst."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/j.eswa.2018.12.044","article-title":"The harmony search algorithm with additional improvement of harmony memory for asymmetric traveling salesman problem","volume":"122","author":"Boryczka","year":"2019","journal-title":"Expert Syst. Appl."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"654","DOI":"10.1002\/(SICI)1520-6750(199909)46:6<654::AID-NAV4>3.0.CO;2-A","article-title":"Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries","volume":"46","author":"Anily","year":"1999","journal-title":"Nav. Res. Logist."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/s001860200239","article-title":"Approximation algorithms for the traveling salesman problem","volume":"56","author":"Monnot","year":"2003","journal-title":"Math. Methods Oper. Res."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"2935","DOI":"10.1007\/s00521-017-2880-4","article-title":"A hybrid algorithm using a genetic algorithm and multiagent reinforcement learning heuristic to solve the traveling salesman problem","volume":"30","author":"Alipour","year":"2018","journal-title":"Neural Comput. Appl."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"622","DOI":"10.1016\/j.swevo.2018.08.004","article-title":"An artificial bee colony algorithm with a modified choice function for the traveling salesman problem","volume":"44","author":"Choong","year":"2019","journal-title":"Swarm Evol. Comput."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/10\/9\/616\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:00:31Z","timestamp":1760166031000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/10\/9\/616"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,16]]},"references-count":50,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2021,9]]}},"alternative-id":["ijgi10090616"],"URL":"https:\/\/doi.org\/10.3390\/ijgi10090616","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,16]]}}}