Abstract:

This paper addresses the Uncapacitated Single Allocation p-hub Maximal Covering Problem (USApHMCP), which aims to determine the best allocation for the p-hubs within a node network in order to maximize the network coverage. We proposed a search strategy-based heuristic VNS (Variable Neighborhood Search [7]) to solve the problem. Two different sets of literature test instances, Civil Aeronautics Board (CAB) and Australian Post (AP), were used to evaluate the performance of VNS and compare it to the Tabu Search metaheuristic (TS) proposed by [11]. As a result, the VNS presented equal or slightly smaller bounds for large-scale AP instances, as well as a similar behavior was shown regarding the quality of the solutions for CAB instances. In addition, it was observed that VNS performs better than the TS algorithm in CPU running times for both CAB and AP instances.