Evacuation planning is a critical aspect of disaster preparedness and response to minimize the number of people exposed to a threat. Controlled evacuations aim at managing the flow of evacuees as efficiently as possible and have been shown to produce significant benefits compared to self-evacuations. However, existing approaches do not capture the delays introduced by diverging and crossing evacuation routes, although evidence from actual evacuations highlights that these can lead to significant congestion. This paper introduces the concept of convergent evacuation plans to tackle this issue. It presents a MIP model to obtain optimal convergent evacuation plans which, unfortunately, does not scale to realistic instances. The paper then proposes a two-stage approach that separates the route design and the evacuation scheduling. Experimental results on a real case study show that the two-stage approach produces better primal bounds than the MIP model and is two orders of magnitude faster; It also produces dual bounds stronger than the linear relaxation of the MIP model. Finally, simulations of the evacuation demonstrate that convergent evacuation plans outperform existing approaches for realistic driver behaviors.

Evacuations are a critical aspect of disaster management, and generally the first prevention measure to ensure the safety of the population under threat. Designing evacuation plans is a complex task that requires to take into account multiple factors in order to limit congestion and ensure that all evacuees reach safety in time. This paper proposes a conflict-based path-generation algorithm for evacuation planning and a web-based intelligent system targeted at local authorities and emergency services. The key contribution of this paper is to propose the first scalable approach to produce actionable evacuation plans that simultaneously schedules the evacuation and selects contraflow roads. The benefits of the approach are illustrated on two large-scale case studies. The resulting optimization model is integrated in NICTA EVACUATION PLANNER, a tool to model, plan, and simulate evacuations.