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 in-decomposable 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. Note to Practitioners-The motivation of our paper is to simultaneously resolve the warehouse selection/location and the fleet routing and scheduling problem for emergency material delivery. Currently, most research work reported in the literatures for emergency material supply problem focuses on either location-allocation problem or fleet routing and scheduling problem. In many practical applications, these two types of problems have to be synergistically considered and solved for timely material delivery. Since the problem is NP-hard, it is extremely difficult to solve by general integer programming methods. A new method based on the successive subproblem solving scheme is developed to solve this problem. The near optimal solution is obtained systematically by adding the once relaxed constraints back into the dual problem successively in feasibility iterations with convergence proof. The numerical testing results show that the new method can solve large-scale problems with satisfactory duality gaps and is much more efficient than general integer programming methods.