A learning-based path relinking algorithm for the bandwidth coloring problem

This paper proposes a learning-based path relinking algorithm (LPR) for solving the bandwidth coloring problem and the bandwidth multicoloring problem. Based on the population path-relinking framework, the proposed algorithm integrates a learning-driven tabu optimization procedure and a path-relinking operator. LPR is assessed on two sets of 66 common benchmark instances, and achieves highly competitive results in terms of both solution quality and computational efficiency compared to the state-of-the-art algorithms in the literature. Specifically, the algorithm establishes 7 new upper bounds while matching the best known results for 56 cases. The impacts of the learning mechanism and the path relinking operators are investigated, confirming their critical role to the success of the proposed algorithm. (C) 2016 Elsevier Ltd. All rights reserved.