Title: An efficient hybrid meta-heuristic ant system for minimum sum colouring problem

Authors: Amin Mohammadnejad; Kourosh Eshghi

Addresses: Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran ' Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran

Abstract: Graph sum colouring problem is a special class of graph vertex colouring problem. Because of its various applications in practical areas, especially in scheduling, many researchers have been focused on it during the past decade. In recent years, several heuristic and meta-heuristic algorithms have been developed to solve sum colouring problem. In this research, a hybrid algorithm based on mini-max ant system and simulated annealing is applied for the problem. This algorithm is tested on benchmark random graphs and compared to the previous algorithms. Results show that in many cases, the best known results can be obtained or improved by the proposed algorithm.

Keywords: graph sum colouring; graph colouring; ant colony; meta-heuristics.

DOI: 10.1504/IJOR.2019.097579

International Journal of Operational Research, 2019 Vol.34 No.2, pp.269 - 284

Received: 28 Oct 2015
Accepted: 04 Mar 2016
Published online: 30 Jan 2019 *

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