Title: Ant colony optimisation with local search for the bandwidth minimisation problem on graphs

Authors: Jian Guan; Geng Lin; Hui-Bin Feng

Addresses: Modern Educational Technology Center, Minjiang University, Fuzhou, China ' College of Mathematics and Data Science, Minjiang University, Fuzhou, China ' College of Computer and Control Engineering, Minjiang University, Fuzhou, China

Abstract: The bandwidth minimisation problem on graphs (BMPG) is an NP-complete problem, which consists of labelling the vertices of a graph with the integers from 1 to n (n is the number of vertices) such that the maximum absolute difference between labels of adjacent vertices is as small as possible. In this paper, an application of the ant colony optimisation with local search is presented to solve the bandwidth minimisation problem. The main novelty of the proposed approach is an efficient local search combined with first improvement and best improvement strategies. A fast incremental evaluation technique is employed to avoid excessive fitness evaluations of moves in local search. Computational experiments on 56 benchmark instances show that the proposed algorithm is able to achieve competitive results.

Keywords: metaheuristics; ant colony optimisation; bandwidth minimisation problem; local search; intelligent algorithm.

DOI: 10.1504/IJIIDS.2019.102327

International Journal of Intelligent Information and Database Systems, 2019 Vol.12 No.1/2, pp.65 - 78

Received: 27 Jul 2018
Accepted: 13 Feb 2019
Published online: 18 Sep 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article