A biased random-key genetic algorithm for the tree of hubs location problem

L.S. Pessoa, A. C. Santos, and M. G. C. Resende

Optimization Letters, vol. 11, pp. 1371-1384, 2017

ABSTRACT

Hubs are facilities used to treat and dispatch resources in a transportation network. The main idea of Hub Location Problems (HLP) is to locate a number of hubs in a network and route resources from origins to destinations such that the total cost of attending all demands is minimized. In this study, we investigate a particular HLP, called the Tree of Hubs Location Problem in which hubs are connected by means of a tree and the overall network infrastructure relies on a spanning tree. This problem is particularly interesting when the total cost of building the hub backbone is high. In this paper, we propose a biased random key genetic algorithm for solving the tree of hubs location problem. Computational results show that the proposed heuristic is a robust and effective method to tackle this problem. The method was able to improve some best known solutions from the benchmark instances used in the experiments.

PDF file of full paper

Mauricio G.C. Resende's Home Page