A Parallel evolutionary algorithm for the hub location problem with fully interconnected backbone and access networks

摘要

This paper proposes a parallel evolutionary algorithm to tackle the fully interconnected network design problem (FINDP), a specific application of hub location to network design. The FINDP has been recently proposed as an NP-hard combinatorial optimization problem formed by two smaller sub-problems: first, given the nodes which form the network, classify them as belonging to the backbone network or not. The second sub-problem consists of assigning the access network to a hub (node of the backbone network). In this paper we propose a parallel evolutionary algorithm to tackle the FINDP. We describe the architecture and how to structure the algorithm to solve the problem. Experimental tests have been carried out in several synthetic instances, and a comparison with existing approaches have shown the good performance of our algorithm.