Research on traveling salesman problem and its solving with hybrid particle swarm optimization algorithm

doi:10.3778/j.issn.1002-8331.2009.25.012

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (25): 38-40.DOI: 10.3778/j.issn.1002-8331.2009.25.012

• 研究、探讨 • Previous Articles Next Articles

Research on traveling salesman problem and its solving with hybrid particle swarm optimization algorithm

SUN Cong，ZHAO Xin-chao

Department of Mathematics，School of Science，Beijing University of Posts and Telecommunications，Beijing 100876，China

Received:2008-10-23 Revised:2009-01-12 Online:2009-09-01 Published:2009-09-01
Contact: SUN Cong

旅行商问题研究及混合粒子群算法求解

孙聪，赵新超

北京邮电大学理学院数学系，北京 100876

通讯作者: 孙聪

Abstract

Abstract: This paper qualitatively analyzes the basic Particle Swarm Optimization（PSO） algorithm.Integrating the ideas of genetic algorithm，3 kinds of crossover and 4 mutation operators are constructed and 12 hybrid PSO algorithms are obtained.A 14-city problem is firstly used to examine and analyze the proposed algorithms.To further verify the proposed algorithms’ performance，several good hybrid algorithms are selected based on the analytic results to solve the Chinese 34-city problem（CTSP） and the kroC100 problem.The optimal solution is quickly obtained for CTSP instance and an even better solution compared with the recent algorithms is obtained for kroC100 instance.

Key words: traveling salesman problem, Particle Swarm Optimization（PSO）, 2-opt, 3-opt, genetic algorithm

摘要： 定性地分析了基本粒子群算法，结合遗传算法思想，构造了3种杂交和4种变异运算法则，从而得到了12种混合粒子群算法，并采用14城市算例对其检验和分析。为进一步验证混合算法的性能，根据分析结果挑选了几种较优的混合算法用以解决中国34城市（CTSP）问题和kroC100问题，其中CTSP问题很快达到最优解，对kroC100问题该文提供的算法获得了一个比现有已知结果更好的结果。

关键词: 旅行商问题, 粒子群算法, 2-opt, 3-opt, 遗传算法

CLC Number:

TP302.7

SUN Cong，ZHAO Xin-chao. Research on traveling salesman problem and its solving with hybrid particle swarm optimization algorithm[J]. Computer Engineering and Applications, 2009, 45(25): 38-40.

孙聪，赵新超. 旅行商问题研究及混合粒子群算法求解[J]. 计算机工程与应用, 2009, 45(25): 38-40.

[1]	ZHANG Songcan, PU Jiexin, SI Yanna, SUN Lifan. Adaptive Improved Ant Colony Algorithm Based on Population Similarity and Its Application [J]. Computer Engineering and Applications, 2021, 57(8): 70-77.
[2]	BU Guannan, LIU Jianhua, JIANG Lei, ZHANG Dongyang. Ant Colony Algorithm with Adaptive Grouping [J]. Computer Engineering and Applications, 2021, 57(6): 67-73.
[3]	HU Xiaomin, WANG Mingfeng, ZHANG Shourong, LI Min. New Differential Evolution with Particle Swarm Optimization Algorithm for Text Clustering [J]. Computer Engineering and Applications, 2021, 57(4): 61-67.
[4]	LI Yuqi, LIU Zhiqian, CHENG Ningyi, WANG Yingying, ZHU Chunli. Path Planning of UAV Under Multi-constraint Conditions [J]. Computer Engineering and Applications, 2021, 57(4): 225-230.
[5]	YANG Wei, WU Yingying, WANG Ting. Research on Configuration Optimization Problems of Shuttle-Carrier Storage and Retrieval System [J]. Computer Engineering and Applications, 2021, 57(4): 258-265.
[6]	WANG Jiayue, SHI Li. Research on Path Optimization and Charging Strategy of Electric Refrigerated Vehicle Considering Cost of Battery Capacity Degradation [J]. Computer Engineering and Applications, 2021, 57(24): 283-289.
[7]	LI Qian, JIANG Li, LIANG Changyong. Multi-objective Cold Chain Distribution Optimization Based on Fuzzy Time Window [J]. Computer Engineering and Applications, 2021, 57(23): 255-262.
[8]	DU Shouxin, WU Tao. Study on Application of Double Population Hybrid Genetic Algorithm in Cut Order Planning [J]. Computer Engineering and Applications, 2021, 57(22): 182-189.
[9]	LIN Weixing, WANG Yujia, CHEN Wanfen, LIANG Haina. High-Dimensional Data Feature Selection Algorithm Based on Multifactor Particle Swarm Optimization [J]. Computer Engineering and Applications, 2021, 57(22): 199-207.
[10]	CAO Lijia, LIU Yang. Recent Advances in Scheduling Optimization of Automated Guided Vehicles in Manufacturing Workshops [J]. Computer Engineering and Applications, 2021, 57(21): 59-67.
[11]	CHEN Qianru, LI Yali, XU Kequan, LIU Yilong, WANG Shuqin. WKNN Feature Selection Method Based on Self-Tuning Adaptive Genetic Algorithm [J]. Computer Engineering and Applications, 2021, 57(20): 164-171.
[12]	MA Yanfang, LI Baoyu, YANG Yifu, FENG Cuiying. Two-Echelon Capacitated Vehicle Routing Model and Algorithm for Fresh Products Distribution with Customer Classification [J]. Computer Engineering and Applications, 2021, 57(20): 287-298.
[13]	SHI Yuqiang, TIAN Yongzheng, ZHANG Yuqi, SHI Xiaoqiu. Solving FJSP by Multi-population Genetic Algorithms with Complex Network Structure [J]. Computer Engineering and Applications, 2021, 57(2): 257-266.
[14]	DAI Jiangtao, HAN Xiaolong. Coordinated Scheduling of Equipment in Container Terminals Considering Energy Consumption Under Different Job Status [J]. Computer Engineering and Applications, 2021, 57(19): 290-298.
[15]	JIANG Liangzhong, LEI Hang, LI Zhenhao, QIAN Weizhong, SHI Gantu. Research on Outbound Slotting Optimization Method by Using Adaptive Optimization Weights [J]. Computer Engineering and Applications, 2021, 57(15): 271-278.

Research on traveling salesman problem and its solving with hybrid particle swarm optimization algorithm

旅行商问题研究及混合粒子群算法求解

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics