TY - GEN
T1 - A variable neighborhood search approach for the capacitated m-Ring-Star problem
AU - Franco, Carlos
AU - López-Santana, Eduyn
AU - Mendez-Giraldo, Germán
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2016.
PY - 2016
Y1 - 2016
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.
UR - http://www.scopus.com/inward/record.url?scp=84978880055&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84978880055&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-42291-6_1
DO - 10.1007/978-3-319-42291-6_1
M3 - Conference contribution
AN - SCOPUS:84978880055
SN - 9783319422909
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 3
EP - 11
BT - Intelligent Computing Theories and Application - 12th International Conference, ICIC 2016, Proceedings
A2 - Premaratne, Prashan
A2 - Huang, De-Shuang
A2 - Bevilacqua, Vitoantonio
PB - Springer
T2 - 12th International Conference on Intelligent Computing Theories and Application, ICIC 2016
Y2 - 2 August 2016 through 5 August 2016
ER -