Iterated local search with tabu search for the weighted vertex coloring problem. (January 2021)

• Record Type: Journal Article
• Authors: Nogueira, Bruno; Tavares, Eduardo; Maciel, Paulo
• Is Part Of: Computers & operations research. Volume 125(2021)
• Publication Date: 2021-01
• Subjects: Combinatorial optimization -- Weighted vertex coloring problem -- Iterated local search -- Tabu search -- Metaheuristics; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2020.105087
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: An efficient iterated local search heuristic of the weighted vertex coloring problem. Comparison with state-of-the-art heuristic and exact methods for the problem. Comprehensive experimental evaluation considering four well-known benchmark instances. Experimental results demonstrate that the heuristic outperforms the other methods in both solution quality and computational time. Abstract: This paper proposes an iterated local search (ILS) based heuristic for the weighted vertex coloring problem (WVCP). Given a graph G ( V, E ) with a weight w ( v ) associated with each vertex v ∈ V, the WVCP asks to find a coloring { V 1, …, V k } of G that minimizes ∑ i = 1 k max v ∈ V i w ( v ) . This problem has many theoretical and practical applications, such as batch scheduling, buffer minimization, and traffic assignment in telecommunication. Our ILS heuristic relies on two new neighborhood structures for the problem, and its local search component is hybridized with a tabu search strategy. We compare our approach with state-of-the-art heuristics and exact methods for the problem. Experimental results on well-known benchmark instances demonstrate that, first, our heuristic is better than the other heuristics in both solution quality and computational time, and, second, it is a good alternative for large instances that cannot be solved by exact methods.