文献类型：期刊文献

中文题名：基于Delaunay三角剖分处理二维欧式空间MTSP的近似算法

英文题名：Approximate Algorithm of MTSP on 2D Euclidean Space with Delaunay Triangulation

作者：寿涛[1];刘朝晖[1]

机构：[1]华东理工大学数学系,上海200237

年份：2017

卷号：43

期号：6

起止页码：895

中文期刊名：华东理工大学学报（自然科学版）

外文期刊名：Journal of East China University of Science and Technology

收录：北大核心:【北大核心2014】；CSCD:【CSCD_E2017_2018】；

语种：中文

中文关键词：MTSP;Delaunay三角剖分;近似算法

外文关键词：MTSP;Delaunay triangulation;approximate algorithm

摘要：考虑了在二维欧式平面内的多旅行商问题,通过Delaunay三角剖分的方法,将问题转化为求解多个旅行商问题。树分解算法的核心是Delaunay边的空圆性质并且可以证明该算法的近似比为2。最后,通过数值模拟验证了算法的有效性。
This paper discussed Multi Travelling Salesman Problem(MTSP)on 2D Euclidean space.This problem could be simplified to solve several TSP by Delaunay Triangulation.It could be proven that the approximate ratio of Tree Decomposed Algorithm was 2 and the core proof was based on empty circle property of Delaunay edge.The paper testified the performance and efficiency of the algorithm by some numerical examples.