关键词: 运筹学, 应急救援物资配送, 近似算法, 车辆路径

Abstract: For the practical case that the total amount of emergency relief supplies is scarce and can not meet the demand of all points, minimum the maximum shortage of each demand point, a emergency relief supply dispatching vehicle routing model based on one distribution center, limited amount of vehicles and time windows is established, and analyze the solutions of the model for three different cases of shortages. For the case that shortages result in vehicles can not reach demand points within rescue time requirement even go along the shortest path, after deleting the demand of this kind of demand points, if the total demand of remaining demand points is not bigger than the amount of emergency relief supplies, and with enough vehicles, this problem can be transformed into shortest path problem and solved. For the case that shortages result in the total amount of emergency relief supplies is scarce and can not meet the demand of all points even with enough vehicles, exact algorithm A^* is designed, and show that the time complexity is, where m and n denote the number of vehicles and demand points, respectively. For the case that shortages result in the total amount of emergency relief supplies is scarce and the amount of vehicles is inadequate that can not dispatch all the supplies to demand points, approximation algorithm GA* is designed, show that the time complexity is, and analyze the approximation ratio of algorithm GA^*. Take the local network of Yiliang earthquake disaster area in Yunnan as an example, confirm the model and algorithms are effective.

Key words: operational research, emergency relief supply dispatching, approximation algorithm, vehicle routing