A math-heuristic for the warehouse location-routing problem in disaster relief

We consider a problem faced by international aid organizations after the occurrence of a natural disaster. A supply system with intermediate warehouses has to be established to provide affected people with relief goods. A three-objective optimization model with a medium-term economic, a short-term economic, and a humanitarian objective function is used. We apply the epsilon constraint method to determine the Pareto frontier. To solve the single-objective constrained optimization problem, we propose an exact solution method as well as a "math-heuristic" technique building on a MILP formulation with a heuristically generated constraint pool. As a subproblem, the multiple-depot, multiple-trip capacitated team orienteering problem is solved. We present a MIP formulation and a VNS procedure for this problem. Synthetically generated instances and a real-world illustration case are used for our computational studies. The results of the math-heuristic technique are compared to those obtained from an application of the NSGA-II metaheuristic and, where possible, to those of the exact solution approach. (C) 2011 Elsevier Ltd. All rights reserved.