Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/326296
Type: Artigo
Title: Heuristics For A Hub Location-routing Problem
Author: Lopes
Mauro Cardoso; de Andrade
Carlos Eduardo; de Queiroz
Thiago Alves; Resende
Mauricio G. C.; Miyazawa
Flavio Keidi
Abstract: 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-andcut 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. (C) 2016 Wiley Periodicals, Inc.
Subject: Hub Location-routing Problem
Heuristics
Variable Neighborhood Descent
Biased Random-key Genetic Algorithm
Integer Formulation
Editor: Wiley-Blackwell
Hoboken
Rights: fechado
Identifier DOI: 10.1002/net.21685
Address: http://onlinelibrary-wiley-com.ez88.periodicos.capes.gov.br/doi/10.1002/net.21685/full
Date Issue: 2016
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
000379914900005.pdf3.19 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.