Exact Solution of Large-Scale Hub Location Problems with Multiple Capacity Levels

Ivan Contreras (), Jean-François Cordeau () and Gilbert Laporte ()
Additional contact information
Ivan Contreras: Concordia University and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montréal, Quebec H3T 2A7, Canada
Jean-François Cordeau: HEC Montréal and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montréal, Quebec H3T 2A7, Canada
Gilbert Laporte: HEC Montréal and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montréal, Quebec H3T 2A7, Canada

Transportation Science, 2012, vol. 46, issue 4, 439-459

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.

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

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1110.0398 (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:ortrsc:v:46:y:2012:i:4:p:439-459

Access Statistics for this article

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