高级检索

  • ISSN 1006-3080
  • CN 31-1691/TQ

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

寿涛 刘朝晖

寿涛, 刘朝晖. 基于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
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

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

doi: 10.14135/j.cnki.1006-3080.2017.06.022

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

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

     

  • [1] GAREY M R,JOHNSON D S.Computers and Intractability:A Guide to the Theory of NP-Completeness[M].New York:W.H.Freeman,1979:206-218.
    [2] LI C L,SIMCHI-LEVI D.Worst-case analysis of heuristics for multidepot capacitated vehicle routing problems[J].Informs Journal on Computing,1990,2(1):64-73.
    [3] HARKS T,KONIG F G,MATUSCHKE J.Approximation algorithms for capacitated location routing[J].Transportation Science,2013,47(1):3-22.
    [4] RATHINAM S,SENGUPTA R,DARBHA S.A resource allocation algorithm for multivehicle systems with nonholonomic constraints[J].IEEE Transaction on Automation Science,2007,4(1):98-104.
    [5] MALIK W,RATHINAM S,DARBHA S.An approximation algorithm for a symmetric generalized multiple depot,multiple travelling salesman problem[J].Operations Research Letters,2007,35(6):747-753.
    [6] ROSENKRANTZ D J.An analysis of several heuristics for the traveling salesman problem[J].SIAM Journal of Computing,1977,6(3):563-581.
    [7] AARTS E,LEBSTRA J.Local search in combinatorial optimization[D].USA:Princeton University Press,2003.
    [8] ANGEL E.A survey of approximation results for local search algorithms[M].Heidelberg:Springer,1970:30-73.
    [9] XU Z,XU L,RODRIGUES B.An analysis of the extended Christofides heuristic for the k-depot TSP[J].Operations Research Letters,2011,39(3):218-223.
    [10] CHRISTOFIDES N.Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem[D].USA:Carnegie Mellon University,1976.
    [11] 徐永安,杨钦,吴壮志,等.三维约束Delaunay三角化的实现[J].软件学报,2001,12(1):103-110.
    [12] JOE B.Delaunay versus max-min solid angle triangulations for three dimensional mesh generation[J].International Journal of Numerical Methods in Engineering,1991,31(5):987-997.
    [13] DE BERG M,VAN KREVELD M,OVERMARS M.Computational geometry:Algorithms and applications[J].Computational Geometry Algorithms & Applications,2013,19(3):333-334.
    [14] LEE D T,SCHACHTER B J.Two algorithm for constructing a Delaunay triangulation[J].International Journal of Parallel Programming,1980,9(3):219-242.
    [15] MARCUM D L,WEATHERILL N P.Unstructured grid generation using iterative point insertion and local reconnection[J].AIAA Journal,1995,33(9):1619-1625.
    [16] RATHINAM S,SENGUPTA R,DARBHA S.A resource allocation algori-thm for multivehicle systems with nonholonomic constraints[J].IEEE Transactions on Automation Science and Engineering,2007,4(1):98-104.
  • 加载中
图(1)
计量
  • 文章访问数:  1470
  • HTML全文浏览量:  247
  • PDF下载量:  329
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-01-16
  • 刊出日期:  2017-12-28

目录

    /

    返回文章
    返回