Reformulations and Computational Results for the Uncapacitated Single Allocation Hub Covering Problem

Andreas Ernst; Houyuan Jiang; M Krishnamoorthy; Davaatseren Baatar

doi:10.1007/978-3-319-55914-8_10

Reformulations and Computational Results for the Uncapacitated Single Allocation Hub Covering Problem

Andreas Ernst, Houyuan Jiang, M Krishnamoorthy, Davaatseren Baatar

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research

Abstract

We study the single allocation hub covering problem, which is a special case of the general hub location problem and an important extension to traditional covering problems. Hubs are located at some nodes in the network and are used to facilitate (consolidate, transfer, distribute) flows. An important feature in hub location is that the transfer cost between hub nodes is discounted. The hub covering problem is to locate a minimum number of hubs such that the travel cost between each o–d pair in the network does not exceed a given threshold. We improve the best existing integer programming formulation for this problem by lifting constraints to produce facet-defining inequalities. We also develop a new formulation for the problem. The numerical results show that your new formulation performs better than existing formulations when using lifted constraints and paying special attention the number of non-zero coefficients used.

Original language	English
Title of host publication	Data and Decision Sciences in Action
Subtitle of host publication	Proceedings of the Australian Society for Operations Research Conference 2016
Editors	Ruhul Sarker, Hussein A Abbass, Simon Dunstall, Philip Kilby, Richard Davis, Leon Young
Place of Publication	Cham Switzerland
Publisher	Springer
Pages	113-148
Number of pages	16
ISBN (Electronic)	9783319559148
ISBN (Print)	9783319559131
DOIs	https://doi.org/10.1007/978-3-319-55914-8_10
Publication status	Published - 2018
Event	Australian Society for Operations Research Conference 2016 - Canberra, Australia Duration: 16 Nov 2016 → 18 Nov 2016 Conference number: 24th http://www.asor-act.net/ASORConf/

Publication series

Name	Lecture Notes in Management and Industrial Engineering
Publisher	Springer
ISSN (Print)	2198-0772
ISSN (Electronic)	2198-0780

Conference

Conference	Australian Society for Operations Research Conference 2016
Abbreviated title	ASOR 2016
Country/Territory	Australia
City	Canberra
Period	16/11/16 → 18/11/16
Other	The 24th ASOR Nation conference, 16-18 November 2016, Canberra
Internet address	http://www.asor-act.net/ASORConf/

Access to Document

10.1007/978-3-319-55914-8_10

Cite this

Ernst, A., Jiang, H., Krishnamoorthy, M., & Baatar, D. (2018). Reformulations and Computational Results for the Uncapacitated Single Allocation Hub Covering Problem. In R. Sarker, H. A. Abbass, S. Dunstall, P. Kilby, R. Davis, & L. Young (Eds.), Data and Decision Sciences in Action: Proceedings of the Australian Society for Operations Research Conference 2016 (pp. 113-148). (Lecture Notes in Management and Industrial Engineering). Springer. https://doi.org/10.1007/978-3-319-55914-8_10

Ernst, Andreas ; Jiang, Houyuan ; Krishnamoorthy, M et al. / Reformulations and Computational Results for the Uncapacitated Single Allocation Hub Covering Problem. Data and Decision Sciences in Action: Proceedings of the Australian Society for Operations Research Conference 2016. editor / Ruhul Sarker ; Hussein A Abbass ; Simon Dunstall ; Philip Kilby ; Richard Davis ; Leon Young. Cham Switzerland : Springer, 2018. pp. 113-148 (Lecture Notes in Management and Industrial Engineering).

@inproceedings{f266ab9ef43743a78950342399790c63,

title = "Reformulations and Computational Results for the Uncapacitated Single Allocation Hub Covering Problem",

abstract = "We study the single allocation hub covering problem, which is a special case of the general hub location problem and an important extension to traditional covering problems. Hubs are located at some nodes in the network and are used to facilitate (consolidate, transfer, distribute) flows. An important feature in hub location is that the transfer cost between hub nodes is discounted. The hub covering problem is to locate a minimum number of hubs such that the travel cost between each o–d pair in the network does not exceed a given threshold. We improve the best existing integer programming formulation for this problem by lifting constraints to produce facet-defining inequalities. We also develop a new formulation for the problem. The numerical results show that your new formulation performs better than existing formulations when using lifted constraints and paying special attention the number of non-zero coefficients used.",

author = "Andreas Ernst and Houyuan Jiang and M Krishnamoorthy and Davaatseren Baatar",

year = "2018",

doi = "10.1007/978-3-319-55914-8_10",

language = "English",

isbn = "9783319559131",

series = "Lecture Notes in Management and Industrial Engineering",

publisher = "Springer",

pages = "113--148",

editor = "Ruhul Sarker and Abbass, {Hussein A} and Simon Dunstall and Philip Kilby and Richard Davis and Leon Young",

booktitle = "Data and Decision Sciences in Action",

note = "Australian Society for Operations Research Conference 2016, ASOR 2016 ; Conference date: 16-11-2016 Through 18-11-2016",

url = "http://www.asor-act.net/ASORConf/",

}

