Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
476677 | European Journal of Operational Research | 2014 | 12 Pages |
•We model scheduling and assigning rescue units to incidents in disaster management.•A decision support model in a mixed integer non-linear formulation is proposed.•A catalog of construction and improvement heuristics as well as GRASP metaheuristics are computationally tested and evaluated.•Several results are close to optimal solutions and improve current best practice.
Natural disasters, such as earthquakes, tsunamis and hurricanes, cause tremendous harm each year. In order to reduce casualties and economic losses during the response phase, rescue units must be allocated and scheduled efficiently. As this problem is one of the key issues in emergency response and has been addressed only rarely in literature, this paper develops a corresponding decision support model that minimizes the sum of completion times of incidents weighted by their severity. The presented problem is a generalization of the parallel-machine scheduling problem with unrelated machines, non-batch sequence-dependent setup times and a weighted sum of completion times – thus, it is NP-hard. Using literature on scheduling and routing, we propose and computationally compare several heuristics, including a Monte Carlo-based heuristic, the joint application of 8 construction heuristics and 5 improvement heuristics, and GRASP metaheuristics. Our results show that problem instances (with up to 40 incidents and 40 rescue units) can be solved in less than a second, with results being at most 10.9% up to 33.9% higher than optimal values. Compared to current best practice solutions, the overall harm can be reduced by up to 81.8%.