A multi-start heuristic for the design of hub-and-spoke networks

Citation:

Rodrigo de Carvalho, Bruno Nonato Gomes, Alexandre Xavier Martins, Rodney Rezende Saldanha, and Ricardo Saraiva de Camargo. 2017. “A multi-start heuristic for the design of hub-and-spoke networks.” Proceeding Series of the Brazilian Society of Computational and Applied Mathematics, 5, 1. Publisher's Version

Abstract:

Design of Hub-and-spoke networks is an extension of classical facility location problem and it is very important due to its applications in cargo, passenger and telecommunication systems. The problem consists in determining the number and location of the hubs, besides define the allocation of non-hub nodes to the installed hubs, aiming to minimize the total costs. This problem is known to be NP-hard and it has been tackled by heuristic based approaches. In this paper it is proposed an efficient multi-start heuristic composed by a simple construction phase, a perturbation mechanism and an adaptive local search. Computational experiments using standard benchmark problems shows that the proposed approach is competitive when compared with the best heuristics in the literature.