The ring/κ-rings network design problem: Model and branch-and-cut algorithm

The ring/κ-rings network design problem: Model and branch-and-cut algorithm

0.00 Avg rating0 Votes
Article ID: iaor20162817
Volume: 68
Issue: 2
Start Page Number: 130
End Page Number: 140
Publication Date: Sep 2016
Journal: Networks
Authors: , ,
Keywords: design, combinatorial optimization
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 κ , thus resulting in a ring/ κ ‐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.

Reviews

Required fields are marked *. Your email address will not be published.