A threshold accepting algorithm for the uncapacitated single allocation hub location problem

Abstract

Hub location problem simultaneously determines the number and locations of hubs, and customer allocations. In this study, we tackle the uncapacitated single allocation hub location problem (USAHLP) that has no capacity constraint on hubs and all non-hub nodes must be allocated to a single hub so that the total flow cost is minimized. Since USAHLP is NP-hard, we propose a threshold accepting (TA) algorithm to solve the problem. Our algorithm was tested on two sets of benchmark instances, Civil Aeronautics Board and Australia Post (AP), and two sets of new larger and modified AP instances from the literature. The computational experiments and comparisons with other metaheuristics are reported. The results show that TA is competitive with other well-known algorithms and able to update numerous new best solutions.

Keywords:

• hub location
• single allocation
• hub-and-spoke networks
• threshold accepting

Acknowledgments

The authors wish to thank Professor Andreas T. Ernst for providing us the full AP data set and Dr Marcos R. Silva for providing new AP data set. We would also like to thank two anonymous referees for their helpful comments and suggestions on improving the presentation of this paper. This research was partially supported by a grant (NSC-98-2410-H-155-059) from the National Science Council of Taiwan.