European Journal of Operational Research, ( ISI ), Volume (207), No (3), Year (2010-12) , Pages (1227-1234)

Title : ( A heuristic procedure for the Capacitated m-Ring-Star problem )

Authors: Zahra Naji Azimi , Majid Salari , Paolo Toth ,

Access to full-text not allowed by authors

Citation: BibTeX | EndNote


In this paper we propose a heuristic method to solve the Capacitated m-Ring-Star Problem which has many practical applications in communication networks. The problem consists of finding m rings (simple cycles) visiting a central depot, a subset of customers and a subset of potential (Steiner) nodes, while customers not belonging to any ring must be “allocated” to a visited (customer or Steiner) node. Moreover, the rings must be node-disjoint and the number of customers allocated or visited in a ring cannot be greater than the capacity Q given as an input parameter. The objective is to minimize the total visiting and allocation costs. The problem is a generalization of the Traveling Salesman Problem, hence it is NP-hard. In the proposed heuristic, after the construction phase, a series of different local search procedures are applied iteratively. This method incorporates some random aspects by perturbing the current solution through a “shaking” procedure which is applied whenever the algorithm remains in a local optimum for a given number of iterations. Computational experiments on the benchmark instances of the literature show that the proposed heuristic is able to obtain, within a short computing time, most of the optimal solutions and can improve some of the best known results.


, Capacitated m-Ring-Star problem, Heuristic Algorithms, Networks
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

author = {Naji Azimi, Zahra and Salari, Majid and Paolo Toth},
title = {A heuristic procedure for the Capacitated m-Ring-Star problem},
journal = {European Journal of Operational Research},
year = {2010},
volume = {207},
number = {3},
month = {December},
issn = {0377-2217},
pages = {1227--1234},
numpages = {7},
keywords = {Capacitated m-Ring-Star problem; Heuristic Algorithms; Networks},


%0 Journal Article
%T A heuristic procedure for the Capacitated m-Ring-Star problem
%A Naji Azimi, Zahra
%A Salari, Majid
%A Paolo Toth
%J European Journal of Operational Research
%@ 0377-2217
%D 2010