Applying two efficient hybrid heuristics for hub location problem with fully interconnected backbone and access networks

This paper considers the design of two-layered networks with fully interconnected backbone and access networks. The problem, a specific application of hub location to network design, is known as fully interconnected network design problem (FINDP). A novel mathematical programming formulation advantageous over an earlier formulation is presented to model the problem. Two hybrid heuristics are proposed to solve the problem, namely SAVNS and TSVNS which incorporate a variable neighborhood search (VNS) algorithm into the framework of simulated annealing (SA) and tabu search (TS). The proposed algorithms are able to easily obtain the optimal solutions for 24 small instances existing in the literature in addition to efficiently solve new generated medium and large instances. Results indicate that the proposed algorithms generate high quality solutions in a quite short CPU time.