Exact and heuristic approaches for the cycle hub location problem

Ivan Contreras (), Moayad Tanash and Navneet Vidyarthi
Additional contact information
Ivan Contreras: Concordia University and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT)
Moayad Tanash: Concordia University and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT)
Navneet Vidyarthi: Concordia University and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT)

Annals of Operations Research, 2017, vol. 258, issue 2, No 21, 655-677

Abstract: Abstract In this paper, we present solution algorithms for the cycle hub location problem (CHLP), which seeks to locate p hub facilities that are connected by means of a cycle, and to assign non-hub nodes to hubs so as to minimize the total cost of routing flows through the network. This problem is useful in modeling applications in transportation and telecommunications systems, where large setup costs on the links and reliability requirements make cycle topologies a prominent network architecture. We present a branch-and-cut algorithm that uses a flow-based formulation and two families of mixed-dicut inequalities as a lower bounding procedure at nodes of the enumeration tree. We also introduce a metaheuristic based on greedy randomized adaptive search procedure to obtain initial upper bounds for the exact algorithm and to obtain feasible solutions for large-scale instances of the CHLP. Numerical results on a set of benchmark instances with up to 100 nodes and 8 hubs confirm the efficiency of the proposed solution algorithms.

Keywords: Hub location; Cycles; Branch-and-cut; GRASP (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-015-2091-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:annopr:v:258:y:2017:i:2:d:10.1007_s10479-015-2091-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-015-2091-2

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

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