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.

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

TOTH, PAOLO
2010

Abstract

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.
ELECTRONIC NOTES IN DISCRETE MATHEMATICS
M. Salari; Z. Naji-Azimi; P. Toth
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/100077
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact