基于泰森图大规模MMTSP问题的高效求解  

Efficient solution of large⁃scale MMTSP problem based on Tyson graph

作　　者：张永亮 王家润[2] ZHANG Yongliang;WANG Jiarun(Alibaba Network Technology Co.,Ltd.,Beijing 100020,China;North China Institute of Computing Technology,Beijing 100083,China)

机构地区：[1]阿里巴巴网络技术有限公司,北京100020 [2]华北计算技术研究所,北京100083

出　　处：《测绘通报》2023年第3期165-172,共8页Bulletin of Surveying and Mapping

基　　金：基础加强重点专项计划(2020JCJQZD01412)。

摘　　要：针对大规模MMTSP问题任务划分不均匀与计算效率低的问题,本文提出了基于泰森图的高效基本计算框架。首先基于离散点上下凸包算法快速构造泰森图;然后基于高端点去除法快速完成MMTSP问题的任务划分;最后结合模拟退火算法求解单旅行商问题,完成大规模MMTSP问题的高效求解。为进一步提升计算效率,对该框架中的部分环节基于GPU的众核算力,提出了GPU并行加速计算时任务的划分设计,结合软件层面提出了软硬件协同加速计算框架。试验证明,本文算法在加速优化与任务划分均衡性上具备较大优势,其计算结果与计算效率均优于其他两类算法,软硬件协同加速优化后,可进一步提高约10倍的效率。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.

关 键 词：大规模MMTSP 快速构造泰森图 高端点去除法 任务划分均衡 软硬件协同 

分 类 号：P208[天文地球—地图制图学与地理信息工程]