A Conflict-Based Path-Generation Heuristic for Evacuation Planning
Evacuation planning and scheduling is a critical aspect of disaster management and national security applications. This paper proposes a conflict-based path-generation approach for evacuation planning. Its key idea is to generate evacuation routes lazily for evacuated areas and to optimize the evacuation over these routes in a master problem. Each new path is generated to remedy conflicts in the evacuation and adds new columns and a new row in the master problem. The algorithm is applied to massive flood scenarios in the Hawkesbury-Nepean river (West Sydney, Australia) which require evacuating in the order of 70,000 persons. The proposed approach reduces the number of variables from 4,500,000 in a Mixed Integer Programming (MIP) formulation to 30,000 in the case study. With this approach, realistic evacuations scenarios can be solved near-optimally in real time, supporting both evacuation planning in strategic, tactical, and operational environments.
Code (0)
등록된 구현이 없습니다.
Tasks
ManagementSchedulingSimilar Papers 제목 키워드 기반
Digital Simulations to Enhance Military Medical Evacuation Decision-Making
Medical evacuation is one of the United States Army's most storied and critical mission sets, responsible for efficiently and expediently evacuating the battlefield ill and injured. Medical evacuation planning involves d…
Simulation-Assisted Optimization for Large-Scale Evacuation Planning with Congestion-Dependent Delays
Evacuation planning is a crucial part of disaster management. However, joint optimization of its two essential components, routing and scheduling, with objectives such as minimizing average evacuation time or evacuation …
Heuristic SearchManagementSchedulingMulti-Robot Path Planning Combining Heuristics and Multi-Agent Reinforcement Learning
Multi-robot path finding in dynamic environments is a highly challenging classic problem. In the movement process, robots need to avoid collisions with other moving robots while minimizing their travel distance. Previous…
Collision AvoidanceHeuristic SearchMulti-agent Reinforcement Learningreinforcement-learningConflict-Free Four-Dimensional Path Planning for Urban Air Mobility Considering Airspace Occupations
Urban air mobility (UAM) has attracted the attention of aircraft manufacturers, air navigation service providers and governments in recent years. Preventing the conflict among urban aircraft is crucial to UAM traffic saf…
ManagementCongestion-aware Evacuation Routing using Augmented Reality Devices
We present a congestion-aware routing solution for indoor evacuation, which produces real-time individual-customized evacuation routes among multiple destinations while keeping tracks of all evacuees' locations. A popula…