Path relinking for the fixed spectrum frequency assignment problem

• Frequency assignment is a key issue in wireless communication systems.
• We introduce a population-based path relinking method to solve this problem.
• The method is assessed on 42 well-known benchmark instances in the literature.
• The method is able to discover improved best results (new upper bounds) for 19 instances.

The fixed spectrum frequency assignment problem (FS-FAP) is a highly relevant application in modern wireless systems. This paper presents the first path relinking (PR) approach for solving FS-FAP. We devise four relinking operators to generate intermediate solutions (or paths) and a tabu search procedure for local optimization. We also adopt a diversity-and-quality technique to maintain population diversity. To show the effectiveness of the proposed approach, we present computational results on the set of 42 benchmark instances commonly used in the literature and compare them with the current best results obtained by any other existing methods. By showing improved best results (new upper bounds) for 19 instances, we demonstrate the effectiveness of the proposed PR approach. We investigate the impact of the relinking operators and the population updating strategy. The ideas of the proposed could be applicable to other frequency assignment problems and search problems.