Conflict-Free Evacuation Route Planning

Given a transportation network, a population, and a set of destinations, the goal of Conflict-Free Evacuation Route Planning (CF-ERP) is to produce routes that minimize the evacuation time for the population with no spatiotemporal movement-conflicts. The CF-ERP problem is an essential component of civic emergency preparedness in the wake of man-made or natural disasters (e.g., terrorist acts, hurricanes, or nuclear accidents). This problem is challenging because of the large size of network data, the large number of evacuees, and the need to account for capacity constraints and the conflict-free constraint. Previous work has focused on minimizing the evacuation time on spatiotemporal networks. However, these approaches cannot minimize potential movement-conflicts that cause traffic accidents, congestion, and delays. We propose novel approaches for CF-ERP to meet the conflict-free constraint while minimizing the evacuation time for the population. Experiments using real-world datasets demonstrate that the proposed algorithms produce evacuation routes with no movement-conflicts and have comparable solution quality to related work.