Electronic Notes in Discrete Mathematics, Volume (36), No (1), Year (2010-8) , Pages (343-350)

Title : ( A Variable Neighborhood Search and its Application to a Ring Star Problem Generalization )

Authors: Majid Salari , Zahra Naji Azimi , Paolo Toth ,

Access to full-text not allowed by authors

Citation: BibTeX | EndNote

Abstract

We address the Capacitated m-Ring-Star Problem (CmRSP) in which the goal 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 a capacity Q. 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 heuristic approach based on a Variable Neighborhood Search (VNS), that incorporates an Integer Linear Programming (ILP) based improvement procedure. Preliminary computational results, performed to compare the proposed VNS method with existing algorithms for CmRSP, shows that the proposed method can obtain slightly better results but in a larger CPU time.

Keywords

, Capacitated m-Ring-Star Problem, Variable Neighborhood Search, Integer Linear Programming, Networks
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

@article{paperid:1022370,
author = {Salari, Majid and Naji Azimi, Zahra and Paolo Toth},
title = {A Variable Neighborhood Search and its Application to a Ring Star Problem Generalization},
journal = {Electronic Notes in Discrete Mathematics},
year = {2010},
volume = {36},
number = {1},
month = {August},
issn = {1571-0653},
pages = {343--350},
numpages = {7},
keywords = {Capacitated m-Ring-Star Problem; Variable Neighborhood Search; Integer Linear Programming; Networks},
}

[Download]

%0 Journal Article
%T A Variable Neighborhood Search and its Application to a Ring Star Problem Generalization
%A Salari, Majid
%A Naji Azimi, Zahra
%A Paolo Toth
%J Electronic Notes in Discrete Mathematics
%@ 1571-0653
%D 2010

[Download]