{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T18:26:42Z","timestamp":1775068002795,"version":"3.50.1"},"reference-count":52,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T00:00:00Z","timestamp":1739145600000},"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>During natural disasters such as earthquakes, fires, or landslides, the timely passage of special vehicles (primarily oversized vehicles) is crucial for successful emergency rescue operations. Efficient route planning algorithms capable of handling large-scale road networks are essential to facilitate this. This paper focuses on the rapid dispatch of special vehicles to their destinations within large-scale national road networks during emergency rescue operations. Using China\u2019s national road network as a case study, a dual-layer road network data model was proposed to separate high-grade expressways from low-grade ordinary roadways to optimize data storage and access. A two-level spatial grid framework is also introduced to efficiently segment, extract, and store road network data. An improved algorithm constrained by a shortest-route planning objective function is proposed to improve route planning efficiency. This algorithm optimizes data access by loading high-grade road network data into memory once and only loading the necessary grid segments of low-grade road network data during route planning. The objective function incorporates constraints such as bridge weight and tunnel height limitations to ensure the safe passage of special vehicles. A parallelized bidirectional Dijkstra algorithm was proposed to further accelerate route planning. This approach simultaneously searches for optimal routes from both the starting and ending points, significantly improving efficiency for large-scale, cross-regional route planning. Experimental results demonstrate that our improved road network model and algorithm reduce search time by 1.69 times compared to conventional methods. The parallelized bidirectional Dijkstra algorithm further accelerates route planning by a factor of 3.75, achieving comparable performance to commercial software. The proposed road network model, route planning algorithm, and related findings offer valuable insights for optimizing emergency rescue operations and ensuring cost-effective resource allocation.<\/jats:p>","DOI":"10.3390\/ijgi14020071","type":"journal-article","created":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T10:25:57Z","timestamp":1739355957000},"page":"71","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["An Efficient Route Planning Algorithm for Special Vehicles with Large-Scale Road Network Data"],"prefix":"10.3390","volume":"14","author":[{"given":"Ting","family":"Tian","sequence":"first","affiliation":[{"name":"School of Computer and Artificial Intelligence, Zhengzhou University, Zhengzhou 450001, China"}]},{"given":"Huijing","family":"Wu","sequence":"additional","affiliation":[{"name":"School of Computer and Artificial Intelligence, Zhengzhou University, Zhengzhou 450001, China"}]},{"given":"Haitao","family":"Wei","sequence":"additional","affiliation":[{"name":"School of Geo-Technology, Zhengzhou University, Zhengzhou 450001, China"}]},{"given":"Fang","family":"Wu","sequence":"additional","affiliation":[{"name":"School of Geo-Technology, Zhengzhou University, Zhengzhou 450001, China"}]},{"given":"Mingliang","family":"Xu","sequence":"additional","affiliation":[{"name":"School of Computer and Artificial Intelligence, Zhengzhou University, Zhengzhou 450001, China"}]}],"member":"1968","published-online":{"date-parts":[[2025,2,10]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Cho, J.-H., Shin, Y.-S., Kim, J.-J., and Kim, B.-S. (2024). Exploring Cost Variability and Risk Management Optimization in Natural Disaster Prevention Projects. Buildings, 14.","DOI":"10.3390\/buildings14020391"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"e12582","DOI":"10.1111\/1468-5973.12582","article-title":"Research on the Influence of Emergency Rescue Information Importance on Emergency Decisions","volume":"32","author":"Jiang","year":"2024","journal-title":"J. Conting. Crisis Manag."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Luo, Q., Liu, H., Liu, C., and Deng, Q. (2024). Multi-Strategy Cooperative Scheduling for Airport Specialized Vehicles Based on Digital Twins. Sci. Rep., 14.","DOI":"10.1038\/s41598-024-66350-0"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"104167","DOI":"10.1016\/j.ijdrr.2023.104167","article-title":"Assessing Road Network Resilience in Disaster Areas from a Complex Network Perspective: A Real-Life Case Study from China","volume":"100","author":"Wei","year":"2024","journal-title":"Int. J. Disaster Risk Reduct."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1705","DOI":"10.1007\/s12053-020-09900-5","article-title":"Energy efficient route planning for electric vehicles with special consideration of the topography and battery lifetime","volume":"13","author":"Perger","year":"2020","journal-title":"Energy Effic."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"D\u2019Emidio, M., Delfaraz, E., Di Stefano, G., Frittella, G., and Vittoria, E. (2024). Route Planning Algorithms for Fleets of Connected Vehicles: State of the Art, Implementation, and Deployment. Appl. Sci., 14.","DOI":"10.3390\/app14072884"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","article-title":"The Truck Dispatching Problem","volume":"6","author":"Dantzig","year":"1959","journal-title":"Manag. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"975","DOI":"10.1177\/0954407020969992","article-title":"Driving-Behavior-Oriented Trajectory Planning for Autonomous Vehicle Driving on Urban Structural Road. Proc. Inst","volume":"235","author":"Zeng","year":"2021","journal-title":"Mech. Eng. Part D J. Automob. Eng."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1002\/asjc.3075","article-title":"Multi-AGV Route Planning in Automated Warehouse System Based on Shortest-Time Q-Learning Algorithm","volume":"26","author":"Zheng","year":"2023","journal-title":"Asian J. Control"},{"key":"ref_10","first-page":"1002","article-title":"Dynamic Online Multimodal Route Planning with Least Expected Travel Time in the Stochastic and Time-Dependent Bus Network","volume":"259","author":"Li","year":"2019","journal-title":"Acad. Lead."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"103864","DOI":"10.1016\/j.jtrangeo.2024.103864","article-title":"Using Shortest Path Routing to Assess Cycling Networks","volume":"117","author":"Reid","year":"2024","journal-title":"J. Transp. Geogr."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"81","DOI":"10.23919\/JSEE.2023.000005","article-title":"Joint Mission and Route Planning of Unmanned Air Vehicles via a Learning-Based Heuristic","volume":"34","author":"Shi","year":"2023","journal-title":"J. Syst. Eng. Electron."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"e516","DOI":"10.1016\/j.jpainsymman.2024.02.282","article-title":"Hospice Care in Emergency Planning and Response","volume":"67","author":"Rogers","year":"2024","journal-title":"J. Pain Symptom Manag."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Huang, B., Zhang, F., and Lei, L. (2022). Dynamic Path Planning Based on Service Level of Road Network. Electronics, 11.","DOI":"10.3390\/electronics11203267"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"129526","DOI":"10.1016\/j.physa.2024.129526","article-title":"Modeling the road network capacity in a mixed HV and CAV environment","volume":"636","author":"Zhou","year":"2024","journal-title":"Phys. A: Stat. Mech. Its Appl."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/j.inffus.2019.06.006","article-title":"On identification of driving-induced stress using electroencephalogram signals: A framework based on wearable safety-critical scheme and machine learning","volume":"53","author":"Halim","year":"2020","journal-title":"Inf. Fusion"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"11747","DOI":"10.1007\/s12652-022-03734-y","article-title":"Deep neural network-based identification of driving risk utilizing driver dependent vehicle driving features: A scheme for critical infrastructure protection","volume":"14","author":"Halim","year":"2022","journal-title":"J. Ambient. Intell. Humaniz. Comput."},{"key":"ref_18","first-page":"1","article-title":"Quantum Algorithms Using Infeasible Solution Constraints for Collision-Avoidance Route Planning","volume":"1","author":"Li","year":"2024","journal-title":"IEEE Trans. Consum. Electron."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1016\/j.isatra.2021.03.041","article-title":"An efficient and global interactive optimization methodology for path planning with multiple routing constraints","volume":"121","author":"Xie","year":"2022","journal-title":"ISA Trans."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1016\/j.trc.2015.03.006","article-title":"A dynamic Bayesian network model for real-time crash prediction using traffic speed conditions data","volume":"54","author":"Sun","year":"2015","journal-title":"Transp. Res. Part C Emerg. Technol."},{"key":"ref_21","first-page":"92","article-title":"Research on intelligent vehicle Traffic Flow control algorithm based on data mining","volume":"5","author":"Cheng","year":"2024","journal-title":"Int. J. Intell. Netw."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"171","DOI":"10.14445\/22315381\/IJETT-V70I1P219","article-title":"Genetic Algorithm for Tourism Route Planning Considering Time Constrains","volume":"70","author":"Choi","year":"2022","journal-title":"Int. J. Eng. Trends Technol."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Tan, L., Zhu, K., and Yi, J. (2024). Vehicle Route Planning of Diverse Cargo Types in Urban Logistics Based on Enhanced Ant Colony Optimization. World Electr. Veh. J., 15.","DOI":"10.3390\/wevj15090405"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/ACCESS.2023.3302698","article-title":"Route Planning for an Autonomous Robotic Vehicle Employing a Weight-Controlled Particle Swarm-Optimized Dijkstra Algorithm","volume":"11","author":"Sundarraj","year":"2023","journal-title":"IEEE Access"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/trsc.2023.intro.v58.n1","article-title":"Introduction to the Special Issue on Machine Learning Methods and Applications in Large-Scale Route Planning Problems","volume":"58","author":"Winkenbach","year":"2024","journal-title":"Transp. Sci."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1155\/2020\/8889903","article-title":"Research on Optimization of Improved Gray Wolf Optimization-Extreme Learning Machine Algorithm in Vehicle Route Planning","volume":"2020","author":"Li","year":"2020","journal-title":"Discret. Dyn. Nat. Soc."},{"key":"ref_27","first-page":"1","article-title":"ERRRT-A*: A fast path planning algorithm suitable for large-scale scenes","volume":"46","author":"Zhang","year":"2024","journal-title":"J. Intell. Fuzzy Syst."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1002\/net.22174","article-title":"Targeted Multi-Objective Dijkstra Algorithm","volume":"82","author":"Pedro","year":"2023","journal-title":"Networks"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1016\/j.future.2021.03.007","article-title":"Robot Path Planning by Leveraging the Graph-Encoded Floyd Algorithm","volume":"122","author":"Lv","year":"2021","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1177\/00202940241228725","article-title":"Precise Path Planning and Trajectory Tracking Based on Improved A-Star Algorithm","volume":"57","author":"Xu","year":"2024","journal-title":"Meas. Control"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Gan, X., and Liu, J. (2017, January 5\u20138). A Multi-Objective Evolutionary Algorithm for Emergency Logistics Scheduling in Large-Scale Disaster Relief. Proceedings of the 2017 IEEE Congress on Evolutionary Computation, Donostia, Spain.","DOI":"10.1109\/CEC.2017.7969295"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1049\/iet-its.2019.0332","article-title":"Robust Multi-Objective Vehicle Routing Problem with Time Windows for Hazardous Materials Transportation","volume":"14","author":"Men","year":"2020","journal-title":"IET Intell. Transp. Syst."},{"key":"ref_33","first-page":"337","article-title":"A Hybrid Heuristic Approach for the Multi-Objective Multi-Depot Vehicle Routing Problem","volume":"15","author":"Walter","year":"2024","journal-title":"Int. J. Ind. Eng. Comput."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1504\/IJCSM.2024.136816","article-title":"Application of a Hybrid Genetic Algorithm Based on the Travelling Salesman Problem in Rural Tourism Route Planning","volume":"19","author":"Chen","year":"2024","journal-title":"Int. J. Comput. Sci. Math."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"114408","DOI":"10.1016\/j.eswa.2020.114408","article-title":"The Parallelization of a Two-Phase Distributed Hybrid Ruin-and-Recreate Genetic Algorithm for Solving Multi-Objective Vehicle Routing Problem with Time Windows","volume":"168","author":"Khoo","year":"2021","journal-title":"Expert Syst. Appl."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Muhammad, A., and Mohamed, Z. (2023). Multi-Objective Message Routing in Electric and Flying Vehicles Using a Genetics Algorithm. Sensors, 23.","DOI":"10.3390\/s23031100"},{"key":"ref_37","first-page":"156","article-title":"An Ant Colony Optimization for the Bi-Objective Vehicle Routing Problem with Time Windows on Multigraph","volume":"18","author":"Chai","year":"2018","journal-title":"J. Transp. Syst. Eng. Inf. Technol."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.susoc.2023.02.002","article-title":"An Adaptive Ant Colony Algorithm for Crowdsourcing Multi-Depot Vehicle Routing Problem with Time Windows","volume":"4","author":"Xue","year":"2023","journal-title":"Sustain. Oper. Comput."},{"key":"ref_39","first-page":"3535","article-title":"Improved Ant Colony Optimization Algorithm for Vehicle Routing Problems with Time Window","volume":"28","author":"Lei","year":"2022","journal-title":"Comput. Integr. Manuf. Syst."},{"key":"ref_40","first-page":"221","article-title":"Hybrid Particle Swarm Optimization for Solving VRPSPD Problems with Soft Time Windows","volume":"54","author":"Fan","year":"2018","journal-title":"Comput. Eng. Appl."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"1732","DOI":"10.1109\/TLA.2018.8444393","article-title":"An Improved Particle Swarm Optimization Algorithm for the VRP with Simultaneous Pickup and Delivery and Time Windows","volume":"16","author":"Lagos","year":"2018","journal-title":"IEEE Lat. Am. Trans."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"1058","DOI":"10.1109\/TITS.2020.3019791","article-title":"Utility-Based Matching of Vehicles and Hybrid Requests on Rider Demand Responsive Systems","volume":"23","author":"Lai","year":"2022","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s43020-023-00116-3","article-title":"Performance analysis of frequency-mixed PPP-RTK using low-cost GNSS chipset with different antenna configurations","volume":"4","author":"Li","year":"2023","journal-title":"Satell. Navig."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Wang, X., Cai, Y., He, K., Wang, S., Liu, Y., and Dong, Y. (2023). Global\u2013Local Information Fusion Network for Road Extraction: Bridging the Gap in Accurate Road Segmentation in China. Remote Sens., 15.","DOI":"10.3390\/rs15194686"},{"key":"ref_45","unstructured":"(2020). Handbook of Technical Standards and Design Specifications for Highway Engineering, People\u2019s Communications Press. [3rd ed.]."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.aej.2023.12.044","article-title":"Intelligent path planning by an improved RRT algorithm with dual grid map","volume":"88","author":"Zhang","year":"2024","journal-title":"Alex. Eng. J."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"237","DOI":"10.12989\/sem.2016.60.2.237","article-title":"Girder distribution factors for steel bridges subjected to permit truck or super load","volume":"60","author":"Tabsh","year":"2016","journal-title":"Struct. Eng. Mech."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"111847","DOI":"10.1016\/j.buildenv.2024.111847","article-title":"The impact of twisted wind on pedestrian comfort around two non-identical-height buildings in tandem arrangement: A wind tunnel study","volume":"262","author":"Li","year":"2024","journal-title":"Build. Environ."},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Zhou, P., Xie, Z., Zhou, W., and Tan, Z. (2023). A Heuristic Integrated Scheduling Algorithm Based on Improved Dijkstra Algorithm. Electronics, 12.","DOI":"10.3390\/electronics12204189"},{"key":"ref_50","first-page":"1624","article-title":"Evacuation Path Planning Based on Improved Dijkstra Algorithm in Metro Station Scene","volume":"20","author":"Zuo","year":"2023","journal-title":"J. Railw. Sci. Eng."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"1238","DOI":"10.1109\/TITS.2022.3216310","article-title":"T-PORP: A Trusted Parallel Route Planning Model on Dynamic Road Networks","volume":"24","author":"Li","year":"2023","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_52","first-page":"7588595","article-title":"Path Planning Algorithm for the Multiple Depot Vehicle Routing Problem Based on Parallel Clustering","volume":"2023","author":"Han","year":"2023","journal-title":"Sci. Program."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/14\/2\/71\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T16:30:12Z","timestamp":1760027412000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/14\/2\/71"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,10]]},"references-count":52,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,2]]}},"alternative-id":["ijgi14020071"],"URL":"https:\/\/doi.org\/10.3390\/ijgi14020071","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,10]]}}}