Simultaneous planning for disaster road clearance and distribution of relief goods: a basic model and an exact solution method

In recent years, more and more disasters occurred. Additionally, the amount of people affected by disasters increased. Because of this, it is of great importance to perform the relief operations efficiently in order to alleviate the suffering of the disaster victims. Immediately after the occurrence of a disaster, there is an urgent need for delivering relief goods to demand locations and affected regions, respectively. Due to roads being blocked or damaged by debris, some demand locations may be out of reach and therefore the delivery of relief goods is hampered. This paper investigates the basic problem of simultaneously unblocking roads in order to make demand locations accessible and delivering relief goods in order to satisfy demand. Strict deadlines for the delivery of relief goods are considered at the demand locations. A formal problem statement is provided, and its computational complexity is analyzed. Additionally, a mixed integer programming model is developed and an exact solution method based on a branch and bound approach is proposed. A computational study investigating the performance of the model formulation and the branch and bound algorithm is conducted.