3rd international conference of Iranian Operations Research Society , 2010-05-05

Title : ( A heuristic procedure for the capacitated m_ring star problem )

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

Access to full-text not allowed by authors

Citation: BibTeX | EndNote

Abstract

In this paper we propose a heuristic method to solve the Capacitated m-Ring-Star Problem which has many practical applications in communication networks. The problem consists of finding 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. In the proposed heuristic, after the construction phase, a series of different local search procedures are applied iteratively. This method incorporates some random aspects by perturbing the current solution through a “shaking” procedure which is applied whenever the algorithm remains in a local optimum for a given number of iterations. Computational experiments on the benchmark instances of the literature show that the proposed heuristic is able to obtain, most of the optimal solutions and can improve some of the best known results.

Keywords

, capacitated m_ring star problem, Heuristics
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

@inproceedings{paperid:1024991,
author = {Naji Azimi, Zahra and Salari, Majid and Paolo Toth},
title = {A heuristic procedure for the capacitated m_ring star problem},
booktitle = {3rd international conference of Iranian Operations Research Society},
year = {2010},
location = {تهران, IRAN},
keywords = {capacitated m_ring star problem; Heuristics},
}

[Download]

%0 Conference Proceedings
%T A heuristic procedure for the capacitated m_ring star problem
%A Naji Azimi, Zahra
%A Salari, Majid
%A Paolo Toth
%J 3rd international conference of Iranian Operations Research Society
%D 2010

[Download]