高级检索

    寿涛, 刘朝晖. 基于Delaunay三角剖分处理二维欧式空间MTSP的近似算法[J]. 华东理工大学学报（自然科学版）, 2017, (6): 895-898. DOI: 10.14135/j.cnki.1006-3080.2017.06.022
    引用本文: 寿涛, 刘朝晖. 基于Delaunay三角剖分处理二维欧式空间MTSP的近似算法[J]. 华东理工大学学报（自然科学版）, 2017, (6): 895-898. DOI: 10.14135/j.cnki.1006-3080.2017.06.022
    shu
    SHOU Tao, LIU Zhao-hui. Approximate Algorithm of MTSP on 2D Euclidean Space with Delaunay Triangulation[J]. Journal of East China University of Science and Technology, 2017, (6): 895-898. DOI: 10.14135/j.cnki.1006-3080.2017.06.022
    Citation: SHOU Tao, LIU Zhao-hui. Approximate Algorithm of MTSP on 2D Euclidean Space with Delaunay Triangulation[J]. Journal of East China University of Science and Technology, 2017, (6): 895-898. DOI: 10.14135/j.cnki.1006-3080.2017.06.022
    shu

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

    Approximate Algorithm of MTSP on 2D Euclidean Space with Delaunay Triangulation

      摘要
    • 摘要: 考虑了在二维欧式平面内的多旅行商问题，通过Delaunay三角剖分的方法，将问题转化为求解多个旅行商问题。树分解算法的核心是Delaunay边的空圆性质并且可以证明该算法的近似比为2。最后，通过数值模拟验证了算法的有效性。

       

      Abstract: 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.

       

      • HTML全文
      • 参考文献(16)
      • 相关文章
      • 施引文献
    • 资源附件(0)

    /

    返回文章
    返回