Abstract: Aiming at the problem of uneven task division and low computational efficiency in large-scale MMTSP,An efficient computational framework based on Tyson digram is proposed.Firstly,based on the proposed upper and lower convex hull alg orithm of discrete points,the Tyson digram is constructed quickly. Secondly,based on the proposed high point ignored method,the task division of MMTSP is completed quickly. Finally,the simulated annealing algorithm for sin gle TSP is used to sovle the large-scale MMTSP problem efficiently.To further improve the efficiency,some parts of the framework are based on GPU,So the task partition design of GPU parallel accelerated computing is proposed. Combine with software level a framework of software and hardware coaccelerated computing is proposed.Experiments show that,this algorithm has great advantages in accelerating optimization and balancing task division,the calculation results and efficiency are better than other two algorithms, after software and hardware coacceleration,the efficiency can be further increased by about 10 times.

Key words: large-scale MMTSP, fast construction Tyson graph, high point ignored, uniform task division, hardware and software coordination