{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T14:02:56Z","timestamp":1784296976163,"version":"3.55.0"},"reference-count":41,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2021,5,31]],"date-time":"2021-05-31T00:00:00Z","timestamp":1622419200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Emergency path planning technology is one of the research hotspots of intelligent transportation systems. Due to the complexity of urban road networks and congested road conditions, emergency path planning is very difficult. Road congestion caused by urban emergencies directly affects the original road network structure. In this way, the static weight of the original road network is no longer suitable as the basis for path recommendation. To handle the dynamic situational road network, an equidistant grid emergency path planning framework will be designed. A novel situation grid road network model, based on situation information, is proposed and applied to an equidistant grid emergency path planning framework. A situational grid heuristic search will be proposed methodology based on this model, which can be used to detect the vehicles passing around the congestion area grid and the road to the destination in the shortest time. In the path planning methodology, a grid inspired search strategy based on quaternion function is included, which can make the algorithm converge to the target grid quickly. Three graph acceleration algorithms are proposed to improve the search efficiency of path planning algorithm. Finally, this paper will set up three experiments to verify our proposed method.<\/jats:p>","DOI":"10.3390\/ijgi10060370","type":"journal-article","created":{"date-parts":[[2021,5,31]],"date-time":"2021-05-31T21:42:06Z","timestamp":1622497326000},"page":"370","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":24,"title":["A Novel Heuristic Emergency Path Planning Method Based on Vector Grid Map"],"prefix":"10.3390","volume":"10","author":[{"given":"Bowen","family":"Yang","sequence":"first","affiliation":[{"name":"College of Computer Science, Beijing University of Technology, Beijing 100124, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jin","family":"Yan","sequence":"additional","affiliation":[{"name":"Institute of Software, Chinese Academy of Sciences, Beijing 100190, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhi","family":"Cai","sequence":"additional","affiliation":[{"name":"College of Computer Science, Beijing University of Technology, Beijing 100124, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhiming","family":"Ding","sequence":"additional","affiliation":[{"name":"College of Computer Science, Beijing University of Technology, Beijing 100124, China"},{"name":"Institute of Software, Chinese Academy of Sciences, Beijing 100190, China"},{"name":"Beijing Key Laboratory on Integration and Analysis of Large-Scale Stream Data, Chinese Academy of Sciences, Beijing 100144, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dongze","family":"Li","sequence":"additional","affiliation":[{"name":"College of Computer Science, Beijing University of Technology, Beijing 100124, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yang","family":"Cao","sequence":"additional","affiliation":[{"name":"School of Information, Beijing Wuzi University, Beijing 101149, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Limin","family":"Guo","sequence":"additional","affiliation":[{"name":"College of Computer Science, Beijing University of Technology, Beijing 100124, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2021,5,31]]},"reference":[{"key":"ref_1","unstructured":"Hojjat, S., Farhad, P., and Siamak, T. (2011, January 6\u20138). Intelligent navigation of emergency vehicles. Proceedings of the 2011 Developments in E-systems Engineering, Dubai, United Arab Emirates."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Meng, X.Z., Zhou, H., and Hu, X.B. (2020, January 1\u20134). Many-to-Many Path Planning for Emergency Material Transportation in Dynamic Environment. Proceedings of the 2020 IEEE Symposium Series on Computational Intelligence (SSCI), Canberra, Australia.","DOI":"10.1109\/SSCI47803.2020.9308496"},{"key":"ref_3","unstructured":"Almeida, J.E., Rossetti, R.J., and Coelho, A.L. (2013). Crowd simulation modeling applied to emergency and evacuation simulations using multi-agent systems. arXiv."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1007\/s10878-018-00377-8","article-title":"Model and algorithm of routes planning for emergency relief distribution in disaster management with disaster information update","volume":"38","author":"Zhu","year":"2019","journal-title":"J. Comb. Optim."},{"key":"ref_5","first-page":"36:1","article-title":"Intelligent evacuation management systems: A review","volume":"7","author":"Venkat","year":"2016","journal-title":"ACM Trans. Intell. Syst. Technol."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1080\/17538947.2018.1425489","article-title":"Mixed reality emergency management: Bringing virtual evacuation simulations into real-world built environments","volume":"12","author":"Lochhead","year":"2019","journal-title":"Int. J. Digit. Earth"},{"key":"ref_7","first-page":"223","article-title":"Driver behavior response to information presentation based on the emergency evacuation procedure of the great East Japan earthquake","volume":"17","author":"Yamabe","year":"2019","journal-title":"Intell. Transp. Syst. Res."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Kim, S., George, B., and Shekhar, S. (2007, January 7\u20139). Evacuation Route Planning: Scalable Heuristics. Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems, Seattle, WA, USA.","DOI":"10.1145\/1341012.1341039"},{"key":"ref_9","first-page":"3291","article-title":"Immune-based approach for optimizing emergency route planning problem: Application to case studies","volume":"9","author":"Khalid","year":"2015","journal-title":"Int. J. Res. Surv."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1080\/15472450.2013.824763","article-title":"An Optimization Model for Guiding Pedestrian-Vehicle Mixed Flows During an Emergency Evacuation","volume":"18","author":"Zhang","year":"2014","journal-title":"J. Intellig. Transport Syst."},{"key":"ref_11","first-page":"454","article-title":"Scalable Stochastic Path Planning under Congestion","volume":"1","author":"Ahmadi","year":"2021","journal-title":"ICAART"},{"key":"ref_12","first-page":"794","article-title":"AutoST: Efficient Neural Architecture Search for Spatio-Temporal Prediction","volume":"Volume 38","author":"Li","year":"2020","journal-title":"Proceedings of the KDD\u201920: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Virtual Event, 6\u201310 July 2020"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Dai, R., Xu, S.K., Gu, Q., Ji, C.G., and Liu, K.K. Hybrid Spatio-Temporal Graph Convolutional Network: Improving Traffic Prediction with Navigation Data. Proceedings of the KDD\u201920: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Virtual Event, 6\u201310 July 2020.","DOI":"10.1145\/3394486.3403358"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Lin, H.X., Bai, R.F., Jia, W.J., Yang, X.Y., and You, Y.J. Preserving Dynamic Attention for Long-Term Spatial-Temporal Prediction. Proceedings of the KDD\u201920: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Virtual Event, 6\u201310 July 2020.","DOI":"10.1145\/3394486.3403046"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"154338","DOI":"10.1109\/ACCESS.2020.3018729","article-title":"A Novel Urban Emergency Path Planning Method Based on Vector Grid Map","volume":"8","author":"Yang","year":"2020","journal-title":"IEEE Access"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"10880","DOI":"10.1109\/ACCESS.2021.3050764","article-title":"Exponential Rank Differential Evolution Algorithm for Disaster Emergency Vehicle Path Planning","volume":"9","author":"Zhang","year":"2021","journal-title":"IEEE Access"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/978-3-540-68552-4_24","article-title":"Contraction Hierarchies: Faster and simpler hierarchical routing in road networks","volume":"5038","author":"Geisberger","year":"2008","journal-title":"Exp. Algorithms"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"104707","DOI":"10.1016\/j.pss.2019.104707","article-title":"Globally optimal rover traverse planning in 3D using Dijkstra\u2019s algorithm for multi-objective deployment scenarios","volume":"179","author":"Fink","year":"2019","journal-title":"Planet. Space Sci."},{"key":"ref_19","first-page":"119","article-title":"Finding optimal route by two-criterion Fuzzy Floyd\u2019s algorithm\u2014Case study Serbia","volume":"20","author":"Pesic","year":"2020","journal-title":"Oper. Res."},{"key":"ref_20","first-page":"190","article-title":"Real-time heuristic search based minimum energy path planning of wheeled mobile robot","volume":"Volume 12","author":"Singh","year":"2015","journal-title":"Proceedings of the AIR\u201915: Proceedings of the 2015 Conference on Advances in Robotics"},{"key":"ref_21","unstructured":"Khalidi, D., and Saha, I. (2018). T*: A Heuristic Search Based Algorithm for Motion Planning with Temporal Goals. arXiv."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Khalidi, D., Gujarathi, D., and Saha, I. (August, January 31). T*: A Heuristic Search Based Path Planning Algorithm for Temporal Logic Specifications. Proceedings of the 2020 IEEE International Conference on Robotics and Automation (ICRA), Paris, France.","DOI":"10.1109\/ICRA40945.2020.9196928"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Bhatia, A., Kavraki, L.E., and Vardi, Y.M. (2010, January 15\u201317). Motion planning with hybrid dynamics and temporal goals. Proceedings of the 49th IEEE Conference on Decision and Control (CDC), Atlanta, GA, USA.","DOI":"10.1109\/CDC.2010.5717440"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"19842","DOI":"10.1109\/ACCESS.2020.2969316","article-title":"Informed RRT*-Connect: An Asymptotically Optimal Single-Query Path Planning Method","volume":"8","author":"Mashayekhi","year":"2020","journal-title":"IEEE Access"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Li, Y.J. (2021, January 4\u20136). An RRT-Based Path Planning Strategy in a Dynamic Environment. Proceedings of the 2021 7th International Conference on Automation, Robotics and Applications (ICARA), Prague, Czech Republic.","DOI":"10.1109\/ICARA51699.2021.9376472"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1016\/j.scitotenv.2019.01.222","article-title":"A vehicle path planning method based on a dynamic traffic network that considers fuel consumption and emissions","volume":"663","author":"Guo","year":"2019","journal-title":"Sci. Total Environ."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1590\/0370-44672018720124","article-title":"Mine Fleet cost evaluation-Dijkstra\u2019s optimized path","volume":"72","author":"Souza","year":"2019","journal-title":"REM-Int. Eng. J."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10846-020-01271-4","article-title":"A Direct Approach of Path Planning Using Environmental Contours","volume":"101","author":"Yu","year":"2021","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1080\/19475683.2020.1755725","article-title":"Multi-factor of path planning based on an ant colony optimization algorithm","volume":"26","author":"Wang","year":"2020","journal-title":"Ann. GIS"},{"key":"ref_30","unstructured":"Page, L., Sergey, B., Rajeev, M., and Terry, W. (1999). The PageRank Citation Ranking: Bringing Order to the Web, Stanford InfoLab."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"69461","DOI":"10.1109\/ACCESS.2020.2986278","article-title":"Short-Term Road Speed Forecasting Based on Hybrid RBF Neural Network With the Aid of Fuzzy System-Based Techniques in Urban Traffic Flow","volume":"8","author":"Ai","year":"2020","journal-title":"IEEE Access"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Keller, S., Gabriel, R., and Guth, J. (2020). Machine Learning Framework for the Estimation of Average Speed in Rural Road Networks with OpenStreetMap Data. ISPRS Int. J. Geo Inf., 9.","DOI":"10.3390\/ijgi9110638"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1007\/978-3-642-41968-3_55","article-title":"Experimental Comparison of A* and D* Lite Path Planning Algorithms for Differential Drive Automated Guided Vehicle","volume":"282","author":"Setiawan","year":"2014","journal-title":"Lect. Notes Electr. Eng."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1142\/S1793351X19400014","article-title":"Evolutionary Heuristic A* Search: Pathfinding Algorithm with Self-Designed and Optimized Heuristic Function","volume":"13","author":"Yiu","year":"2019","journal-title":"Int. J. Semant. Comput."},{"key":"ref_35","first-page":"18","article-title":"Travel Route Planning with Optimal Coverage in Difficult Wireless Sensor Network Environment","volume":"19","author":"Gao","year":"2019","journal-title":"Sensors"},{"key":"ref_36","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_37","doi-asserted-by":"crossref","unstructured":"Yang, K.S., and Shekhar, S. (2017). Evacuation route planning. Spatial Network Big Databases, Springer.","DOI":"10.1007\/978-3-319-56657-3"},{"key":"ref_38","unstructured":"Tuin, M.S., Weerdt, M., and Batz, G.V. (2018, January 24\u201329). Route planning with breaks and truck driving bans using time-dependent Contraction Hierarchies. Proceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling, Delft, The Netherlands."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Nowak, C., Hahne, F., and Ambrosi, K. (2012, January 5\u20137). Contraction Hierarchies with turn restrictions. Proceedings of the Annual Conference of the German Operations Research Society, Hannover, Germany.","DOI":"10.1007\/978-3-319-00795-3_85"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"012005","DOI":"10.1088\/1742-6596\/1756\/1\/012005","article-title":"A Novel Heuristic Method for Emergency Path Planning Based on Dynamic Spatial-Temporal Characteristics Map","volume":"1756","author":"Yang","year":"2021","journal-title":"J. Phys. Conf. Ser."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Yao, R., Ding, Z.M., Cao, Y., and Ren, F.J. (2019, January 15\u201318). A Path Planning Model based on Spatio-Temporal State Vector from Vehicles Trajectories. Proceedings of the 2019 IEEE 4th International Conference on Big Data Analytics (ICBDA), Suzhou, China.","DOI":"10.1109\/ICBDA.2019.8713199"}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/10\/6\/370\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:09:25Z","timestamp":1760162965000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/10\/6\/370"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,31]]},"references-count":41,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2021,6]]}},"alternative-id":["ijgi10060370"],"URL":"https:\/\/doi.org\/10.3390\/ijgi10060370","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,31]]}}}