[1]张帅,汪芸,李凯.基于拓扑感知的TSP快速求解算法[J].东南大学学报(自然科学版),2014,44(3):522-525.[doi:10.3969/j.issn.1001-0505.2014.03.013]
 Zhang Shuai,Wang Yun,Li Kai.Fast TSP algorithm based on topological perception[J].Journal of Southeast University (Natural Science Edition),2014,44(3):522-525.[doi:10.3969/j.issn.1001-0505.2014.03.013]
点击复制

基于拓扑感知的TSP快速求解算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
44
期数:
2014年第3期
页码:
522-525
栏目:
自动化
出版日期:
2014-05-16

文章信息/Info

Title:
Fast TSP algorithm based on topological perception
作者:
张帅汪芸李凯
东南大学计算机科学与工程学院, 南京210096; 东南大学网络和信息集成教育部重点实验室, 南京210096
Author(s):
Zhang Shuai Wang Yun Li Kai
School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
Key Laboratory of Computer Network and Information Integration of Ministry of Education, Southeast University, Nanjing 210096, China
关键词:
拓扑 TSP 无线传感器网络 启发式算法
Keywords:
topology traveling salesman problem(TSP) wireless sensor networks heuristic algorithm
分类号:
TP212.9;TN929.5
DOI:
10.3969/j.issn.1001-0505.2014.03.013
摘要:
为了适应无线传感器网络环境的特点,提出了一种基于拓扑感知的旅行商问题(TSP)启发式快速求解算法.通过分析无线传感器网络拓扑与TSP解之间的关系,提出了基于最大公共同构子图的拓扑距离,并用于度量拓扑之间的相似度.然后,以拓扑距离为标准,对输入拓扑进行聚类分析,继而映射得出该输入拓扑的TSP解.该算法设置了合适的剪枝条件以提高运行速度,通过加入阈值参数来平衡类内拓扑间的相似度和聚类类别数目.仿真结果表明,在节点数为90和70的TSP环境下,这种拓扑感知算法的运行时间分别为0.615和0.508 s,约为Lin-Kernighan算法和蚁群算法的3%~4%,且其精确度介于这两种算法之间.
Abstract:
To satisfy the characteristics of wireless sensor networks, a high speed heuristic algorithm for traveling salesman problem(TSP)based on topological perception is put forward. Through analyzing the relationship between the topology of wireless sensor networks and the solution of TSP, the topological distance based on the maximum common subgraph isomorphism is defined to compute the similarity of topologies. Then, the input topology is clustered based on the topological distance and the solution of TSP is solved through mapping. In the proposed algorithm, appropriate trim conditions are set to improve the speed of the algorithm. A threshold parameter is added to balance the similarity of topologies in class and the number of generated clusters. The simulation results show that when the numbers of the nodes are 90 and 70 in TSP, the running time of this topological perception algorithm are 0.615 and 0.508 s, respectively, which are about 3% to 4% of those of the Lin-Kernighan algorithm and the ant cology algorithm. And the precision of the proposed algorithm is between those of the two algorithms.

参考文献/References:

[1] Applegate D L, Bixby R E, Chvatal V, et al. The traveling salesman problem: a computational study [M]. Princeton: Princeton University Press, 2011: 10-21.
[2] Lihoreau M, Chittka L, Raine N E. Travel optimization by foraging bumblebees through readjustments of traplines after discovery of new feeding locations [J]. The American Naturalist, 2010, 176(6): 744-757.
[3] Sugihara R, Gupta R K. Optimal speed control of mobile node for data collection in sensor networks [J]. IEEE Transactions on Mobile Computing, 2010, 9(1): 127-139.
[4] Bunke H. On a relation between graph edit distance and maximum common subgraph [J]. Pattern Recognition Letters, 1997, 18(8): 689-694.
[5] Cordella L P, Foggia P, Sansone C, et al. A(sub)-graph isomorphism algorithm for matching large graphs [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(10): 1367-1372.
[6] Conte D, Foggia P, Vento M. Challenging complexity of maximum common subgraph detection algorithms: a performance analysis of three algorithms on a wide database of graphs [J]. Journal of Graph Algorithms and Applications, 2007, 11(1): 99-143.
[7] Vansteenwegen P, Souffriau W, Oudheusden D V. The orienteering problem: a survey [J]. European Journal of Operational Research, 2011, 209(1): 1-10.
[8] Lin S, Kernighan B W. An effective heuristic algorithm for the traveling-salesman problem [J]. Operations Research, 1973, 21(2): 498-516.
[9] Dorigo M, Gambardella L M. Ant colonies for the travelling salesman problem [J]. Biosystems, 1997, 43(2): 73-81.
[10] Hlaing Z C S S, Khine M A. An ant colony optimization algorithm for solving traveling salesman problem [C]//International Conference on Information Communication and Management. Singapore, 2011: 54-59.

相似文献/References:

[1]王发鸿,达庆利.逆向物流单车辆运输策略[J].东南大学学报(自然科学版),2006,36(1):156.[doi:10.3969/j.issn.1001-0505.2006.01.032]
 Wang Fahong,Da Qingli.Transportation strategy of single vehicle in reverse logistics[J].Journal of Southeast University (Natural Science Edition),2006,36(3):156.[doi:10.3969/j.issn.1001-0505.2006.01.032]

备注/Memo

备注/Memo:
收稿日期: 2013-11-04.
作者简介: 张帅(1988—),男,硕士生;汪芸(联系人),女,博士,教授,博士生导师,yunwang@seu.edu.cn.
引用本文: 张帅,汪芸,李凯.基于拓扑感知的TSP快速求解算法[J].东南大学学报:自然科学版,2014,44(3):522-525. [doi:10.3969/j.issn.1001-0505.2014.03.013]
更新日期/Last Update: 2014-05-20