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, most of the optimal solutions and can improve some of the best known results.

Keywords