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.

Authors

• Xiangjing Lai
• Jin-Kao Hao
• Zhipeng Lü Huazhong University of Science and Technology
• Fred Glover

Keywords

• Path relinking and tabu search
• Learning mechanism
• Bandwidth and graph coloring problems
• Population-based computing