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

Keywords