Home > Research > Publications & Outputs > The ring/k-rings network design problem

Research

Links

Text available via DOI:

Keywords

View graph of relations

The ring/k-rings network design problem: model and branch-and-cut algorithm

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

The ring/k-rings network design problem: model and branch-and-cut algorithm. / Rodriguez-Martin, Inmaculada; Salazar-Gonzalez, Juan-Jose; Yaman, Hande.
In: Networks, Vol. 68, No. 2, 09.2016, p. 130-140.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Rodriguez-Martin, I, Salazar-Gonzalez, J-J & Yaman, H 2016, 'The ring/k-rings network design problem: model and branch-and-cut algorithm', Networks, vol. 68, no. 2, pp. 130-140. https://doi.org/10.1002/net.21687

APA

Rodriguez-Martin, I., Salazar-Gonzalez, J-J., & Yaman, H. (2016). The ring/k-rings network design problem: model and branch-and-cut algorithm. Networks, 68(2), 130-140. https://doi.org/10.1002/net.21687

Vancouver

Rodriguez-Martin I, Salazar-Gonzalez J-J, Yaman H. The ring/k-rings network design problem: model and branch-and-cut algorithm. Networks. 2016 Sept;68(2):130-140. doi: 10.1002/net.21687

Author

Rodriguez-Martin, Inmaculada ; Salazar-Gonzalez, Juan-Jose ; Yaman, Hande. / The ring/k-rings network design problem : model and branch-and-cut algorithm. In: Networks. 2016 ; Vol. 68, No. 2. pp. 130-140.

Bibtex

@article{edd87926312c45c1a63f9208e7f77bcb,
title = "The ring/k-rings network design problem: model and branch-and-cut algorithm",
abstract = "This article considers the problem of designing a two‐level network where the upper level consists of a backbone ring network connecting the so‐called hub nodes, and the lower level is formed by access ring networks that connect the non‐hub nodes to the hub nodes. There is a fixed cost for each type of link, and a facility opening cost associated to each hub. The number of nodes in each access ring is bounded, and the number of access rings connected to a hub is limited to urn:x-wiley:00283045:media:net21687:net21687-math-0001, thus resulting in a ring/ urn:x-wiley:00283045:media:net21687:net21687-math-0002‐rings topology. The aim is to decide the hubs to open and to design the backbone and access rings to minimize the installation cost. We propose a mathematical model, give valid inequalities, and describe a branch‐and‐cut algorithm to solve the problem. Computational results show the algorithm is able to find optimal solutions on instances involving up to 40 nodes within a reasonable time. ",
keywords = "network design, ring networks, valid inequalities, branch-and-cut",
author = "Inmaculada Rodriguez-Martin and Juan-Jose Salazar-Gonzalez and Hande Yaman",
year = "2016",
month = sep,
doi = "10.1002/net.21687",
language = "English",
volume = "68",
pages = "130--140",
journal = "Networks",
issn = "0028-3045",
publisher = "Blackwell-Wiley",
number = "2",

}

RIS

TY - JOUR

T1 - The ring/k-rings network design problem

T2 - model and branch-and-cut algorithm

AU - Rodriguez-Martin, Inmaculada

AU - Salazar-Gonzalez, Juan-Jose

AU - Yaman, Hande

PY - 2016/9

Y1 - 2016/9

N2 - This article considers the problem of designing a two‐level network where the upper level consists of a backbone ring network connecting the so‐called hub nodes, and the lower level is formed by access ring networks that connect the non‐hub nodes to the hub nodes. There is a fixed cost for each type of link, and a facility opening cost associated to each hub. The number of nodes in each access ring is bounded, and the number of access rings connected to a hub is limited to urn:x-wiley:00283045:media:net21687:net21687-math-0001, thus resulting in a ring/ urn:x-wiley:00283045:media:net21687:net21687-math-0002‐rings topology. The aim is to decide the hubs to open and to design the backbone and access rings to minimize the installation cost. We propose a mathematical model, give valid inequalities, and describe a branch‐and‐cut algorithm to solve the problem. Computational results show the algorithm is able to find optimal solutions on instances involving up to 40 nodes within a reasonable time.

AB - This article considers the problem of designing a two‐level network where the upper level consists of a backbone ring network connecting the so‐called hub nodes, and the lower level is formed by access ring networks that connect the non‐hub nodes to the hub nodes. There is a fixed cost for each type of link, and a facility opening cost associated to each hub. The number of nodes in each access ring is bounded, and the number of access rings connected to a hub is limited to urn:x-wiley:00283045:media:net21687:net21687-math-0001, thus resulting in a ring/ urn:x-wiley:00283045:media:net21687:net21687-math-0002‐rings topology. The aim is to decide the hubs to open and to design the backbone and access rings to minimize the installation cost. We propose a mathematical model, give valid inequalities, and describe a branch‐and‐cut algorithm to solve the problem. Computational results show the algorithm is able to find optimal solutions on instances involving up to 40 nodes within a reasonable time.

KW - network design

KW - ring networks

KW - valid inequalities

KW - branch-and-cut

U2 - 10.1002/net.21687

DO - 10.1002/net.21687

M3 - Journal article

VL - 68

SP - 130

EP - 140

JO - Networks

JF - Networks

SN - 0028-3045

IS - 2

ER -