Abstract: Emergency relief supply dispatching is an important issue after the sudden disaster. For the practical case that emergency rescue materials are in short supply and cannot meet the needs of all demand points, a multi-objective Two-Echelon emergency relief supply dispatching vehicle routing model which is the nonlinear programming model is built to find an optimal solution with the aim of minimizing both the maximum shortage of each demand point and total distribution cost. Then, an approximation algorithm GA is designed with the time complexity O(n3), the upper and lower bounder of the approximation ratio is analyzed and the approximation ratio is measured by instances. The approximation ratio which closes to 1 means that the approximation performance of the algorithm is better. Further, the influencing factors of the approximate ratio is analyzed, along with the finding that the more of the number of satellites, the supplies in the depot and the capacity of primary vehicles and secondary vehicles, the less of the number of customers, the better of the algorithm effectiveness. Finally, by comparing the results of the algorithm GA with the results of genetic algorithm, the effectiveness of the algorithm GA is proved.

Key words: Two-Echelon Vehicle Routing; approximation algorithms; emergency relief supply dispatching; optimization