Evacuation Planning

Cooperative Multiple Agent-Based (CMA) Algorithm for Evacuation Planning for Victims with Different Levels of Urgency

A well-organized evacuation plan is crucial to save more lives in the aftermath of natural disasters. In this paper, a mathematical model and an efficient solution approach are proposed for optimal planning of a fleet of aerial vehicles to save victims with different levels of urgency.

Evacuation planning is a task assignment problem combined with scheduling of aerial vehicles with different capabilities while considering complex conditions such as:

  • multiple bases for the vehicles,
  • victims with different urgency levels (immediate: require cares within 2 hours; delayed: within 6 hours; minimal: within 12 hours) at multiple locations, and
  • multiple safe locations (for example, hospitals and refuges).

Evacuation process at the initial phase of the disaster response

Example of an evacuation planning problem

In our previous work, the problem was formulated as integer linear programming (ILP) to provide optimal solution. Because the ILP, however, is intractable for a large-scale disaster problem, a heuristic method called the cooperative multiple agent-based (CMA) algorithm is proposed to solve the large-scale problem in practical time.

  • The proposed algorithm defines simple rules for vehicle agents and demand agents (victims), and
  • it applies cooperative interaction between agents to efficiently find a suboptimal solution.

Structure of the cooperative multiple agent-based (CMA) algorithm

The computational efficiency and the performance of the algorithm are demonstrated using illustrative numerical examples based on realistic data.

  • Large-scale problem example
    • The total number of 2,153 victims (411 victims of immediate category, 562 victims of delayed category, and 562 victims of minimal category) located at 160 disaster sites
    • A fleet of 5 helicopters (one large, three medium, and one small), two bases, and three safe locations
  • Results (Please find the detailed results in the related publication)
    • Computation time: 10.322 s
    • Performance: 1,523 victims (70.74% of total number of victims) can be evacuated

Related Publication

  • B. Oh, K. Kim, H. Choi, and I. Hwang, “Cooperative Multi–Agent based Algorithm for Evacuation Planning for Victims with Different Urgency,” AIAA Journal of Aerospace Information Systems, Publication Date (online): February 19, 2018