Centrality Measures for Evacuation: Finding Agile Evacuation Routes

In this paper, we study the agility of evacuation routes in relation to dynamically changing unpredictable hazardous conditions in smart space networks. Infrastructure safety conditions may unpredictably change through time. Due to unpredictability, evacuees’ safety can get jeopardized at any point of the evacuation route. Thus, it is not sufficient only to find the shortest evacuation routes considering present safety conditions and evacuation flow, but we should also consider other relevant characteristics that make the evacuation routes sufficiently safe through time. With this aim, we propose two new node importance metrics: evacuation betweenness centrality and evacuation centrality, both inspired by betweenness centrality. The first metric represents the fraction of k efficient evacuation routes between all origin–destination pairs different from the given node that pass through that node, while the second represents the importance of the given node for evacuation considering the availability of alternative efficient evacuation paths (routes) from that node towards safe exits. Moreover, given a set of evacuees’ positions and safe exits, we find shortest agile evacuation routes, where by agile route we mean the ability to efficiently and safely reroute from intermediate nodes in case of unpredictable safety drops through maximizing the value of the evacuation centrality of the route’s intermediate nodes. In addition, we propose an algorithm for that problem and discuss its capability to react to the changes in safety circumstances along recommended routes.