A Hybrid Genetic Algorithm for Solving the Uncapacitated Multiple Allocation Hub Location Problem

Abstract

In this paper, a hybrid genetic algorithm for solving the Uncapacitated Multiple Allocation Hub Location Problem is proposed. This NP-hard problem has significant application in designing modern transportation and telecommunication networks, such as road and railway systems, postal systems, systems of fast delivery, etc. In order to improve the efficiency, genetic algorithm is combined with the local search heuristic. The proposed hybrid method shows to be very successful in solving problems of large dimensions with up to n = 120 nodes. It is also tested on instances with n = 130 and n = 200 nodes for which no optimal solution is presented in the literature so far. Although the optimal solutions are not known, we believe that the proposed hybrid method provides high quality solutions on these problem instances unsolved to optimality before.