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

作者：Ting Ching Jung^*; Wang Hung Jie

来源：Journal of the Chinese Institute of Engineers, 2014, 37(3): 300-312.

DOI：10.1080/02533839.2013.781797

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

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.

• 出版日期2014