Ernst, A, Jiang, H, Krishnamoorthy, M & Baatar, D 2018, Reformulations and Computational Results for the Uncapacitated Single Allocation Hub Covering Problem. in R Sarker, HA Abbass, S Dunstall, P Kilby, R Davis & L Young (eds), Data and Decision Sciences in Action: Proceedings of the Australian Society for Operations Research Conference 2016. Lecture Notes in Management and Industrial Engineering, Springer, Cham Switzerland, pp. 113-148, Australian Society for Operations Research Conference 2016, Canberra, Australian Capital Territory, Australia, 16/11/16. https://doi.org/10.1007/978-3-319-55914-8_10

Reformulations and Computational Results for the Uncapacitated Single Allocation Hub Covering Problem. / Ernst, Andreas; Jiang, Houyuan; Krishnamoorthy, M et al.
Data and Decision Sciences in Action: Proceedings of the Australian Society for Operations Research Conference 2016. ed. / Ruhul Sarker; Hussein A Abbass; Simon Dunstall; Philip Kilby; Richard Davis; Leon Young. Cham Switzerland: Springer, 2018. p. 113-148 (Lecture Notes in Management and Industrial Engineering).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research

TY - GEN

T1 - Reformulations and Computational Results for the Uncapacitated Single Allocation Hub Covering Problem

AU - Ernst, Andreas

AU - Jiang, Houyuan

AU - Krishnamoorthy, M

AU - Baatar, Davaatseren

N1 - Conference code: 24th

PY - 2018

Y1 - 2018

N2 - We study the single allocation hub covering problem, which is a special case of the general hub location problem and an important extension to traditional covering problems. Hubs are located at some nodes in the network and are used to facilitate (consolidate, transfer, distribute) flows. An important feature in hub location is that the transfer cost between hub nodes is discounted. The hub covering problem is to locate a minimum number of hubs such that the travel cost between each o–d pair in the network does not exceed a given threshold. We improve the best existing integer programming formulation for this problem by lifting constraints to produce facet-defining inequalities. We also develop a new formulation for the problem. The numerical results show that your new formulation performs better than existing formulations when using lifted constraints and paying special attention the number of non-zero coefficients used.

AB - We study the single allocation hub covering problem, which is a special case of the general hub location problem and an important extension to traditional covering problems. Hubs are located at some nodes in the network and are used to facilitate (consolidate, transfer, distribute) flows. An important feature in hub location is that the transfer cost between hub nodes is discounted. The hub covering problem is to locate a minimum number of hubs such that the travel cost between each o–d pair in the network does not exceed a given threshold. We improve the best existing integer programming formulation for this problem by lifting constraints to produce facet-defining inequalities. We also develop a new formulation for the problem. The numerical results show that your new formulation performs better than existing formulations when using lifted constraints and paying special attention the number of non-zero coefficients used.

U2 - 10.1007/978-3-319-55914-8_10

DO - 10.1007/978-3-319-55914-8_10

M3 - Conference Paper

SN - 9783319559131

T3 - Lecture Notes in Management and Industrial Engineering

SP - 113

EP - 148

BT - Data and Decision Sciences in Action

A2 - Sarker, Ruhul

A2 - Abbass, Hussein A

A2 - Dunstall, Simon

A2 - Kilby, Philip

A2 - Davis, Richard

A2 - Young, Leon

PB - Springer

CY - Cham Switzerland

T2 - Australian Society for Operations Research Conference 2016

Y2 - 16 November 2016 through 18 November 2016

ER -

Ernst A, Jiang H, Krishnamoorthy M, Baatar D. Reformulations and Computational Results for the Uncapacitated Single Allocation Hub Covering Problem. In Sarker R, Abbass HA, Dunstall S, Kilby P, Davis R, Young L, editors, Data and Decision Sciences in Action: Proceedings of the Australian Society for Operations Research Conference 2016. Cham Switzerland: Springer. 2018. p. 113-148. (Lecture Notes in Management and Industrial Engineering). doi: 10.1007/978-3-319-55914-8_10