Título:
The capacitated m two node survivable star problem
Otros títulos:
Coordinador:
Director:
Compilador:
Autor:
Bayá Mantani, Gabriel
Mauttone, Antonio
Robledo, Franco
Mauttone, Antonio
Robledo, Franco
Tutor:
Tipo de documento:
Reporte técnico
Editor:
Palabras clave:
Topological network design
Survivability
Greedy randomized adataptive search procedure (GRASP)
Variable neigborhood search (VNS)
Metaheuristics
Survivability
Greedy randomized adataptive search procedure (GRASP)
Variable neigborhood search (VNS)
Metaheuristics
Descriptores:
Año de publicación:
2015
Contenido:
Resumen:
The problem addressed in this paper attempts to efficiently solve a network design with redundant connections, often used by telephone operators and internet services. This network connects customers with one master node and sets some 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) 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 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.
Descripción:
Editorial:
UR. FI – INCO.
EN:
Reportes Técnicos 15-11
Financiadores:
Citación:
Bayá, G., Mauttone, A., Robledo, F. "The capacitated m two node survivable star problem". Montevideo : UR. FI-INCO, 2015. Reportes Técnicos 15-11.
Citación:
metadata.cc.license.name:
Documento del Gobiberno:
URI:
http://hdl.handle.net/20.500.12008/5160
ISBN:
e-ISBN:
ISSN:
0797-6410
ISMN:
Otros identificadores:
Título Obtenido:
Facultad o Servicio que otorga el Título:
Licencia:
Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0)
Cobertura geográfica:
Cobertura temporal:
metadata.dc.relation.IsVersionOf:
Clasificación:
Es versión de:
Colecciones:
| Ficheros | Descripción | Tamaño | Formato | ||
|---|---|---|---|---|---|
| TR1511.pdf | — | 315.49 KB | Adobe PDF |