Geodesic
The Capacitated $m$ Two Node Survivable Star Problem
Yugoslav journal of operations research, Tome 27 (2017) no. 3, p. 341 Cet article a éte moissonné depuis la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

Voir la notice de l'article

In this paper, we address the problem of network design with redundant connections, often faced by operators of telephone and internet services. The network connects customers with one master node and is built by taking into account the rules that shape its construction, such as number of customers, number of components and types of links, in order to meet operational needs and technical constraints. We propose a combinatorial optimization problem called CmTNSSP (Capacitated $m$ Two-Node-Survivable Star Problem), a relaxation of CmRSP (Capacitated $m$ Ring Star Problem). In this variant of CmRSP, the rings are not constrained to be cycles; instead, they can be two-node connected components. The contributions of this paper are: (a) the introduction and definition of a new problem, (b) the specification of a mathematical programming model of the problem to be treated, and (c) the approximate resolution thereof through a GRASP metaheuristic, which alternates local searches that obtain incrementally better solutions, and exact resolution local searches based on mathematical programming models, particularly Integer Linear Programming ones. Computational results obtained by the developed algorithms show robustness and competitiveness when compared to results of the literature relative to benchmark instances. Likewise, the experiments show the relevance of considering the specific variant of the problem studied in this work.
Classification : 90B06, 90C05, 90C08
Keywords: Topological Network Design, Survivability, Greedy Randomized Adaptive Search Procedure (GRASP), Variable Neighborhood Search (VNS), Metaheuristics 
@article{YJOR_2017_27_3_a4,
     author = {Gabriel Bay\'a and Antonio Mauttone and Franco Robledo},
     title = {The {Capacitated} $m$ {Two} {Node} {Survivable} {Star} {Problem}},
     journal = {Yugoslav journal of operations research},
     pages = {341 },
     year = {2017},
     volume = {27},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2017_27_3_a4/}
}
TY  - JOUR
AU  - Gabriel Bayá
AU  - Antonio Mauttone
AU  - Franco Robledo
TI  - The Capacitated $m$ Two Node Survivable Star Problem
JO  - Yugoslav journal of operations research
PY  - 2017
SP  - 341 
VL  - 27
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/YJOR_2017_27_3_a4/
LA  - en
ID  - YJOR_2017_27_3_a4
ER  - 
%0 Journal Article
%A Gabriel Bayá
%A Antonio Mauttone
%A Franco Robledo
%T The Capacitated $m$ Two Node Survivable Star Problem
%J Yugoslav journal of operations research
%D 2017
%P 341 
%V 27
%N 3
%U http://geodesic.mathdoc.fr/item/YJOR_2017_27_3_a4/
%G en
%F YJOR_2017_27_3_a4
Gabriel Bayá; Antonio Mauttone; Franco Robledo. The Capacitated $m$ Two Node Survivable Star Problem. Yugoslav journal of operations research, Tome 27 (2017) no. 3, p. 341 . http://geodesic.mathdoc.fr/item/YJOR_2017_27_3_a4/