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.
Original language | English |
---|---|
Pages (from-to) | 1477-1490 |
Number of pages | 14 |
Journal | Operations Research |
Volume | 59 |
Issue number | 6 |
DOIs | |
Publication status | Published - Nov 2011 |
Keywords
- Benders decomposition
- Elimination tests
- Hub location
- Pareto-optimal cuts
ASJC Scopus subject areas
- Computer Science Applications
- Management Science and Operations Research