Solving Large-Scale TSP Using a Fast Wedging Insertion Partitioning Approach

doi:10.1155/2015/854218

	Solving Large-Scale TSP Using a Fast Wedging Insertion Partitioning Approach
	Xiang, Zuoyong 1; Chen, Zhenyu 2; Gao, Xingyu 3; Wang, Xinjun 1; Di, Fangchun 2; Li, Lixin 2; Liu, Guangyi 2; Zhang, Yi 4
	2015
发表期刊	MATHEMATICAL PROBLEMS IN ENGINEERING
ISSN	1024-123X
页码	8
摘要	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.
DOI	10.1155/2015/854218
收录类别	SCI
语种	英语
资助项目	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类目	Engineering, Multidisciplinary ; Mathematics, Interdisciplinary Applications
WOS记录号	WOS:000365235400001
出版者	HINDAWI PUBLISHING CORP
引用统计	被引频次：6[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/9183
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Chen, Zhenyu
作者单位	1.Cent S Univ Forestry & Technol, Sch Sci, Changsha 410004, Hunan, Peoples R China 2.China Elect Power Res Inst, Beijing 100192, Peoples R China 3.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China 4.State Grid Fujian Elect Power Res Inst, Fuzhou 350007, Fujian, 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.