An efficient genetic algorithm for the Uncapacitated r-allocation p-hub maximal covering problem

Yugoslav Journal of Operations Research

Janković Olivera¹ 

[1] Faculty of Mathematics, Belgrade + Faculty of Economics, Kragujevac;

关键词: p-Hub maximal covering problem;    binary coverage;    heuristic;    genetic algorithm;   

DOI  :  10.2298/YJOR170120011J

来源: DOAJ

【 摘 要 】

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 nonhub 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.

【 授权许可】

Unknown