Improved artificial bee colony algorithm for large scale colored bottleneck traveling salesman problem

Wenyong DONG; Xueshi DONG; Yufeng WANG

doi:10.11959/j.issn.1000-436x.2018284

您当前的位置：

首页 >

文章列表页 >

Improved artificial bee colony algorithm for large scale colored bottleneck traveling salesman problem

Papers | 更新时间：2024-06-05

- Improved artificial bee colony algorithm for large scale colored bottleneck traveling salesman problem
- Journal on Communications Vol. 39, Issue 12, Pages: 18-29(2018)
- 作者机构：
  
  武汉大学计算机学院，湖北武汉 430072
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(No.61672024);The National Natural Science Foundation of China(No.61170305)
- DOI：10.11959/j.issn.1000-436x.2018284
  CLC： TP301
- Online First：2018-12，
  
  Published：25 December 2018
- 稿件说明：
移动端阅览
Wenyong DONG, Xueshi DONG, Yufeng WANG. Improved artificial bee colony algorithm for large scale colored bottleneck traveling salesman problem[J]. Journal on Communications, 2018, 39(12): 18-29.
DOI：

Wenyong DONG, Xueshi DONG, Yufeng WANG. Improved artificial bee colony algorithm for large scale colored bottleneck traveling salesman problem[J]. Journal on Communications, 2018, 39(12): 18-29. DOI： 10.11959/j.issn.1000-436x.2018284.

摘要

在智能交通、多任务协作等领域，用着色瓶颈旅行商问题(CBTSP

colored bottleneck traveling salesman problem)所构建模型尺度易趋向于大规模，因此有必要研究大规模CBTSP及其求解算法。本文将一种改进蜂群算法(IABC

improved artificial bee colony algorithm)应用于求解大规模CBTSP。IABC首先运用m-tour编码方法生成问题的解，然后使用产生邻近解(GNS

generate neighboring solution)优化蜂群算法求解该问题，GNS通过采用删除和重插入操作来产生新的解，并在该过程中实现对已有解的优化。实验表明 IABC 求解大规模 CBTSP 问题的求解质量优于其他对比算法。

Abstract

In the fields such as intelligent transport and multiple tasks cooperation

the model scale constructed by colored bottleneck traveling salesman problem (CBTSP) tends to large scale

and therefore it is necessary to study the large scale CBTSP and its algorithms. An improved artificial bee colony algorithm (IABC) was applied to solve the large scale CBTSP. IABC employed generating neighboring solution (GNS) to improve artificial bee colony algorithm for CBTSP. GNS generated new solution by deletion and reinsertion operations

during this process

and it can optimized the existed solution for this problem. Experiments show that IABC can demonstrate better solution quality than other compared algorithms for large scale CBTSP.

关键词

Keywords

references

LI J , ZHOU M C , SUN Q , et al . Colored traveling salesman problem [J ] . IEEE Transactions on Cybernetics , 2015 , 45 ( 11 ): 2390 - 2401 .

LI J , QIRU S , ZHOU M C , et al . A new multiple traveling salesman problem and its genetic algorithm-based solution [C ] // The 2013 IEEE International Conference on Systems Man and Cybernetics , 2013 : 1 - 6 .

MENG X H , LI J , DAI X Z , et al . Variable neighborhood search for a colored traveling salesman problem [J ] . IEEE Transactions on Intelligent Transport Systems , 2018 , 19 ( 4 ): 1018 - 1025 .

DONG X S , DONG W Y , CAI Y L . Ant colony optimization for colored traveling salesman problem by multi-task learning [J ] . IET Intelligent Transport Systems , 2018 , 12 ( 8 ): 774 - 782 .

KAO M Y , SANGHI M . An approximation algorithm for a bottleneck traveling salesman problem [J ] . Journal of Discrete Algorithms , 2009 , 7 ( 3 ): 315 - 326 .

LARUSIC J , PUNNEN A P . The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis [J ] . Computer & Operation Research , 2014 , 43 : 20 - 35 .

AHMED Z H . A hybrid genetic algorithm for the bottleneck traveling salesman problem [J ] . ACM Transactions on Embedded Computing Systems , 2013 , 12 ( 1 ): 9:1 - 9:10 .

VAIRAKTARAKIS G . VAIRAKTARAKIS L . On Gilmore-Gomorys open question for the bottleneck TSP [J ] . Operations Research Letters , 2003 , 31 : 483 - 491 .

KABADI S N . Polynomial solvable cases of the TSP [M ] . Traveling Salesman Problem and its Variants , 2007 , 12 : 489 - 583 .

董学士，董文永，蔡永乐 . 混合算法求解着色瓶颈旅行商问题 [J ] . 计算机研究与发展， 2018 , 55 ( 11 ): 2372 - 2385 .

DONG X S , DONG W Y , CAI Y L . Hybrid algorithm for colored bot-tleneck traveling salesman problem [J ] . Journal of Computer Research and Development , 2018 , 55 ( 11 ): 2372 - 2385 .

CHENG R , JIN Y C . A competitive swarm optimizer for large scale optimization [J ] . IEEE Transaction on Cybernetics , 2015 , 45 ( 2 ): 191 - 204 .

YE B L , WU W M , LI L X , et al . A hierarchical model predictive control approach for signal splits optimization in large-scale urban road networks [J ] . IEEE Transaction on Intelligent Transport Systems , 2016 , 17 ( 8 ): 2182 - 2192 .

OMIDVAR M N , YANG M , MEI Y , et al . DG2: a faster and more accurate differential grouping for large-scale black-box optimization [J ] . IEEE Transaction on Evolutionary Computation , 2017 , 21 ( 6 ): 929 - 942 .

ZHANG X Y , TIAN Y , CHENG R , et al . A decision variable clustering-based evolutionary algorithm for large-scale many-objective optimization [J ] . IEEE Transaction on Evolutionary Computation , 2018 , 22 ( 1 ): 97 - 112 .

HU X M , HE F L , CHEN W N , et al . Cooperation coevolution with fast interdependency identification for large scale optimization [J ] . Information Science , 2017 , 381 : 142 - 160 .

GAO W F , HUANG L L , LIU S Y , et al . Artificial bee colony algorithm based on information learning [J ] . IEEE Transactions on Cybernetics , 2015 , 45 ( 12 ): 2827 - 2838 .

KARABOGA D . An idea based on honey bee swarm for numerical optimization [R ] . Computers Engineering Department, Engineering Faculty, Erciyes University , 2015 .

LI J Q , PAN Q K , DUAN P Y . An improved artificial bee colony algorithm for solving hybrid flexible flowshop with dynamic operation skipping [J ] . IEEE Transactions on Cybernetics , 2016 , 46 ( 6 ): 1311 - 1323 .

MANUEL L , CARLOS G M , FRANCISCO , , et al . Optimizing network attacks by artificial bee colony [J ] . Information Sciences , 2017 , 377 : 30 - 50 .

VENKATESH P , SINGH A . Two metaheuristic approaches for the multiple traveling salesperson problem [J ] . Applied Soft Computing , 2015 , 26 : 74 - 89 .

ZHANG H G , ZHOU J . Dynamic multicale region search algorithm using vitality selection for traveling salesman problem [J ] . Expert Systems with Applications , 2016 , 60 : 81 - 95 .

Views

1482

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

AI问答

⁰