Hybrid Evolutionary Algorithm for the Overlap Constrained Resource Allocation Problem in Wireless Networks

In wireless networks, efficiently allocating limited network resources holds significant practical importance. This work focuses on the NP-hard overlap constrained resource allocation problem (OCRAP) in wireless networks. As one of the practical decision-making problems, OCRAP aims to find a subset of candidate wireless resources, each capable of servicing multiple areas, to maximize the profit function while satisfying the given budget and overlap constraints. We have formulated the OCRAP model based on the budgeted maximum coverage problem and propose an effective hybrid evolutionary algorithm (HEA) for solving it. The proposed HEA algorithm combines a tabu search procedure for local optimization with an effective crossover operator to generate promising offspring solutions. We show computational results on 60 benchmark instances and present comparative studies with several heuristic algorithms as well as the general CPLEX solver. We also provide a convergence analysis to further demonstrate the robust performance of the proposed algorithm.