Solution approaches to hub location problems

The hub location problem involves a network of origins and destinations over which transport takes place. Any distribution system falls into this type of category. In this paper, we present a new quadratic integer formulation for the Uncapacitated Hub Location Problem (UHP), which is based on the idea of multi-commodity flows in networks. This new formulation lends itself well for using a branch-and-bound procedure to find optimal solutions. The branch-and-bound procedure is not implemented in a traditional fashion, where bounds are obtained by linearizing the objective function and relaxing the integrality constraints. Instead, a more sophisticated approach is used where bounds are obtained by employing the underlying network structure of the problem. In addition, an artificial intelligence-based technique (Genetic Search) is designed to find solutions quickly and efficiently. The two solution approaches assume that the number of hubs is a variable, each spoke is assigned to a single hub, and all hubs are interconnected. The model and the algorithm can be applied even when all the hubs are not directly linked.