Article ID: | iaor19982092 |
Country: | Netherlands |
Volume: | 78 |
Issue: | 1 |
Start Page Number: | 31 |
End Page Number: | 50 |
Publication Date: | Mar 1998 |
Journal: | Annals of Operations Research |
Authors: | Venkataramanan M.A., Abdinnour-Helm Sue |
Keywords: | networks: flow |
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, 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.