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

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