A Modified Benders Method for the Single- and Multiple Allocation P-Hub Median Problems

Hamid Mokhtar (), Mohan Krishnamoorthy and Andreas T. Ernst
Additional contact information
Hamid Mokhtar: Monash University
Mohan Krishnamoorthy: Monash University
Andreas T. Ernst: Monash University

A chapter in Operations Research Proceedings 2017, 2018, pp 135-141 from Springer

Abstract: Abstract We consider the well-known uncapacitated p-hub median problem with multiple allocation (UMApHMP), and single allocation (USApHMP). These problems have received significant attention in the literature because while they are easy to state and understand, they are hard to solve. They also find practical applications in logistics and telecommunication network design. Due to the inherent complexity of these problems, we apply a modified Benders decomposition method to solve large instances of the UMApHMP and USApHMP. The Benders decomposition approach does, however, suffer from slow convergence mainly due to the high degeneracy of subproblems. To resolve this, we apply a novel method of accelerating Benders method. We improve the performance of the accelerated Benders method by more appropriately choosing parameters for generating cuts, and by solving subproblems more efficiently using minimum cost network flow algorithms. We implement our approach on well-known benchmark data sets in the literature and compare our computational results for our implementations of existing methods and commercial solvers. The computational results confirms that our approach is efficient and enables us to solve larger single- and multiple allocation hub median instances. We believe this paper is the first implementation of Benders method to solve USA $$p$$ HMP and UMA $$p$$ HMP.

Keywords: Single allocation p-hub median problem; Multiple allocation p-hub median problem; Accelerated Benders decomposition method (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:oprchp:978-3-319-89920-6_19

Ordering information: This item can be ordered from
http://www.springer.com/9783319899206

DOI: 10.1007/978-3-319-89920-6_19

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().