[1]赵玉章 郭文强 冯昊[].基于二点组合算法的旅行商问题应用性能分析[J].计算机技术与发展,2011,(10):137-139.
　ZHAO Yu-zhang,GUO Wen-qiang,FENG Hao.Performance Analysis of Two Vertices Combination Algorithm in TSP[J].,2011,(10):137-139.
点击复制

基于二点组合算法的旅行商问题应用性能分析()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2011年10期
页码:
137-139
栏目:
智能、算法、系统工程
出版日期:
1900-01-01

文章信息/Info

Title:
Performance Analysis of Two Vertices Combination Algorithm in TSP
文章编号:
1673-629X（2011）10-0137-03
作者:
赵玉章1 郭文强1; 2 冯昊[3]
[1]新疆财经大学计算机科学与工程学院[2]电子科技大学计算机科学与工程学院[3]新疆公安厅十一处计算机科
Author(s):
ZHAO Yu-zhang ; GUO Wen-qiang ; FENG Hao
[1]School of Computer Sci. and Eng. , Xinjiang University of Finance and Economics[2]School of Computer Sci. and Eng. , University of Electronic Sci. and Technology[3]Computer Section of Eleven Department, Xinjiang Public Security Bureau
关键词:
旅行商问题; 二点组合算法; 环路改造
Keywords:
traveling salesman problem; two vertices combination algorithm;  loop transformation
分类号:
TP181
文献标志码:
A
摘要:
旅行商问题模型应用广泛，其求解策略的研究具有重要的理论和实践意义。为高效快速解决旅行商问题，给出一种基于环路改造的二点组合算法，即选取一条汉密尔顿环路作为目标解，任取两个顶点删除与之相关的边形成2至4个环路片断，对这些环路片断进行排列组合，尝试寻找更优的解替换目标解的方法。仿真实验结果表明，该算法的计算效率和计算误差性能皆优于蚁群算法，实际应用结果也表明本算法在解决中小规模旅行商问题时的实用性。因此，本算法具有较强的理论价值和较强的实用价值，可以较好地完成中等规模的TSP问题，且适用于一系列的优化组合问题
Abstract:
In order to efficiently solve TSP problem, given a two vertices combination algorithm based on loop transformation. Hamilton Circle is selected as the target of a solution, take any two vertices associated with edges removed to form 2 to 4 loop clips, clips of permutations and combinations of these loops, try to find better solutions replaced target solution method. Comparing this method with ant colony algorithm, its time complexity and computational accuracy are better than those of the latter. The results show that this proposed algorithm possesses a better practicability in solving the middle and small scale traveling salesman problem. So, .this method has strong theoretical and practical value. It can better complete the medium-scale TSP problems, and it applied to a series of optimization

相似文献/References:

[1]段凤玲 李龙澍 曹文婷.具有多态特征和聚类处理的蚁群算法[J].计算机技术与发展,2009,(12):77.
　DUAN Feng-ling,LI Long-shu,CAO Wen-ting.Ant Colony Algorithm with Polymorphism and Clustering Processing[J].,2009,(10):77.
[2]杨益 方潜生 高翠云.求解TSP问题的遗传算法硬件实现[J].计算机技术与发展,2009,(04):54.
　YANG Yi,FANG Qian-sheng,GAO Cui-yun.Implementation of Hardware Based on Genetic Algorithm for Solving TSP Problem[J].,2009,(10):54.
[3]王娟 王建.一种求解TSP问题的改进蚁群算法[J].计算机技术与发展,2008,(12):50.
　WANG Juan,WANG Jian.An Improved Ant Colony Algorithm for Solving TSP Problem[J].,2008,(10):50.
[4]苏劲松 周昌乐 蒋旻隽.一种基于逆转算子的求解TSP问题的改进演化算法[J].计算机技术与发展,2007,(07):94.
　SU Jin-song,ZHOU Chang-le,JIANG Min-jun.An Improved Evolutionary Algorithm for Traveling Salesman Problem Based on Inver- Over Operator[J].,2007,(10):94.
[5]陈文兰 戴树贵.求解旅行商问题的混合蚂蚁算法[J].计算机技术与发展,2007,(07):110.
　CHEN Wen-lan,DAI Shu-gui.A Hybrid Ant Colony Algorithm for Solving Traveling Salesman Problem[J].,2007,(10):110.
[6]孙宪丽 王敏 李颖.求解TSP问题的一种启发式算法[J].计算机技术与发展,2010,(10):70.
　SUN Xian-li,WANG Min,LI Ying.A Heuristic Algorithm to Solve Travelling Salesman Problem[J].,2010,(10):70.
[7]赵越,徐鑫,赵焱,等.自适应记忆遗传算法研究[J].计算机技术与发展,2014,24(02):63.
　ZHAO Yue[],XU Xin[],ZHAO Yan[],et al.Research on Adaptive Memory Genetic Algorithm[J].,2014,24(10):63.
[8]宗德才[],王康康[]. 旅行商问题中巡回路径的数据结构[J].计算机技术与发展,2014,24(12):72.
　ZONG De-cai[],WANG Kang-kang[]. Data Structure of Tour for Traveling Salesman Problem[J].,2014,24(10):72.
[9]易正俊[],李勇霞[],易校石[].自适应蚁群算法求解最短路径和TSP问题[J].计算机技术与发展,2016,26(12):1.
　YI Zheng-jun[],LI Yong-xia[],YI Xiao-shi[]. Solving of Shortest Path Problem and TSP with Adaptive Ant Colony Algorithm[J].,2016,26(10):1.
[10]马金科,王 直.基于改进蚁群算法的盘点型机器人路径规划[J].计算机技术与发展,2019,29(07):84.[doi:10. 3969 / j. issn. 1673-629X. 2019. 07. 017]
　MA Jin-ke,WANG Zhi.Path Planning of Inventory Robot Based on Improved Ant Colony Algorithm[J].,2019,29(10):84.[doi:10. 3969 / j. issn. 1673-629X. 2019. 07. 017]

备注/Memo

备注/Memo:
国家自然科学基金资助项目（60902074）;新疆高校科研计划项目（XJEDU2009S79）赵玉章（1956-），男，副教授，研究方向为算法分析、信息管理；郭文强，博士，教授，博士后，研究方向为人工智能，信息安全
更新日期/Last Update: 1900-01-01