A Bi-Objective MIP Model and a Hybrid Algorithm for Post-Disaster Connectivity Problem with Heterogeneous Vehicles

Some roads in the disaster area may be closed due to debris or collapse/deterioration after disasters. It is necessary to restore transportation as soon as possible for the evacuation of people, transportation to hospitals, or distribution of aid, by reconnecting the nodes where the connection is broken. Different types of vehicles may be needed to repair the edges depending on the type of damage. In this problem, it is essential to restore the edges to enable the complete connectivity of the network such that all nodes can be reached from one another. In addition, it is also to reach the critical nodes, such as hospitals, as soon as possible. We develop a multi-objective mathematical model for this problem, considering multiple vehicle types that can repair different types of damages. Since even the small-sized instances of this NP-hard problem require a long solution time, a heuristic method is also developed, and numerical results are presented