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’s 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.

Off-road path planning involves navigating vehicles through areas lacking established road networks, which is critical for emergency response in disaster events, but is limited by the complex geographical environments in natural conditions. How to model the vehicle’s off-road mobility effectively and represent environments is critical for efficient path planning in off-road environments. This paper proposed an improved A* path planning algorithm based on a Delaunay triangular NavMesh model with off-road environment representation. Firstly, a land cover off-road mobility model is constructed to determine the navigable regions by quantifying the mobility of different geographical factors. This model maps passable areas by considering factors such as slope, elevation, and vegetation density and utilizes morphological operations to minimize mapping noise. Secondly, a Delaunay triangular NavMesh model is established to represent off-road environments. This mesh leverages Delaunay triangulation’s empty circle and maximum-minimum angle properties, which accurately represent irregular obstacles without compromising computational efficiency. Finally, an improved A* path planning algorithm is developed to find the optimal off-road mobility path from a start point to an end point, and identify a path triangle chain with which to calculate the shortest path. The improved road-off path planning A* algorithm proposed in this paper, based on the Delaunay triangulation navigation mesh, uses the Euclidean distance between the midpoint of the input edge and the midpoint of the output edge as the cost function $g\left(n\right)$, and the Euclidean distance between the centroids of the current triangle and the goal as the heuristic function $h\left(n\right)$. Considering that the improved road-off path planning A* algorithm could identify a chain of path triangles for calculating the shortest path, the funnel algorithm was then introduced to transform the path planning problem into a dynamic geometric problem, iteratively approximating the optimal path by maintaining an evolving funnel region, obtaining a shortest path closer to the Euclidean shortest path. Research results indicate that the proposed algorithms yield optimal path-planning results in terms of both time and distance. The navigation mesh-based path planning algorithm saves 5~20% of path length than hexagonal and 8-directional grid algorithms used widely in previous research by using only 1~60% of the original data loading. In general, the path planning algorithm is based on a national-level navigation mesh model, validated at the national scale through four cases representing typical natural and social landscapes in China. Although the algorithms are currently constrained by the limited data accessibility reflecting real-time transportation status, these findings highlight the generalizability and efficiency of the proposed off-road path-planning algorithm, which is useful for path-planning solutions for emergency operations, wilderness adventures, and mineral exploration.