A multi-start iterated local search algorithm for the uncapacitated single allocation hub location problem

The uncapacitated single allocation hub location problem (USAHLP) is a particular variant of the hub location problem, which has broad applications in the transportation network. The objective of USAHLP is to minimize the sum of transportation cost and fixed cost. In this paper, a multi-start iterated local search algorithm (MSLSA) is proposed for solving the USAHLP. Firstly, a randomized greedy construction procedure is built to generate initial solutions with good quality. Then, solutions are improved by an iterated local search, which consists of promising solutions selection and improvement on nodes reallocation. Meanwhile, a perturbation mechanism helps the search to escape from local optima and explore new promising regions. Our proposed algorithm is evaluated on four USAHLP data sets and compared with two state-of-the-art algorithms. The experimental results demonstrate the high competitiveness of our proposed MSLSA in terms of both solution quality and computational efficiency. MSLSA achieves the same solutions for multiple runs on each instance, which highlights the advantage of MSLSA in terms of solution robustness and stability. With the high solution quality and the rapid running speed, the proposed algorithm could be a promising tool for other hub location problems.