.png){kind=icon}
.png){kind=icon}
Return
An Integer Linear Programming based heuristic for the Capacitated m-Ring-Star Problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2011.08.026.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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. (C) 2011 Elsevier B.V. All rights reserved.
Keywords:
Capacitated m-Ring-Star Problem
Heuristic algorithms
Local search
Integer Linear Programming
Variable Neighborhood Search
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W