A hybrid algorithm of simulated annealing and tabu search for graph colouring problem

The graph colouring problem, as an important NP‐complete problem, is considered in this paper and a hybrid meta‐heuristic approach is developed to solve it. The initial solution of the algorithm, generated by a heuristic method, is used by a simulated annealing (SA) approach to generate new solutions until no progress in a number of solutions reported. At this stage, the algorithm will use a tabu search routine and this local search operator will be followed for some iterations. After finding a better solution, the algorithm is again followed through SA. Efficiency of the algorithm is showed through various experiments on well‐known benchmark problems of DIMACS. Comparison with the available algorithms shows considerable performance in terms of solution quality and computational time.