震后应急物流系统中双目标开放式选址:路径问题模型与算法研究

Model and Algorithms for Integrated Open Location and Routing Problem in Emergency Logistics under Earthquake

灾害发生后,应急物资调度是救援工作核心。应急配送中心选址以及车辆路径安排在应急物资调度中仍然有很大的挑战。本文以平均车辆运输时间最小化和系统总成本最小化为目标,建立了基于多车型、双目标的开放式选址-路径问题混合整数规划模型。采用基于非支配解排序的遗传算法求解,得出包括若干非支配解的Pareto最优解集,为决策者提供多样化选择。最后以"汶川"地震为实例进行研究,结果论证了该模型与算法的有效性以及在实践中的可行性。

Earthquakes have already been major fatal disasters that threaten humankind＇s life. Rescue efforts can reduce the impact of damage after an earthquake occurs. Distribution of relief goods is the focus of rescue work. Emergency managers need to find an optimal schedule for distributing relief to disaster areas with limited time and funds. The location of distribution centers and routes scheduling of vehicles are vital to the relief items distribution, which remains challenging in emergency logistics research and related fields.In this paper we focus on the coordination of location of distribution centers（DCs） and vehicle routes scheduling for distributing relief items to disaster areas efficiently. The problem can be classified as an integrated open location-routing problem（OLRP） with bi-objective. In emergency logistics, with higher uncertainty and dynamic the former DC may not work in the next order in OLRP. Each dispatching vehicle stays at the last disaster areas it serves without returning to DC until the next mission is received. With large demand for relief items in disaster areas after earthquake, the capacity of vehicles may not be enough for fulfillment. Thus, disaster areas can be served more than once. This is called split delivery, which is a big feature from typical vehicle routing problem. It makes the research problem more realistic. In the first part, we review literature on relief items distribution in emergency logistics. There is a lack of studies on the design of mathematical models and solution algorithms for OLRP in a post-disaster situation. In the second part, we describe the bi-objective OLRP in emergency logistics. Sleeping bags and water are relief items mainly considered in this study. The relief items are considered for one day needed by disaster areas. Split deliveries are required once the demands of disaster area break the capacity of the serving vehicle. Two objectives are considered：（1） minimizing the average vehicle route time, and（2） minimizing the total cost, including the fixed establishing costs of DCs and the vehicle travelling cost. Objective（1） and（2） are conflict with each other. In the test instance section, we take this fact into account by considering the two objectives simultaneously. Mixed integer programming mathematic models of OLRP are presented. In the third part, Non-dominated Sorting Genetic Algorithm（NSGA-II） is designed to solve the bi-objective model. Series of sets solutions called generations are computed by NSGA-II. Each generation consists of several individuals called chromosomes. Each chromosome denotes one strategy for relief distribution. Fast-Non-Dominated-Sort and Crowding-Density–Sort are used to select the elites into the offspring, which can guarantee the convergence and diversity of Pareto optimal solutions. In the fourth part, ‘Wenchuan earthquake＇ is conducted to illustrate the efficiency and potential advantages of the proposed method. The approximate optimal DC location and vehicles scheduling according to the above two objectives（minimize the average route travelling time and the total cost） are given. The results show that DC location and vehicle scheduling depend on each other. To minimize the average vehicle travelling time, more DCs are located, and vehicles with higher normal velocity are chosen. The higher normal velocity, the higher cost per kilometers the vehicles are. Thus, the total cost including the fixed location cost and vehicle travelling cost will increase. In contrary, to minimize the total cost fewer DCs are open and vehicles with lower cost per unit of travelling are scheduled. The solutions will support decision makers to direct the distribution of relief items under adverse conditions. Comparisons are made between NSGA-II and Multi-Objective Scatter Search（MOSS） algorithm. The results have shown that the approximate Pareto optimal solutions obtained by NSGA-II dominate most of all the solutions obtained by MOSS, which verifies the strengths of the NSGA-II in solving multi-objective problems. This provides a profound basis to extend our method to more realistic assumptions. Finally, it is expected that the proposed relief items distribution approach can improve the performance of emergency logistics managements. In the next step, multi-periods OLRP will be considered.