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

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