A hybrid heuristic for the uncapacitated hub location problem

Given n interacting nodes in a network, the Uncapacitated Hub Location Problem (UHP) determines the number of hubs, the location for the hubs, and the assignment of the spokes to hubs that minimizes the overall transportation cost. The hubs are interconnected and each spoke is assigned to a single hub. A new heuristic method is developed based on a hybrid of Genetic Algorithms (GAs) and Tabu Search (TS). The new heuristic yields much improved results when compared to applying GAs alone. In all but one of the cases tested, the results matched the best solutions found in the literature so far. (C) 1998 Elsevier Science B.V. All rights reserved.