The 2-allocation p-hub median problem and a modified Benders decomposition method for solving hub location problems

Hamid Mokhtar, Mohan Krishnamoorthy, Andreas T. Ernst

Research output: Contribution to journalArticleResearchpeer-review

Abstract

We study the uncapacitated 2-allocation p-hub median problem (U2ApHMP), which is a special case of the well-studied hub median problem. The hub median problem designs a hub network in which the location of p hubs needs to be decided (the hubs are fully interconnected). The other nodes (known as access nodes) in the hub median problem are then allocated to one or many hubs. In the U2ApHMP, each access node is allocated to exactly two hubs. We discuss how this problem provides an alternative network design option for well-known p-hub median problems. We show its relevance and usefulness in the context of survivable network design and show that it addresses network survivability, a feature that has often been largely overlooked in hub network design research to date. We show that U2ApHMP is NP-hard even for a fixed/known set of hubs. We propose a mathematical formulation and develop a modified Benders decomposition method for this problem. In this, we convert the corresponding subproblems to minimum cost network flow problems. This allows us to solve large instances efficiently. We believe that, while our resulting method solves the U2ApHMP efficiently, it is also generalisable and can potentially be employed for solving other classes and types of hub location problems too.

Original languageEnglish
Pages (from-to)375-393
Number of pages19
JournalComputers and Operations Research
Volume104
DOIs
Publication statusPublished - Apr 2019

Keywords

  • Benders decomposition
  • Hub location
  • Location-allocation
  • p-hub median
  • Survivability

Cite this

@article{54d3e36f11934a298fd78481e04f8f4a,
title = "The 2-allocation p-hub median problem and a modified Benders decomposition method for solving hub location problems",
abstract = "We study the uncapacitated 2-allocation p-hub median problem (U2ApHMP), which is a special case of the well-studied hub median problem. The hub median problem designs a hub network in which the location of p hubs needs to be decided (the hubs are fully interconnected). The other nodes (known as access nodes) in the hub median problem are then allocated to one or many hubs. In the U2ApHMP, each access node is allocated to exactly two hubs. We discuss how this problem provides an alternative network design option for well-known p-hub median problems. We show its relevance and usefulness in the context of survivable network design and show that it addresses network survivability, a feature that has often been largely overlooked in hub network design research to date. We show that U2ApHMP is NP-hard even for a fixed/known set of hubs. We propose a mathematical formulation and develop a modified Benders decomposition method for this problem. In this, we convert the corresponding subproblems to minimum cost network flow problems. This allows us to solve large instances efficiently. We believe that, while our resulting method solves the U2ApHMP efficiently, it is also generalisable and can potentially be employed for solving other classes and types of hub location problems too.",
keywords = "Benders decomposition, Hub location, Location-allocation, p-hub median, Survivability",
author = "Hamid Mokhtar and Mohan Krishnamoorthy and Ernst, {Andreas T.}",
year = "2019",
month = "4",
doi = "10.1016/j.cor.2018.09.006",
language = "English",
volume = "104",
pages = "375--393",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier",

}

The 2-allocation p-hub median problem and a modified Benders decomposition method for solving hub location problems. / Mokhtar, Hamid; Krishnamoorthy, Mohan; Ernst, Andreas T.

In: Computers and Operations Research, Vol. 104, 04.2019, p. 375-393.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - The 2-allocation p-hub median problem and a modified Benders decomposition method for solving hub location problems

AU - Mokhtar, Hamid

AU - Krishnamoorthy, Mohan

AU - Ernst, Andreas T.

PY - 2019/4

Y1 - 2019/4

N2 - We study the uncapacitated 2-allocation p-hub median problem (U2ApHMP), which is a special case of the well-studied hub median problem. The hub median problem designs a hub network in which the location of p hubs needs to be decided (the hubs are fully interconnected). The other nodes (known as access nodes) in the hub median problem are then allocated to one or many hubs. In the U2ApHMP, each access node is allocated to exactly two hubs. We discuss how this problem provides an alternative network design option for well-known p-hub median problems. We show its relevance and usefulness in the context of survivable network design and show that it addresses network survivability, a feature that has often been largely overlooked in hub network design research to date. We show that U2ApHMP is NP-hard even for a fixed/known set of hubs. We propose a mathematical formulation and develop a modified Benders decomposition method for this problem. In this, we convert the corresponding subproblems to minimum cost network flow problems. This allows us to solve large instances efficiently. We believe that, while our resulting method solves the U2ApHMP efficiently, it is also generalisable and can potentially be employed for solving other classes and types of hub location problems too.

AB - We study the uncapacitated 2-allocation p-hub median problem (U2ApHMP), which is a special case of the well-studied hub median problem. The hub median problem designs a hub network in which the location of p hubs needs to be decided (the hubs are fully interconnected). The other nodes (known as access nodes) in the hub median problem are then allocated to one or many hubs. In the U2ApHMP, each access node is allocated to exactly two hubs. We discuss how this problem provides an alternative network design option for well-known p-hub median problems. We show its relevance and usefulness in the context of survivable network design and show that it addresses network survivability, a feature that has often been largely overlooked in hub network design research to date. We show that U2ApHMP is NP-hard even for a fixed/known set of hubs. We propose a mathematical formulation and develop a modified Benders decomposition method for this problem. In this, we convert the corresponding subproblems to minimum cost network flow problems. This allows us to solve large instances efficiently. We believe that, while our resulting method solves the U2ApHMP efficiently, it is also generalisable and can potentially be employed for solving other classes and types of hub location problems too.

KW - Benders decomposition

KW - Hub location

KW - Location-allocation

KW - p-hub median

KW - Survivability

UR - http://www.scopus.com/inward/record.url?scp=85054019269&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2018.09.006

DO - 10.1016/j.cor.2018.09.006

M3 - Article

VL - 104

SP - 375

EP - 393

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

ER -