A Hybrid Heuristic Algorithm for a Bi-Objective Problem in Humanitarian Relief Transportation

Natural disasters are abrupt events and have extended effects on vast areas. Due to these features, decision making and crisis management are complicated tasks. In this situation, hasty decisions may cause immense waste of organizational and national resources and drop in quality of services. This study provides a model to optimize emergency services with regard to two objectives, namely 1) maximizing the total satisfied demand of customers, and 2) minimizing the cost of emergency services (i.e., time or distance). One of the practical assumptions of this problem is using the covering idea to provide the customers demand in case of unavailability of communication paths to the customers. Essentially, the demand of each customer can be satisfied by directly visiting it on a vehicle route or it can be covered by other visited customers located within a given pre-specified distance of it. We propose a node-based mathematical formulation. Moreover, to obtain the Pareto frontier, we present a hybrid bi-objective heuristic algorithm by combining the adaptive large neighborhood search (ALNS) and multi-directional local search (MDLS) algorithms. The performance of the proposed algorithm is tested on a set of 72 randomly generated instances. Computational results indicate the effectiveness of the proposed algorithm.