Heuristics for a hub location-routing problem

详细信息    查看全文

• 作者：Mauro Cardoso Lopes ; Carlos Eduardo de Andrade ; Thiago Alves de Queiroz ; Mauricio G. C. Resende and Flá ; vio Keidi Miyazawa
• 刊名：Networks
• 出版年：2016
• 出版时间：August 2016
• 年：2016
• 卷：68
• 期：1
• 页码：54-90
• 全文大小：3190K
• ISSN：1097-0037

文摘

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.