We address the Capacitated m-Ring-Star Problem in which the aim is to nd 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 a given capacity Q. The objective is to minimize the total visiting and allocation costs. The Capacitated m-Ring-Star Problem is NP-hard, since it generalizes the Traveling Salesman Problem. In this paper we propose a new heuristic approach which combines both heuristic and exact ideas to solve the problem. Considering the general scheme of the Variable Neighborhood Search approach, the algorithm incorporates an Integer Linear Programming based improvement method which is applied whenever the heuristic procedure is not able to enhance the quality of the current solution. Extensive computational experiments, on benchmark instances of the literature and on a new set of instances, have been performed to compare the proposed approach with the most eective methods from the literature. The results show that the proposed algorithm outperforms the other approaches.

Keywords