Search papers, labs, and topics across Lattice.
The paper introduces the Bus Evacuation Orienteering Problem (BEOP) for optimizing bus-based urban evacuations, aiming to maximize the number of evacuees within a time limit. They propose a deep reinforcement learning approach using a Graph Edge Attention Network (GREAT-EER) to solve the NP-hard BEOP, enabling fast inference for route generation. Experimental results on San Francisco road networks demonstrate near-optimal solution quality and the ability to analyze vehicle requirements for evacuation quotas.
Ditch gridlock: a graph-based deep RL agent can generate near-optimal bus evacuation plans for cities in seconds.
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.
