GPU-enabled Evolutionary Dynamic Programming for Rapid Route and Rescue Planning for First Responders

Rapid and reliable route planning is of paramount significance for first responders to respond to emergent situations promptly, hence minimizing damages and casualties. This paper presents a new GPU-enabled evolutionary dynamic programming (EDP) algorithm designed for rapid multi-source route and rescue planning, addressing the urgent need for real-time decision-making for first responders. It considers potential delays caused by unexpected railroad crossing blockages in densely populated metropolitan areas by incorporating real-time traffic information to identify an optimal route with the shortest response time during emergencies. Specifically, the EDP allows effective utilization of massive GPU computing threads for rapid and accurate pathfinding subject to train blockage constraints. A new method for GPU resource allocation at the structural level is also proposed, which constructs GPU threads as two-dimensional blocks to enable efficient route computation between a starting node and any nodes within the road network. The performance of our method is validated through case studies involving multiple emergency scenarios in the City of Columbia, SC. The results demonstrate that the method can find the optimal route with train blockage constraints within 1 second, a significant improvement over our prior method (Wu et al., 2024). This research has the potential to significantly enhance emergency response efficiency, enabling first responders to navigate urban environments with unprecedented speed and reliability.