Benders Decomposition Algorithms for Two Variants of the Single Allocation Hub Location Problem

Nader Ghaffarinasab () and Bahar Y. Kara ()
Additional contact information
Nader Ghaffarinasab: University of Tabriz
Bahar Y. Kara: Bilkent University

Networks and Spatial Economics, 2019, vol. 19, issue 1, No 4, 83-108

Abstract: Abstract The hub location problem (HLP) is a special type of the facility location problem with numerous applications in the airline industry, postal services, and computer and telecommunications networks. This paper addresses two basic variants of the HLP, namely the uncapacitated single allocation hub location problem (USAHLP) and the uncapacitated single allocation p-hub median problem (USAp HMP). Exact solution procedures based on Benders decomposition algorithm are proposed to tackle large sized instances of these problems. The standard Benders decomposition algorithm is enhanced through implementation of several algorithmic refinements such as using a new cut disaggregation scheme, generating strong optimality cuts, and an efficient algorithm to solve the dual subproblems. Furthermore, a modern implementation of the algorithm is used where a single search tree is established for the problem and Benders cuts are successively added within a branch-and-cut framework. Extensive computational experiments are conducted to examine the efficiency of the proposed algorithms. We have been able to solve all the instances of the problems from all three main data sets of the HLP to optimality in reasonable computational times.

Keywords: Hub location problem; Single allocation; Benders decomposition; Branch-and-cut; Algorithmic refinements (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1007/s11067-018-9424-z Abstract (text/html)
Access to full text is restricted to subscribers.

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:kap:netspa:v:19:y:2019:i:1:d:10.1007_s11067-018-9424-z

Ordering information: This journal article can be ordered from
http://www.springer. ... ce/journal/11067/PS2

DOI: 10.1007/s11067-018-9424-z

Access Statistics for this article

Networks and Spatial Economics is currently edited by Terry L. Friesz

More articles in Networks and Spatial Economics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().