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

doi:10.3778/j.issn.1002-8331.2009.25.012

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (25): 38-40.DOI: 10.3778/j.issn.1002-8331.2009.25.012

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

孙聪，赵新超

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

收稿日期:2008-10-23 修回日期:2009-01-12 出版日期:2009-09-01 发布日期:2009-09-01
通讯作者: 孙聪

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

摘要/Abstract

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

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

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

中图分类号:

TP302.7

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

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.

[1]	史春天，曾艳阳，侯守明. 群体智能算法在图像分割中的应用综述[J]. 计算机工程与应用, 2021, 57(8): 36-47.
[2]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[3]	李静星，杨有龙. 针对高维数据的马尔科夫毯特征选择[J]. 计算机工程与应用, 2021, 57(6): 58-66.
[4]	卜冠南，刘建华，姜磊，张冬阳. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73.
[5]	朱佳莹，高茂庭. 融合粒子群与改进蚁群算法的AUV路径规划算法[J]. 计算机工程与应用, 2021, 57(6): 267-273.
[6]	李昱奇，刘志乾，程凝怡，王莹莹，朱春丽. 多约束条件下无人机航迹规划[J]. 计算机工程与应用, 2021, 57(4): 225-230.
[7]	杨玮，吴莹莹，王婷. 子母式穿梭车仓储系统配置优化问题研究[J]. 计算机工程与应用, 2021, 57(4): 258-265.
[8]	王嘉月，史立. 考虑电池损耗的电动冷藏车路径及充电策略[J]. 计算机工程与应用, 2021, 57(24): 283-289.
[9]	李倩，蒋丽，梁昌勇. 基于模糊时间窗的多目标冷链配送优化[J]. 计算机工程与应用, 2021, 57(23): 255-262.
[10]	杜守信，毋涛. 双种群混合遗传算法的裁剪分床应用研究[J]. 计算机工程与应用, 2021, 57(22): 182-189.
[11]	林炜星，王宇嘉，陈万芬，梁海娜. 基于多因子粒子群的高维数据特征选择算法[J]. 计算机工程与应用, 2021, 57(22): 199-207.
[12]	曹立佳，刘洋. 制造车间自动导引车调度新进展[J]. 计算机工程与应用, 2021, 57(21): 59-67.
[13]	陈倩茹，李雅丽，许科全，刘铱龙，王淑琴. 自调优自适应遗传算法的WKNN特征选择方法[J]. 计算机工程与应用, 2021, 57(20): 164-171.
[14]	石宇强，田永政，张雨琦，石小秋. 运用含复杂网络结构的多种群遗传算法求解FJSP[J]. 计算机工程与应用, 2021, 57(2): 257-266.
[15]	代江涛，韩晓龙. 考虑作业状态能耗的集装箱码头设备协调调度[J]. 计算机工程与应用, 2021, 57(19): 290-298.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics