A variable neighborhood search approach for cyclic bandwidth sum problem

In this paper, we tackle the Cyclic Bandwidth Sum Problem, consisting in minimizing the sum of the bandwidth of the edges of an input graph computed in a cycle-structured host graph. This problem has been widely studied in the literature due to its multiple real-world applications, such as circuit d...

Full description

Saved in:
Bibliographic Details
Published in:Knowledge-based systems 2022-06, Vol.246, p.108680, Article 108680
Main Authors: Cavero, Sergio, Pardo, Eduardo G., Duarte, Abraham, Rodriguez-Tello, Eduardo
Format: Article
Language:English
Subjects:
Bandwidths
Circuit design
Combinatorial optimization
Cyclic bandwidth sum
Graph layout problem
Graph theory
Greedy algorithm
Greedy algorithms
Heuristic methods
Statistical tests
Variable Neighborhood search
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we tackle the Cyclic Bandwidth Sum Problem, consisting in minimizing the sum of the bandwidth of the edges of an input graph computed in a cycle-structured host graph. This problem has been widely studied in the literature due to its multiple real-world applications, such as circuit design, migration of telecommunication networks, or graph drawing, among others. Particularly, we tackle this problem by proposing a multistart procedure whose main components are a new greedy constructive algorithm and an intensification strategy based on the Variable Neighborhood Search metaheuristic. The constructive procedure introduces two different greedy criteria to determine each step of the construction phase, which can be used for other related problems. Additionally, we illustrate how to perform an efficient exploration of the neighborhood structure by using an alternative neighborhood. Our algorithmic proposal is evaluated over a set of 40 instances previously studied in the literature and over a new proposed set of 66 well-known instances introduced in this paper. The obtained results have been satisfactory compared with the ones obtained by the best previous algorithm in the state of the art. The statistical tests performed indicate that the differences between the methods are significant.
ISSN:0950-7051
1872-7409
DOI:10.1016/j.knosys.2022.108680