Cooperative Multiple Agent-Based Algorithm for Evacuation Planning for Victims with Different Urgencies

摘要

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 at multiple locations, and multiple safe locations (for example, hospitals and refuges). In our previous work, the problem was formulated as integer linear programming to provide optimal solution. Because the integer linear programming, however, is intractable for a large-scale disaster problem, a heuristic method called the cooperative multiagent-based 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. The computational efficiency and the performance of the algorithm are demonstrated using illustrative numerical examples based on realistic data.