A Threshold Accepting Algorithm for the Uncapacitated Single Allocation p-Hub Median Problem

概要

論文の詳細を見る
Hub facilities serve as transshipment and switching points in transportation and telecommunication networks. This paper deals with the uncapacitated single allocation p-hub median problem (USApHMP), which is a well known NP-hard problem. Few studies applied simulated annealing (SA), tabu search (TS), and genetic algorithm (GA) to solve the problem in the past decades. A threshold accepting (TA) algorithm is proposed for solving the USApHMP. The numerical experiments were carried out on two sets of benchmark instances, CAB and AP, from the literature. The results show that our TA algorithm is efficient and competitive with other approaches. TA can obtain all the optimal solutions in the CAB data set and update two best-known solutions of large instances in the AP data set.