A Variable Neighborhood Search and its Application to a Ring Star Problem Generalization

We address the Capacitated m-Ring-Star Problem (CmRSP) in which the aim is to find 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. We present a new approach based on Variable Neighborhood search (VNS), also incorporate the algorithm with an Integer Linear Programming (ILP) based improvement procedure to enhance the quality of the solutions. Comparing the proposed VNS method with the best state-of-the-art algorithms for the CmRSP on a large variety of instances, clearly shows the superiority of the proposed approach.