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

 引用本文: 寿涛, 刘朝晖. 基于Delaunay三角剖分处理二维欧式空间MTSP的近似算法[J]. 华东理工大学学报（自然科学版）, 2017, (6): 895-898.
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.

## 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.

##### 计量
• 文章访问数:  1470
• HTML全文浏览量:  247
• PDF下载量:  329
• 被引次数: 0
##### 出版历程
• 收稿日期:  2017-01-16
• 刊出日期:  2017-12-28

/

• 分享
• 用微信扫码二维码

分享至好友和朋友圈