Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
A Variable Neighborhood Search Approach for the Capacitated m-Ring-Star Problem
verfasst von : Carlos Franco, Eduyn López-Santana, Germán Mendez-Giraldo
Erschienen in: Intelligent Computing Theories and Application
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.