An Efficient Route Planning Algorithm for Special Vehicles with Large-Scale Road Network Data

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.