A Variable Neighborhood Search Approach for the Capacitated m-Ring-Star Problem

Carlos Alberto Franco Franco, eduyn ramiro Lopéz-Santana, Germán Andrés Mendez Giraldo

Resultado de la investigación: Contribución a RevistaArtículo

Resumen

In this paper, we proposed an algorithm based on variable neighborhood search (VNS) for the capacitated m-Ring-Star problem. This problem has several real applications in communications networks, rapid transit system planning and optical fiber networks. The problem consists in design m rings or cycles that begins of a central depot and visits a set of customers and transition or steiner nodes. While the nodes don’t belong to a ring these must be allocated or assign to a customer or steiner node that belongs to a ring. The number of customers allocated or visited in each ring must not exceed the maximum capacity. The goal is to minimize the visiting and allocation cost. For solving the problem, we propose a VNS approach based on random perturbation for escaping from the local optimal solutions. Our method reached the optimal solution in a reasonable amount of time in a set of instances from the literature.
Idioma originalEnglish (US)
Páginas (desde-hasta)3-11
Número de páginas9
PublicaciónLecture Notes in Computer Science
Volumen9771
EstadoPublished - jul 12 2016

Huella dactilar

Rapid transit
Variable Neighborhood Search
Telecommunication networks
Stars
Optical fibers
Star
Ring
Planning
Customers
Costs
Vertex of a graph
Optimal Solution
Cost Allocation
Random Perturbation
Communication Networks
Optical Fiber
Assign
Exceed
Minimise
Cycle

Citar esto

Franco Franco, Carlos Alberto ; Lopéz-Santana, eduyn ramiro ; Mendez Giraldo, Germán Andrés . / A Variable Neighborhood Search Approach for the Capacitated m-Ring-Star Problem. En: Lecture Notes in Computer Science. 2016 ; Vol. 9771. pp. 3-11.
@article{cceeac7716fb4ffeba950072267eb2c6,
title = "A Variable Neighborhood Search Approach for the Capacitated m-Ring-Star Problem",
abstract = "In this paper, we proposed an algorithm based on variable neighborhood search (VNS) for the capacitated m-Ring-Star problem. This problem has several real applications in communications networks, rapid transit system planning and optical fiber networks. The problem consists in design m rings or cycles that begins of a central depot and visits a set of customers and transition or steiner nodes. While the nodes don’t belong to a ring these must be allocated or assign to a customer or steiner node that belongs to a ring. The number of customers allocated or visited in each ring must not exceed the maximum capacity. The goal is to minimize the visiting and allocation cost. For solving the problem, we propose a VNS approach based on random perturbation for escaping from the local optimal solutions. Our method reached the optimal solution in a reasonable amount of time in a set of instances from the literature.",
author = "{Franco Franco}, {Carlos Alberto} and Lop{\'e}z-Santana, {eduyn ramiro} and {Mendez Giraldo}, {Germ{\'a}n Andr{\'e}s}",
year = "2016",
month = "7",
day = "12",
language = "English (US)",
volume = "9771",
pages = "3--11",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Springer",

}

A Variable Neighborhood Search Approach for the Capacitated m-Ring-Star Problem. / Franco Franco, Carlos Alberto; Lopéz-Santana, eduyn ramiro; Mendez Giraldo, Germán Andrés .

En: Lecture Notes in Computer Science, Vol. 9771, 12.07.2016, p. 3-11.

Resultado de la investigación: Contribución a RevistaArtículo

TY - JOUR

T1 - A Variable Neighborhood Search Approach for the Capacitated m-Ring-Star Problem

AU - Franco Franco, Carlos Alberto

AU - Lopéz-Santana, eduyn ramiro

AU - Mendez Giraldo, Germán Andrés

PY - 2016/7/12

Y1 - 2016/7/12

N2 - In this paper, we proposed an algorithm based on variable neighborhood search (VNS) for the capacitated m-Ring-Star problem. This problem has several real applications in communications networks, rapid transit system planning and optical fiber networks. The problem consists in design m rings or cycles that begins of a central depot and visits a set of customers and transition or steiner nodes. While the nodes don’t belong to a ring these must be allocated or assign to a customer or steiner node that belongs to a ring. The number of customers allocated or visited in each ring must not exceed the maximum capacity. The goal is to minimize the visiting and allocation cost. For solving the problem, we propose a VNS approach based on random perturbation for escaping from the local optimal solutions. Our method reached the optimal solution in a reasonable amount of time in a set of instances from the literature.

AB - In this paper, we proposed an algorithm based on variable neighborhood search (VNS) for the capacitated m-Ring-Star problem. This problem has several real applications in communications networks, rapid transit system planning and optical fiber networks. The problem consists in design m rings or cycles that begins of a central depot and visits a set of customers and transition or steiner nodes. While the nodes don’t belong to a ring these must be allocated or assign to a customer or steiner node that belongs to a ring. The number of customers allocated or visited in each ring must not exceed the maximum capacity. The goal is to minimize the visiting and allocation cost. For solving the problem, we propose a VNS approach based on random perturbation for escaping from the local optimal solutions. Our method reached the optimal solution in a reasonable amount of time in a set of instances from the literature.

M3 - Article

VL - 9771

SP - 3

EP - 11

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -