Approximation Algorithm For MTSP Based On 2-dimension Euclidean Space

Delauany Triangulation is one of useful means for spatial clustering.This paper would discuss the Multi Travelling Salesman Problem on 2-dimension Euclidean space.Tree Decomposed Algorithm is based on Delauany Triangulation,Minimal Spanning Tree Algorithm and Double Tree Algorithm.From the theoretical analysis,it could be proven that the approximation ratio of Tree Decomposed Algorithm is 2 and its complexity is O(nlogn).In the part of simulation,we take the part into two sections.Firstly,to contrast the performance with Zhou xu and others'(2-1/k)algorithm,the result of Tree Decomposed Algorithm is better than Zhou xu and others' on the same instance.Secondly,several instances in TSPLIB were presented to test the difference between Tree Decomposed Algorithm and Rathinam and others'2 approximation ratio algorithm.As the result,we conclude that as the scale is getting bigger,the performance gap between Tree Decomposed Algorithm and Rathinam and others' algorithm gets wider,too.And the accuracy of Tree Decomposed Algorithm's solution is 10%better than Rathinam's.In the last section of application,we choose the logistics route of YiGuo.com as the instance.From the mathematical model,we could find the route generated by Tree Decomposed Algorithm is 8%better than the conventional route.