An Efficient Genetic Algorithm for the Uncapacitated $R$-Allocation $P$-Hub Maximal Covering Problem

Olivera Janković

This paper deals with the Uncapacitated $r$-allocation $p$-hub Maximal Covering Problem (UrApHMCP) with a binary coverage criterion. This problem consists of choosing $p$ hub locations from a set of nodes so as to maximize the total demand covered under the $r$-allocation strategy. The general assumption is that the transportation between the non-hub nodes is possible only via hub nodes, while each non-hub node is assigned to at most $r$ hubs. An integer linear programming formulation of the UrApHMCP is presented and tested within the framework of a commercial CPLEX solver. In order to solve the problem on large scale hub instances that cannot be handled by the CPLEX, a Genetic Algorithm (GA) is proposed. The results of computational experiments on standard $p$-hub benchmark instances with up to 200 nodes demonstrate efficiency and effectiveness of the proposed GA method.