This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Baldacci, R. Articles by González, J. S. Search for Related Content

The Capacitated m-Ring-Star Problem

Dipartimento di Elettronica, Informatica e Sistemistica, University of Bologna, 47023 Cesena, Italy
Dipartimento di Scienze e Metodi dell'Ingegneria, University of Modena and Reggio Emilia, 42100 Reggio Emilia, Italy
Departamento de Estadistica, Investigacíon Operativa y Computacíon, Facultad de Matemáticas, Universidad de La Laguna, 38271 La Laguna, Tenerife, Spain
rbaldacci{at}deis.unibo.it
dellamico{at}unimore.it
jjsalaza{at}ull.es

The Capacitated m-Ring-Star Problem (CmRSP) is the problem of designing a set of rings that pass through a central depot and through some transition points and/or customers, and then assigning each nonvisited customer to a visited point or customer. The number of customers visited and assigned to a ring is bounded by an upper limit: the capacity of the ring. The objective is to minimize the total routing cost plus assignment costs. The problem has practical applications in the design of urban optical telecommunication networks. This paper presents and discusses two integer programming formulations for the CmRSP. Valid inequalities are proposed to strengthen the linear programming relaxation and are used as cutting planes in a branch-and-cut approach. The procedure is implemented and tested on a large family of instances, including real-world instances, and the good performance of the proposed approach is demonstrated.

Subject classifications: networks/graphs; optical network design; programming; integer; cutting plane; branch-and-cut algorithm.
History: Received August 2004; revision received August 2005; accepted January 2007.