Autonomous vehicle dispatching for person evacuation

The rapid development of Autonomous Vehicle (AV) technologies provides a new opportunity to evacuate vulnerable persons from their residences to shelters when some emergency event happens. One of the most important objectives is to minimize the evacuation time, which depends on the order to evacuate persons and which shelter each person is delivered to. We first formulate this AV dispatching problem as an Integer Linear Programming (ILP) model and prove this problem is NP-hard. Due to the problem hardness, an efficient algorithm based on Dynamical Programming (DP) is proposed. Through extensive simulations, we find that our algorithm can reduce the evacuation time by 58% compared with a greedy based algorithm, which is the common method to solve the Traveling Salesman Problem (TSP), a special case of our AV dispatching problem.