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

Rodrigo de Carvalho, Bruno Gomes, Alexandre Martins, Rodney Saldanha, Ricardo de Camargo


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.


Hub-and-spoke networks, heuristics, combinatorial optimization.

Texto completo:


DOI: https://doi.org/10.5540/03.2017.005.01.0471


  • Não há apontamentos.

SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120

Normas para publicação | Contato