中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
Solving Large-Scale TSP Using a Fast Wedging Insertion Partitioning Approach

文献类型：期刊论文

作者Xiang, Zuoyong3; Chen, Zhenyu2; Gao, Xingyu4; Wang, Xinjun3; Di, Fangchun2; Li, Lixin2; Liu, Guangyi2; Zhang, Yi1
刊名MATHEMATICAL PROBLEMS IN ENGINEERING
出版日期2015
页码8
ISSN号1024-123X
DOI10.1155/2015/854218
英文摘要A new partitioning method, called Wedging Insertion, is proposed for solving large-scale symmetric Traveling Salesman Problem (TSP). The idea of our proposed algorithm is to cut a TSP tour into four segments by nodes' coordinate (not by rectangle, such as Strip, FRP, and Karp). Each node is located in one of their segments, which excludes four particular nodes, and each segment does not twist with other segments. After the partitioning process, this algorithm utilizes traditional construction method, that is, the insertion method, for each segment to improve the quality of tour, and then connects the starting node and the ending node of each segment to obtain the complete tour. In order to test the performance of our proposed algorithm, we conduct the experiments on various TSPLIB instances. The experimental results show that our proposed algorithm in this paper is more efficient for solving large-scale TSPs. Specifically, our approach is able to obviously reduce the time complexity for running the algorithm; meanwhile, it will lose only about 10% of the algorithm's performance.
资助项目National Natural Science Foundation of China[11447034] ; National High-Tech Research and Development 863 Plan of China[2014AA051901] ; Science and Technology Program of State Grid Corporation of China[DZB17201400108]
WOS研究方向Engineering ; Mathematics
语种英语
WOS记录号WOS:000365235400001
出版者HINDAWI PUBLISHING CORP
源URL[http://119.78.100.204/handle/2XEOYT63/9182]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Chen, Zhenyu
作者单位1.State Grid Fujian Elect Power Res Inst, Fuzhou 350007, Fujian, Peoples R China
2.China Elect Power Res Inst, Beijing 100192, Peoples R China
3.Cent S Univ Forestry & Technol, Sch Sci, Changsha 410004, Hunan, Peoples R China
4.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China
推荐引用方式
GB/T 7714		 Xiang, Zuoyong,Chen, Zhenyu,Gao, Xingyu,et al. Solving Large-Scale TSP Using a Fast Wedging Insertion Partitioning Approach[J]. MATHEMATICAL PROBLEMS IN ENGINEERING,2015:8.
APA Xiang, Zuoyong.,Chen, Zhenyu.,Gao, Xingyu.,Wang, Xinjun.,Di, Fangchun.,...&Zhang, Yi.(2015).Solving Large-Scale TSP Using a Fast Wedging Insertion Partitioning Approach.MATHEMATICAL PROBLEMS IN ENGINEERING,8.
MLA Xiang, Zuoyong,et al."Solving Large-Scale TSP Using a Fast Wedging Insertion Partitioning Approach".MATHEMATICAL PROBLEMS IN ENGINEERING (2015):8.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。