A Memetic Algorithm Designed for Solving Graph Coloring Problems: A Round-Robin Sports Scheduling Case Study

Abstract

Babak Javadi, Hamed Habibnejad-Ledari, Nezam Mahdavi-Amiri and Mohammadreza Abdali

The issue of graph coloring is concerned with assigning colors to each vertex of an undirected graph so that adjacent vertices are not assigned the same color. Due to its NP-hard nature, a variety of heuristics and metaheuristics have been developed to tackle this problem. One of these approaches is the memetic algorithm, which was introduced as a solution for this problem. Another example is using a metaheuristic approach to address the round-robin sports scheduling problem. The algorithm suggested for this task comprises three primary components: (1) a randomized danger heuristic algorithm, (2) tabu search, and (3) a genetic algorithm with adaptive multi-parent crossover. To assess the performance of this algorithm, a set of test problems from different benchmark graphs in two categories were selected and compared with nine effective heuristics from existing literature. The results show that the algorithm performs exceptionally well on benchmark graphs that are known to be challenging. Additionally, a case study was conducted to demonstrate the effectiveness of the proposed algorithm.

PDF