← Search

Benders Decomposition for Large-Scale Uncapacitated Hub Location

Ivan Contreras¹; Jean-François Cordeau²; Gilbert Laporte²

¹ Concordia University and CIRRELT, Montréal H3G 1M8, Canada · ² HEC Montréal and CIRRELT, Montréal, H3T 2A7, Canada

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.

DOI

10.1287/opre.1110.0965

Volume

59 (6)

Pages

1477-1490

Language

en

Export

BibTeX

Sources

crossref