Exact solution of large-scale hub location problems with multiple capacity levels

Ivan Contreras, Jean François Cordeau, Gilbert Laporte

Research output: Contribution to journalArticle

34 Citations (Scopus)

Abstract

This paper presents an extension of the classical capacitated hub location problem with multiple assignments in which the amount of capacity installed at the hubs is part of the decision process. An exact algorithm based on a Benders decomposition of a strong path-based formulation is proposed to solve large-scale instances of two variants of the problem: the splittable and nonsplittable commodities cases. The standard decomposition algorithm is enhanced through the inclusion of features such as the generation of strong optimality cuts and the integration of reduction tests. Given that in the nonsplittable case the resulting subproblem is an integer program, we develop an efficient enumeration algorithm. Extensive computational experiments are performed to evaluate the efficiency and robustness of the proposed algorithms. Computational results obtained on benchmark instances with up to 300 nodes and five capacity levels confirm their efficiency.

Original languageEnglish
Pages (from-to)439-459
Number of pages21
JournalTransportation Science
Volume46
Issue number4
DOIs
Publication statusPublished - Nov 2012

Keywords

  • Benders decomposition
  • Elimination tests
  • Hub location
  • Pareto-optimal cuts

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation

Cite this