Benders Decomposition for Large-Scale Uncapacitated Hub Location

Ivan Contreras (), Jean-François Cordeau () and Gilbert Laporte ()
Additional contact information
Ivan Contreras: Concordia University and CIRRELT, Montréal H3G 1M8, Canada
Jean-François Cordeau: HEC Montréal and CIRRELT, Montréal H3T 2A7, Canada
Gilbert Laporte: HEC Montréal and CIRRELT, Montréal H3T 2A7, Canada

Operations Research, 2011, vol. 59, issue 6, 1477-1490

Abstract: 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.

Keywords: hub location; Benders decomposition; Pareto-optimal cuts; elimination tests (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (58)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1110.0965 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:59:y:2011:i:6:p:1477-1490

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().