| Article ID: | iaor20162814 |
| Volume: | 68 |
| Issue: | 1 |
| Start Page Number: | 54 |
| End Page Number: | 90 |
| Publication Date: | Aug 2016 |
| Journal: | Networks |
| Authors: | Resende Mauricio G C, Lopes Mauro Cardoso, de Andrade Carlos Eduardo, de Queiroz Thiago Alves, Miyazawa Flvio Keidi |
| Keywords: | networks, combinatorial optimization, heuristics, heuristics: genetic algorithms, heuristics: local search |
We investigate a variant of the many‐to‐many hub location‐routing problem which consists in partitioning the set of nodes of a graph into routes containing exactly one hub each, and determining an extra route interconnecting all hubs. A variable neighborhood descent with neighborhood structures based on remove/add, swap and exchange moves nested with routing and location operations is used as a local search procedure in a multistart algorithm. We also consider a sequential version of this local search in the multistart. In addition, a biased random‐key genetic algorithm working with a local search routine, which also considers routing and location operations, is applied to the problem. To compare the heuristic solutions, we develop an integer programming formulation which is solved with a branch‐and‐cut algorithm. Capacity and path elimination constraints are added in a cutting plane fashion. The separation algorithms are based on the computation of min‐cut trees and on the connected components of a support graph. Computational experiments were conducted on several benchmark instances of routing problems and show that the heuristics are effective on medium to large‐sized instances, while the branch‐and‐cut algorithm solves small to medium sized problems to optimality. These algorithms were also compared with a commercial hybrid solver showing that the heuristics are quite competitive.