GREAT-EER: Graph Edge Attention Network for Emergency Evacuation Responses
This addresses the need for effective and fast evacuation planning in urban areas during emergencies, though it is incremental as it builds on existing graph learning and reinforcement learning techniques for a specific domain problem.
The authors tackled the Bus Evacuation Orienteering Problem (BEOP), an NP-hard optimization for evacuating people by bus in urban emergencies, by proposing a deep reinforcement learning method with graph learning that achieves near-optimal solution quality and fast inference in fractions of seconds, validated on real-world San Francisco scenarios.
Emergency situations that require the evacuation of urban areas can arise from man-made causes (e.g., terrorist attacks or industrial accidents) or natural disasters, the latter becoming more frequent due to climate change. As a result, effective and fast methods to develop evacuation plans are of great importance. In this work, we identify and propose the Bus Evacuation Orienteering Problem (BEOP), an NP-hard combinatorial optimization problem with the goal of evacuating as many people from an affected area by bus in a short, predefined amount of time. The purpose of bus-based evacuation is to reduce congestion and disorder that arises in purely car-focused evacuation scenarios. To solve the BEOP, we propose a deep reinforcement learning-based method utilizing graph learning, which, once trained, achieves fast inference speed and is able to create evacuation routes in fractions of seconds. We can bound the gap of our evacuation plans using an MILP formulation. To validate our method, we create evacuation scenarios for San Francisco using real-world road networks and travel times. We show that we achieve near-optimal solution quality and are further able to investigate how many evacuation vehicles are necessary to achieve certain bus-based evacuation quotas given a predefined evacuation time while keeping run time adequate.