Research On Two-Echelon Vehicle Routing For Emergency Relief Supply Dispatching

The research on two-echelon vehicle routing for emergency relief supply dispatching has great theoretical significance and practical value.Existing studies aim at minimizing the cost of total shortage,without considering the shortage of each customer which cause some customers only received few relief materials or even received no relief materials and considering that relief material supplies cannot finish the distribution in single cycle which require the situation of multi-cycle distribution.In this paper,we research on two-echelon vehicle routing for emergency relief within of single-cycle and two-cycle,and the objectives of this paper are minimizing the maximum cost for the shortage of relief materials at each customer and minimizing the total routing cost.The main innovative research results are as follows.Modeling and solving problem of two-echelon vehicle routing for emergency relief supply dispatching.Aiming to find minimizing the maximum cost for the shortage of relief materials at each customer and minimizing the total routing cost with the situation that relief material supplies cannot meet demand of all customers and relief materials can only distributing in single-cycle,we build the model of single-cycle two-echelon vehicle routing for emergency relief supply dispatching and design an approximate algorithm to solve the distribution and the routing.Time complexity of the algorithm GA is We analyze the upper and lower bound of approximate ratio of the algorithm and verify the value and influencing factors of approximation ratio by numerical experiment.The result shows that the maximum approximate ratio of the algorithm is 3.2 by given coordinate of depot,satellites and customers,the quantity of relief materials and the quantity of demands.The approximate ratio is smaller when the smaller of the number of customers and the quantity of relief materials in depot,the more of the number of satellites and the carrying capacity of vehicles.Finally,make an example analysis of Ya'an earthquake rescue road network,the approximation ratio of GA is 1.7 which shows that the approximate performance of the algorithm in the example is better.Modeling and solving problem of two-cycle two-echelon vehicle routing for emergency relief supply dispatching.Aiming to find minimizing the maximum cost for the shortage of relief materials at each customer and minimizing the total routing cost after second cycle with the situation that relief material supplies cannot meet demand of all customers and two types of relief materials can distributing in two-cycle,we build the model of two-cycle two-echelon vehicle routing for emergency relief supply dispatching and design an approximate algorithm GA*to solve the distribution and the routing.The time complexity of the algorithm GA is o(n3).We analyze the upper and lower bound of the approximate ratio of the algorithm and verify the value and influencing factors of approximation ratio by numerical experiment.The result shows that the maximum approximate ratio of the algorithm is 4 by given coordinate of depot,satellites and customers,the quantity of relief materials and demands in each cycle.The approximate ratio is smaller when the smaller of the quantity of relief materials ? in single cycle and the carrying capacity of primary vehicles,the more of the carrying capacity of secondly vehicles.Finally,make an example analysis of Ya'an earthquake rescue road network to verify the validity of model and algorithm,the approximation ratio of is 1.41 which shows that the approximate performance of the algorithm in the example is better.