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. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1287/opre.1110.0965 | Operations Research |
Keywords | Field | DocType |
computational result,large-scale instance,classical benchmark instance,strong path-based formulation,strong optimality cut,large-scale uncapacitated hub location,benders decomposition,standard decomposition algorithm,difficult set,extensive computational experiment,heuristic procedure | Mathematical optimization,Exact algorithm,Algorithm,Robustness (computer science),Mathematics,Hub location problem,Benders' decomposition,Heuristic procedure | Journal |
Volume | Issue | ISSN |
59 | 6 | 0030-364X |
Citations | PageRank | References |
25 | 0.97 | 17 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ivan Contreras | 1 | 307 | 17.90 |
Jean-François Cordeau | 2 | 2604 | 127.77 |
Gilbert Laporte | 3 | 8666 | 612.13 |