Optimization Based Method for Supply Location Selection and Routing in Large-Scale Emergency Material Delivery

被引:38
作者
Han, Yunjun [1 ,2 ]
Guan, Xiaohong [1 ,3 ,4 ]
Shi, Leyuan [1 ,5 ]
机构
[1] Tsinghua Univ, Dept Automat, NLIST, Ctr Intelligent & Networked Syst, Beijing 100084, Peoples R China
[2] Marine Dev Ctr China, Beijing 100161, Peoples R China
[3] Xi An Jiao Tong Univ, SKLMS Lab, Xian 710049, Peoples R China
[4] Xi An Jiao Tong Univ, MOE KLINNS Lab, Xian 710049, Peoples R China
[5] Univ Wisconsin, Dept Ind Engn, Madison, WI 53706 USA
关键词
Emergency supply; Lagrangian relaxation (LR); location selection; scheduling; FACILITY LOCATION; RESOURCE-ALLOCATION; LOGISTICS; MODEL; ALGORITHM; TRANSMISSION; CONSTRAINTS; EVACUATION; FRAMEWORK;
D O I
10.1109/TASE.2011.2159838
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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.
引用
收藏
页码:683 / 693
页数:11
相关论文
共 49 条
[1]  
Agarwal N., P 2007 IND ENG RES C
[2]  
Ahuja R., 1993, NETWORK FLOWS THEORY
[3]   OR/MS research in disaster operations management [J].
Altay, Nezih ;
Green, Walter G., III .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 175 (01) :475-493
[4]  
[Anonymous], 1999, Athena scientific Belmont
[5]   Facility location in humanitarian relief [J].
Balcik, B. ;
Beamon, B. M. .
INTERNATIONAL JOURNAL OF LOGISTICS-RESEARCH AND APPLICATIONS, 2008, 11 (02) :101-121
[6]   A two-stage stochastic programming framework for transportation planning in disaster response [J].
Barbarosoglu, G ;
Arda, Y .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2004, 55 (01) :43-53
[7]   An interactive approach for hierarchical analysis of helicopter logistics in disaster relief operations [J].
Barbarosoglu, G ;
Özdamar, L ;
Çevik, A .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2002, 140 (01) :118-133
[8]   DAILY GENERATION SCHEDULING OPTIMIZATION WITH TRANSMISSION CONSTRAINTS - A NEW CLASS OF ALGORITHMS [J].
BATUT, J ;
RENAUD, A .
IEEE TRANSACTIONS ON POWER SYSTEMS, 1992, 7 (03) :982-989
[9]  
Black P., 2004, DICT ALGORITHMS DATA
[10]   A scenario planning approach for the flood emergency logistics preparation problem under uncertainty [J].
Chang, Mei-Shiang ;
Tseng, Ya-Ling ;
Chen, Jing-Wen .
TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW, 2007, 43 (06) :737-754