{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T06:27:37Z","timestamp":1762928857586,"version":"build-2065373602"},"reference-count":37,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2020,12,30]],"date-time":"2020-12-30T00:00:00Z","timestamp":1609286400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Accurate and fast path calculation is essential for applications such as vehicle navigation systems and transportation network routing. Although many shortest path algorithms for restricted search areas have been developed in the past ten years to speed up the efficiency of path query, the performance including the practicability still needs to be improved. To settle this problem, this paper proposes a new method of calculating statistical parameters based on a unidirectional road network model that is more in line with the real world and a path planning algorithm for dynamically restricted search areas that constructs virtual boundaries at a lower confidence level. We conducted a detailed experiment on the proposed algorithm with the real road network in Zhengzhou. As the experiment shows, compared with the existing algorithms, the proposed algorithm improves the search performance significantly in the condition of optimal path under the premise of ensuring the optimal path solution.<\/jats:p>","DOI":"10.3390\/s21010203","type":"journal-article","created":{"date-parts":[[2020,12,30]],"date-time":"2020-12-30T20:13:41Z","timestamp":1609359221000},"page":"203","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Shortest Path Algorithm in Dynamic Restricted Area Based on Unidirectional Road Network Model"],"prefix":"10.3390","volume":"21","author":[{"given":"Haitao","family":"Wei","sequence":"first","affiliation":[{"name":"School of Earth Science and Technology, Zhengzhou University, No. 75 Daxue North Road, Erqi District, Zhengzhou 450052, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shusheng","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Earth Science and Technology, Zhengzhou University, No. 75 Daxue North Road, Erqi District, Zhengzhou 450052, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaohui","family":"He","sequence":"additional","affiliation":[{"name":"School of Earth Science and Technology, Zhengzhou University, No. 75 Daxue North Road, Erqi District, Zhengzhou 450052, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,12,30]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1016\/j.cie.2006.07.007","article-title":"Integration of GIS, GPS, and optimization technologies for the effective control of parcel delivery service","volume":"51","author":"Jung","year":"2006","journal-title":"Comput. Ind. Eng."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/j.optlaseng.2013.08.011","article-title":"Optimization of 3D laser scanning speed by use of combined variable step","volume":"54","author":"Sergiyenko","year":"2014","journal-title":"Opt. Lasers Eng."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1016\/j.compeleceng.2015.10.011","article-title":"Interacting multiple model for improving the precision of vehicle-mounted global position system","volume":"51","author":"Gao","year":"2016","journal-title":"Comput. Electr. Eng."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Amer, H., Salman, N., Hawes, M., Chaqfeh, M., Mihaylova, L., and Mayfield, M. (2016). An improved simulated annealing technique for enhanced mobility in smart cities. Sensors, 16.","DOI":"10.3390\/s16071013"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"101080","DOI":"10.1016\/j.ijdrr.2019.101080","article-title":"Proposal to planning facility location using UAV and geographic information systems in a post-disaster scenario","volume":"36","author":"Leandro","year":"2019","journal-title":"Int. J. Disaster Risk Reduct."},{"key":"ref_6","unstructured":"Leesmiller, J.D., and Wilson, R.E. (2013, January 13\u201317). Hidden Markov models for vehicle tracking with Bluetooth. Proceedings of the Transportation Research Board 92nd Annual Meeting, Washington, DC, USA."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Song, T., Capurso, N., Cheng, X., Yu, J., Chen, B., and Zhao, W. (2017). Enhancing gps with lane-level navigation to facilitate highway driving. IEEE Trans. Veh. Technol., 4579\u20134591.","DOI":"10.1109\/TVT.2017.2661316"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1663","DOI":"10.1017\/S0263574719000183","article-title":"Obstacle Avoidance through Gesture Recognition: Business Advancement Potential in Robot Navigation Socio-Technology","volume":"37","author":"Liu","year":"2019","journal-title":"Robotica"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Zou, D., Niu, S., Chen, S., Su, B., and Li, Y. (2019). A smart city used low-latency seamless positioning system based on inverse global navigation satellite system technology. Int. J. Distrib. Sens. Netw., 15.","DOI":"10.1177\/1550147719873815"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Zhu, D., Du, H., Sun, Y., and Cao, N. (2018). Research on path planning model based on short-term traffic flow prediction in intelligent transportation system. Sensors, 18.","DOI":"10.3390\/s18124275"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Zambrano-Martinez, J.L., Calafate, C.T., Soler, D., Lenin-Guillermo, L.-Z., and Gayraud, T. (2019). A Centralized route-management solution for autonomous vehicles in urban areas. Electronics, 8.","DOI":"10.3390\/electronics8070722"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Song, Q., Li, M., and Li, X. (2018). Accurate and fast path computation on large urban road networks: A general approach. PLoS ONE, 13.","DOI":"10.1371\/journal.pone.0192274"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"6401","DOI":"10.1016\/j.amc.2011.01.019","article-title":"Finding the shortest paths by node combination","volume":"217","author":"Lu","year":"2011","journal-title":"Appl. Math. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/j.ejor.2019.01.007","article-title":"A biobjective Dijkstra algorithm","volume":"276","author":"Colebrook","year":"2019","journal-title":"Eur. J. Oper. Res."},{"key":"ref_15","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_16","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1109\/3477.484436","article-title":"Ant system: Optimization by a colony of cooperating agents","volume":"26","author":"Dorigo","year":"1996","journal-title":"IEEE Trans. Syst. Man. Cybern. Part. B"},{"key":"ref_18","first-page":"1","article-title":"A genetic algorithm for the fuzzy shortest path problem in a fuzzy network","volume":"3","author":"Lin","year":"2020","journal-title":"Complex. Intell. Syst."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"ref_20","unstructured":"Yue, Y., and Gong, J. (1999). An efficient implementation of shortest path algorithm based on Dijkstra algorithm. J. Wuhan Tech. Univ. Surv. Ma., 209\u2013212."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Nordbeck, S., and Rystedt, B. (1969). Computer Cartography: Shortest Route Programs, Gleerup. Royal University of Lund, Department of Geography.","DOI":"10.1007\/BF01933251"},{"key":"ref_22","first-page":"123","article-title":"Shortest path algorithm based on limiting parallelogram and its application in traffic networks","volume":"1","author":"Wang","year":"2006","journal-title":"J. Jilin Univ."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1109\/3468.594911","article-title":"Route finding by using knowledge about the road network","volume":"27","author":"Bing","year":"1997","journal-title":"IEEE Trans. Syst. ManCybern Part A Syst. Hum."},{"key":"ref_24","first-page":"1","article-title":"Partitioning graphs to speed up Dijkstra\u2019s algorithm","volume":"11","author":"Schilling","year":"2005","journal-title":"J. Exp. Algorithmics"},{"key":"ref_25","unstructured":"Chondrogiannis, T., and Gamper, J. (2014, January 21\u201324). Exploring graph partitioning for shortest path queries on road networks. Proceedings of the 26th GI-Workshop Grundlagen von Datenbanken: GvDB\u201914, Bozen, Italy."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1029","DOI":"10.1109\/TKDE.2002.1033772","article-title":"An efficient path computation model for hierarchically structured topographical road maps","volume":"14","author":"Jung","year":"2015","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_27","first-page":"255","article-title":"On the determination of the nondominated paths in a multiobjective network problem","volume":"40","author":"Climaco","year":"1981","journal-title":"Methods. Oper Res."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0377-2217(91)90094-C","article-title":"A parametric approach to solving bicriterion shortest path problems","volume":"53","author":"Mote","year":"1991","journal-title":"Eur. J. Oper. Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1299","DOI":"10.1016\/j.cor.2008.02.002","article-title":"A comparison of solution strategies for biobjective shortest path problems","volume":"36","author":"Raith","year":"2009","journal-title":"Comput. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"788","DOI":"10.1016\/j.ejor.2014.11.003","article-title":"An exact method for the biobjective shortest path problem for large-scale road networks","volume":"242","author":"Duque","year":"2015","journal-title":"Eur. J. Oper. Res."},{"key":"ref_31","first-page":"3","article-title":"Time shortest path algorithm for restricted searching area in transportation networks","volume":"10","author":"Lu","year":"1999","journal-title":"J. Image Graph."},{"key":"ref_32","first-page":"881","article-title":"A route planning algorithm for the shortest distance within a restricted searching area","volume":"10","author":"Fu","year":"2004","journal-title":"J. Beijing Inst. Technol."},{"key":"ref_33","unstructured":"Bu, F., and Fang, H. (2010, January 8\u201310). Shortest path algorithm within dynamic restricted searching area in city emergency rescue. Proceedings of the 2010 IEEE International Conference on Emergency Management and Management Sciences, Beijing, China."},{"key":"ref_34","first-page":"1158","article-title":"Ellipse-based shortest path algorithm for typical urban road networks","volume":"31","author":"Wang","year":"2011","journal-title":"Syst. Eng. Theory Pract."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Zhou, W., Qiu, Q., Luo, P., and Fang, P. (2013, January 27\u201329). An improved shortest path algorithm based on orientation rectangle for restricted searching area. Proceedings of the 2013 IEEE 17th International Conference on Computer Supported Cooperative Work in Design (CSCWD), Whistler, BC, Canada.","DOI":"10.1109\/CSCWD.2013.6581044"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1023\/A:1008751210054","article-title":"supporting different dimensions of adaptability in workflow modeling","volume":"9","author":"Divitini","year":"2000","journal-title":"Comput. Supported Coop. Work"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1109\/TEVC.2002.802444","article-title":"A short convergence proof for a class of ant colony optimization algorithms","volume":"6","author":"Stutzle","year":"2002","journal-title":"IEEE Trans. Evol. Comput."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/1\/203\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:48:07Z","timestamp":1760179687000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/1\/203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,30]]},"references-count":37,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,1]]}},"alternative-id":["s21010203"],"URL":"https:\/\/doi.org\/10.3390\/s21010203","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2020,12,30]]}}}