Synchronous Optical Network (SONET) in North America and Synchronous Digital Hierarchy (SDH) in Europe and Japan are the current transmission and multiplexing standards for high speed signals within the carrier infrastructure. The typical topology of a SONET network is a collection of rings connecting all the customer sites. We deal with a design problem in which each customer has to be assigned to exactly one ring and these rings have to be connected through a single federal ring. A capacity constraint on each ring is also imposed. The problem is to find a feasible assignment of the customers minimizing the total number of rings used.A Tabu Search method is proposed to solve the problem. The key elements are the use of a variable objective function and the strategic use of two neighborhoods. We have also implemented other techniques such as Path Relinking, eXploring Tabu Search and a Scatter Search. Extensive computational experiments have been done using two sets of benchmark instances.The performances of the proposed algorithms have also been compared with those of three multistart algorithms involving greedy methods previously proposed for the problem, and of the CPLEX solver. The computational experiments show the effectiveness of the proposed Tabu Search.

Solution of the SONET ring assignment problem with capacity constraints / R., Aringhieri; Dell'Amico, Mauro. - STAMPA. - 30(2005), pp. 93-116.

Solution of the SONET ring assignment problem with capacity constraints

DELL'AMICO, Mauro
2005

Abstract

Synchronous Optical Network (SONET) in North America and Synchronous Digital Hierarchy (SDH) in Europe and Japan are the current transmission and multiplexing standards for high speed signals within the carrier infrastructure. The typical topology of a SONET network is a collection of rings connecting all the customer sites. We deal with a design problem in which each customer has to be assigned to exactly one ring and these rings have to be connected through a single federal ring. A capacity constraint on each ring is also imposed. The problem is to find a feasible assignment of the customers minimizing the total number of rings used.A Tabu Search method is proposed to solve the problem. The key elements are the use of a variable objective function and the strategic use of two neighborhoods. We have also implemented other techniques such as Path Relinking, eXploring Tabu Search and a Scatter Search. Extensive computational experiments have been done using two sets of benchmark instances.The performances of the proposed algorithms have also been compared with those of three multistart algorithms involving greedy methods previously proposed for the problem, and of the CPLEX solver. The computational experiments show the effectiveness of the proposed Tabu Search.
Metaheuristic Optimization via Memory and Evolution. Tabu Search and Scatter Search
9781402081347
Springer
STATI UNITI D'AMERICA
Solution of the SONET ring assignment problem with capacity constraints / R., Aringhieri; Dell'Amico, Mauro. - STAMPA. - 30(2005), pp. 93-116.
R., Aringhieri; Dell'Amico, Mauro
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11380/308394
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? ND
social impact