Optimization based method for supply location selection and routing in large-scale emergency material delivery

Timely supply of vital materials to disaster hit areas plays a critical role in emergency relief. The problem involves warehouse selection, fleet routing, and scheduling so as to meet demand in the strict time window. The problem is NP-hard, in general, and extremely difficult to solve. The congestion caused by heavy traffic further aggravates the problem. To obtain a scalable solution, a new method based on successive subproblem solving in Lagrangian Relaxation (LR) framework is developed. The route capacity and location selection constraints are relaxed by Lagrange multipliers, and the problem is converted into a two-level optimization problem. The subproblems at the lower level are solved successively in dual iterations with convergence assurance so that the indecomposable location constraints can be incorporated. A systematic method is developed to obtain a feasible solution by adding the once relaxed constraints back into the dual problem successively in feasibility iterations. Convergence proof of the new method and its properties are presented. Numerical results show that the new method is effective and efficient, and can be applied to large-scale problems.