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

作者：Saboury Ali; Ghaffari Nasab Nader^*; Barzinpour Farnaz; Jabalameli Mohamad Saeed

来源：Computers & Operations Research, 2013, 40(10): 2493-2507.

DOI：10.1016/j.cor.2013.01.008

• Hierarchical networks
• Hub location
• Hybrid heuristic
• Simulated annealing
• Tabu search
• Variable neighborhood search

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 SA(VNS) 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.

• 出版日期2013-10