Two vertices combination algorithm for TSP problem

doi:10.3778/j.issn.1002-8331.2009.17.013

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (17): 44-46.DOI: 10.3778/j.issn.1002-8331.2009.17.013

• 研究、探讨 • Previous Articles Next Articles

Two vertices combination algorithm for TSP problem

GUO Wen-qiang^1,2,QIN Zhi-guang¹,FENG hao³

1.University of Electronic Science and Technology of China，Chengdu 610054，China
2.Xinjiang University of Finance and Economics，Urumqi 830012，China
3.Xinjiang Provincal Public Security Bureau，Urumqi 830000，China

Received:2009-01-19 Revised:2009-02-19 Online:2009-06-11 Published:2009-06-11
Contact: GUO Wen-qiang

适用于求解TSP问题的二点组合算法

郭文强^1,2,秦志光¹,冯昊³

1.电子科技大学计算机科学与工程学院，成都 610054
2.新疆财经大学计算机科学与工程学院，乌鲁木齐 830012
3.新疆公安厅十一处计算机科，乌鲁木齐 830000

通讯作者: 郭文强

Abstract

Abstract: Based on the analysis of local optimal solution and the whole relationship between the optimal solution to the optimal solution for local classified，a method is designed for adding more kinds of local optimal types of two vertices combination algorithms，which is algorithm process of the multi-angle test and the results show that the algorithm of small and medium-scale is practical for traveling salesman problem.

Key words: ant colony optimization, heuristic algorithm, two vertices combination algorithm, traveling salesman problem（TSP）

摘要： 分析局部最优解与全局最优解之间关系，对局部最优解进行分类，给出一种可加入更多种局部最优类型的二点组合算法。对该算法程序进行的多角度测试结果表明这个算法在解决中小规模的旅行商问题时是实用的。

关键词: 蚁群算法, 启发式算法, 二点组合算法, 旅行商问题

GUO Wen-qiang^1,2,QIN Zhi-guang¹,FENG hao³. Two vertices combination algorithm for TSP problem[J]. Computer Engineering and Applications, 2009, 45(17): 44-46.

郭文强^1,2,秦志光¹,冯昊³. 适用于求解TSP问题的二点组合算法[J]. 计算机工程与应用, 2009, 45(17): 44-46.

[1]	BU Guannan, LIU Jianhua, JIANG Lei, ZHANG Dongyang. Ant Colony Algorithm with Adaptive Grouping [J]. Computer Engineering and Applications, 2021, 57(6): 67-73.
[2]	ZHU Jiaying, GAO Maoting. AUV Path Planning Based on Particle Swarm Optimization and Improved Ant Colony Optimization [J]. Computer Engineering and Applications, 2021, 57(6): 267-273.
[3]	LI Zhuangkuo, CHANG Kaixuan. Ant Colony Optimization for Continuous Domains Applied to Cooperative Game [J]. Computer Engineering and Applications, 2021, 57(24): 198-204.
[4]	HE Yaying, FAN Xinwei. Application of Improved Ant Colony Optimization in Robot Path Planning [J]. Computer Engineering and Applications, 2021, 57(16): 276-282.
[5]	ZHANG Chengling, LI Jinjin, LIN Yidong. Attribute Reduction in Formal Contexts Based on OE-Concept Lattices [J]. Computer Engineering and Applications, 2021, 57(15): 82-89.
[6]	ZHANG Ming, DENG Wenhan, LIN Juan, ZHONG Yiwen. Modified Ant Colony Optimization Algorithm for Discounted {0-1} Knapsack Problem [J]. Computer Engineering and Applications, 2021, 57(13): 85-95.
[7]	HU Chunyang, JIANG Ping, ZHOU Genrong. Application of Improved Ant Colony Optimization in AGV Path Planning [J]. Computer Engineering and Applications, 2020, 56(8): 270-278.
[8]	ZHANG Hainan, YOU Xiaoming, LIU Sheng, LIU Zhongqiang. Interactive Learning Cuckoo Search Algorithm [J]. Computer Engineering and Applications, 2020, 56(7): 147-154.
[9]	MENG Xin, YANG Qin, HAO Tingting, ZHANG Jie, CAO Cejun. Optimized Combination of Picking Path in Different Distributions and Algorithms [J]. Computer Engineering and Applications, 2020, 56(23): 229-236.
[10]	LI Yali, WANG Shuqin, CHEN Qianru, WANG Xiaogang. Comparative Study of Several New Swarm Intelligence Optimization Algorithms [J]. Computer Engineering and Applications, 2020, 56(22): 1-12.
[11]	YI Chengqi, GUO Xin, TONG Nannan, DOU Yue, CHEN Dong, WANG Jiandong. Innovation Situation Analysis Algorithm Based on Heuristic Model of Community Detection [J]. Computer Engineering and Applications, 2020, 56(15): 74-79.
[12]	HU Xiaomin, LIANG Tianyi, WANG Mingfeng, LI Min. Novel Tree Heuristic Search Algorithm for Robot Path Planning [J]. Computer Engineering and Applications, 2020, 56(11): 164-171.
[13]	FENG Jie, SHI Li. Research on Vehicle Routing Problem of Fresh Products with Pure Electric Refrigerator Truck [J]. Computer Engineering and Applications, 2019, 55(9): 237-242.
[14]	CHI Zongzheng, DONG Shaozheng, GUO Tong, REN Zhilei, ZHOU Kuanjiu, GUO He. Research on Wind Farm Layout Based on Hyper-Heuristic [J]. Computer Engineering and Applications, 2019, 55(7): 220-225.
[15]	GAO Ling1，2, WANG Fan1, GAO Ni1，3, MAO Yong1. Security Hardening Measures Selection Model Based on Improved Ant Colony Optimization [J]. Computer Engineering and Applications, 2019, 55(7): 100-107.

Two vertices combination algorithm for TSP problem

适用于求解TSP问题的二点组合算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics