Research On Vehicle Routing Problem Of Emergency Materials Considering Demand Utility

The study of emergency supplies distribution path selection after a sudden disaster has significant theoretical meaning and practical sense.This thesis takes into account that the demand utility of emergency materials at each demand point changes with the increase of the distribution volume of emergency materials per unit,construct a nonlinear utility function to measure the demand utility of obtaining emergency materials at a single demand point,and study the distribution path selection problem of emergency materials with the goal of maximizing the sum of demand utility of obtaining emergency materials at all demand points and minimizing the distance traveled by vehicles.The main work is as follows.A single distribution center emergency material distribution path selection considering demand utility.A vehicle selection model for emergency material distribution is constructed with the goal of maximizing the sum of the demand utility of emergency materials obtained by all demand points and the shortest vehicle driving distance.Comparing the maximum cargo capacity of the delivery vehicle and the point of requirement,it is discussed in three different situations and an algorithm is designed to solve it.When the distribution vehicles are insufficient and the demand at each demand point is smaller than the highest capacity of the vehicle,A1 is devised and the temporal complexity of the algorithm is justified to beO(ln2);When the distribution vehicles are insufficient and the demand at each demand point is greater than the maximum load of the distribution vehicle,the algorithm A2 is devised and the temporal complexity of the algorithm is justified to be O(ln2);When the distribution vehicles are insufficient and the demand at each demand point is greater than,less than or equal to the maximum load of the distribution vehicle,the algorithm A3 is designed and the time complexity of the algorithm is proved to be O(ln2).At the end,the effectiveness of the model and algorithm is demonstrated by taking the actual distribution of emergency supplies in local disaster areas in Jiuzhaigou earthquake area as an example.Model and solution of emergency material distribution path selection in m distribution centers considering demand utility.Aiming at the maximum sum of the demand utility of all the demand points to obtain emergency materials and the shortest vehicle travel distance,a model for the selection of emergency materials distribution routes is constructed.According to the sufficient and insufficient number of vehicles in each distribution center,the model is discussed in three cases and an algorithm is devised to solve it.When the total amount of materials is insufficient and the number of vehicles in all distribution centers is sufficient,the algorithmEA is devised to prove that the time complexity of EA is O(l(m+n)2);when the total amount of materials is insufficient and the number of vehicles in all distribution centers is insufficient,evise the algorithm EA*,and verify that the time complexity of the algorithm EA*is O(l(m+n)2);when the total amount of materials is insufficient and the number of vehicles in all distribution centers is partially insufficient,devise the algorithm LNGA*,and verify that The time complexity of the algorithm LNGA*is O(l(m+n)2)and its approximation ratio is analyzed.At the last,the actual distribution of emergency supplies in Jiuzhaigou earthquake area is used as an example to verify the effectiveness of the m distribution centers emergency supplies distribution path selection model and algorithm LNGA*considering demand utility,and the approximation ratio of the algorithm LNGA*is 2.5,which indicates that the algorithm is used well in the example.