Title: A note on solution of the capacitated single allocation hub location problem

Authors: Jeng-Fung Chen

Addresses: Department of Industrial Engineering and Systems Management, Feng Chia University, P.O. Box 25-097, Taichung 40724, Taiwan

Abstract: Hub-and-spoke designs are frequently used in many types of transportation and communication networks. The challenge to academics is to develop effective solution procedures for determining the number of hubs, locating hub facilities and allocating the non-hubs to the hubs. In this note, we deal with the capacitated single allocation hub location problem (CSAHLP) in which each non-hub can only be allocated to a single hub, each hub has its capacity constraint, and the objective function includes fixed costs for establishing hubs. A problem closely related to the CSAHLP is the uncapacitated single allocation hub location problem (USAHLP). We have proposed a hybrid heuristic for solving the USAHLP with competitive results obtained. In this note, an effective procedure to allocate the non-hubs to the capacitated hubs is developed to be embedded in the previous hybrid heuristic to solve the CSAHLP. Computational results show the presented heuristic is capable of obtaining optimal solutions for almost all small-scale problems and outperforms a simulated annealing algorithm from the literature in solving the large-scale CSAHLP. It is expected that this note can provide distribution managers an effective heuristic to design hub-and-spoke networks where the volume of traffic that a hub can collect is restricted.

Keywords: capacitated hub location problem; CHLP; p-hub median problem; uncapacitated hub location problem; UHLP; hub-and-spoke design; hub allocation.

DOI: 10.1504/IJAMS.2008.021101

International Journal of Applied Management Science, 2008 Vol.1 No.2, pp.198 - 216

Published online: 04 Nov 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article