Benders Decomposition for Large-Scale Uncapacitated Hub Location

• 成果类型: Article
• 署名作者: Contreras, Ivan; Cordeau, Jean-Francois; Laporte, Gilbert
• 署名单位: Concordia University - Canada; Universite de Montreal; Universite de Montreal; HEC Montreal; Universite de Montreal
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1110.0965
• 发表日期: 2011
• 页码: 1477-1490
• 关键词: formulations

摘要

This paper describes an exact algorithm capable of solving large-scale instances of the well-known uncapacitated hub location problem with multiple assignments. The algorithm applies Benders decomposition to a strong path-based formulation of the problem. The standard decomposition algorithm is enhanced through the inclusion of several features such as the use of a multicut reformulation, the generation of strong optimality cuts, the integration of reduction tests, and the execution of a heuristic procedure. Extensive computational experiments were performed to evaluate the efficiency and robustness of the algorithm. Computational results obtained on classical benchmark instances (with up to 200 nodes) and on a new and more difficult set of instances (with up to 500 nodes) confirm the efficiency of the algorithm.