Research On Vehicle Routing For Scarce Emergency Relief Supplies Distribution

The emergency rescue after sudden disasters is a focus of the society. Previous studies have made great achievements, one assumes the amount of supplies can satisfy all the demand points, however, during the short time after disasters, the emergency relief supplies must be scarce, can not meet the demand of all points. Others assume the amount of supplies is scarce, and minimum the total unmet demand of all demand points, give the vehicle routing plans. But, if consider only that minimum the total unmet demand of all demand points, but ignore the unmet demands of each point, some demand points may get little supplies even none. This will cause adverse effect to the rescue operation.Thus, minimum the maximum unmet demand of each demand point, study the vehicle routing for scarce emergency relief supplies distribution, have important theoretical significance and practical value. The major work and innovative achievements of this paper are as follows.For the situation that the amount of emergency relief supplies is scarce which can not meet the total demand, minimum the maximum unmet demand of each demand point, a vehicle routing model based on one depot, rescue time windows and limited vehicles is established, analyze the solutions for the model under three different cases of unmet demand. For the case that vehicles can not reach some demand points within rescue time windows even go along the shortest paths, delete the demands and rescue time windows of these demand points, transform this problem into shortest path problem and solve if the total demand of remaining demand points is not bigger than the amount of supplies with enough vehicles. Exact algorithm A*is designed for the case that the amount of supplies is scarce which can not meet total demand even with enough vehicles, show that the time complexity is O(ln2), where l and n denote the number of vehicles and demand points, respectively. Approximation algorithm GA*is designed for the case that the amount of supplies is scarce and with insufficient vehicles which can not distribute all supplies, show that the time complexity is O(n2), where n denote the number of demand points, and analyze the approximation ratio. If the demands of each demand point are nearly the same and the total demand is far higher than the supplies, the approximation ratio level off to1. Take the local network of Yushu earthquake disaster area in Qinghai as an example, the result shows that the model and algorithm can avoid the situation that some demand points get only little supplies even none effectively.For the situation that the amount of emergency relief supplies is scarce which can not meet the total demand, minimum the maximum unmet demand of each demand point, a vehicle routing model based on multi-depots, rescue time windows and limited vehicles is established. Combine with the travel times of shortest paths between distribution depots and demand points, the numbers of vehicles and amounts of supplies of each distribution depot, the cases of unmet demand are summarized, and analyze the solutions for the model under different cases. For the case that vehicles from all distribution depots can not reach some demand points within rescue time windows even go along the shortest paths, delete the demands and rescue time windows of these demand points. Exact algorithm MDA*is designed for the case that the amount of supplies is scarce which can not meet total demand with enough vehicles, show that the time complexity is O(l(m+n)2), where m, n, l denote the number of depots, demand points and vehicles, respectively. Approximation algorithm MDGA*is designed for the case that the amount of supplies is scarce and with insufficient vehicles which can not distribute all supplies, show that the time complexity is O(l(m+n)2), where m, n, l denote the number of depots, demand points and vehicles, respectively, and analyze the approximation ratio. If the demands of each demand point are nearly the same and the total demand is far higher than the supplies, the approximation ratio level off to1. Take the local network of Yushu earthquake disaster area in Qinghai as an example, contrast the result with the situation of single distribution depot, and show that the maximum unmet demand of each demand point will drop with more than one distribution depot. Take the local network of Ya’an earthquake disaster area in Sichuan as an example, show that the model and algorithm can avoid the situation that some demand points get only little supplies even none effectively.