European Journal of Operational Research, ( ISI ), Volume (217), No (1), Year (2012-7) , Pages (17-25)

Title : ( An Integer Linear Programming based heuristic 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

We address the Capacitated m-Ring-Star Problem 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 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 algorithm which combines both heuristic and exact ideas to solve the problem. Following the general Variable Neighborhood Search scheme, the algorithm incorporates an Integer Linear Programming based improvement method which is applied whenever the heuristic algorithm is not able to improve 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 algorithm with the most effective methods from the literature. The results show that the proposed algorithm outperforms the other methods.

Keywords

, Network Optimization, Integer Linear Programming, Column Generation.
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

@article{paperid:1023039,
author = {Naji Azimi, Zahra and Salari, Majid and Paolo Toth},
title = {An Integer Linear Programming based heuristic for the Capacitated m-Ring-Star Problem},
journal = {European Journal of Operational Research},
year = {2012},
volume = {217},
number = {1},
month = {July},
issn = {0377-2217},
pages = {17--25},
numpages = {8},
keywords = {Network Optimization; Integer Linear Programming; Column Generation.},
}

[Download]

%0 Journal Article
%T An Integer Linear Programming based heuristic for the Capacitated m-Ring-Star Problem
%A Naji Azimi, Zahra
%A Salari, Majid
%A Paolo Toth
%J European Journal of Operational Research
%@ 0377-2217
%D 2012

[Download]