.png){kind=icon}
返回
Tabu search for the cyclic bandwidth problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.cor.2014.11.013.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The Cyclic Bandwidth (CB) problem for graphs consists in labeling the vertices of a guest graph G by distinct vertices of a host cycle C-n (both of order n) in such a way that the maximum distance in the cycle between adjacent vertices in G is minimized. To the best of our knowledge, this is the first research work investigating the use of metaheuristic algorithms for solving this challenging combinatorial optimization problem in the case of general graphs. In this paper a new carefully devised Tabu Search algorithm, called TSCB, for finding near-optimal solutions for the CB problem is proposed. Different possibilities for its key components and input parameter values were carefully analyzed and tuned, in order to find the combination of them offering the best quality solutions to the problem at a reasonable computational effort. Extensive experimentation was carried out, using 113 standard benchmark instances, for assessing its performance with respect to a Simulated Annealing (SA(CB)) implementation. The experimental results show that there exists a statistically significant performance amelioration achieved by TSCB with respect to SA(CB) in 90 out of 113 graphs (79.646%). It was also found that our TSCB algorithm attains 56 optimal solutions and establishes new better upper bounds for the other 57 instances. Furthermore, these competitive results were obtained expending reasonable computational times. (C) 2014 Elsevier Ltd. All rights reserved.
Keyword:
Cyclic bandwidth problem
Tabu search
Best-known bounds
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
.png){kind=icon}
分享收藏Tabu search for the single row facility layout problem using exhaustive 2-opt and insertion neighborhoods使用穷举2-opt和插入邻域的单行设施布局问题的禁忌搜索
PREAI
分享收藏
查看更多内容