In this paper, we consider the problem of designing urban opticalnetworks. In particular, given a set of telephone exchanges, we must design a collection of ring-stars, where each ring-star is a cycle composed of a telephone exchange, some customers, some "transition points" used to save routing costs and customers not on the cycle connected to the cycle by a single edge. The ring topology is chosen in many fiber optic communication networks since it allows to prevent the loss of connection due to a single edge or even a single node failure. The objective is to minimize the total cost of the optical network which is mainly due to the excavation costs. We call this problem Multi-Depot Ring-Star Problem (MDRSP) and we formulate it as an optimization problem in Graph Theory. We present lower bounds andheuristic algorithms for the MDRSP. Computational results onrandomly generated instances and real-life datasets are also

Heuristic Algorithms for the Multiple-Depot Ring-Star Problem / R., Baldacci; Dell'Amico, Mauro. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - STAMPA. - 203:1(2010), pp. 270-281. [10.1016/j.ejor.2009.07.026]

Heuristic Algorithms for the Multiple-Depot Ring-Star Problem

DELL'AMICO, Mauro
2010

Abstract

In this paper, we consider the problem of designing urban opticalnetworks. In particular, given a set of telephone exchanges, we must design a collection of ring-stars, where each ring-star is a cycle composed of a telephone exchange, some customers, some "transition points" used to save routing costs and customers not on the cycle connected to the cycle by a single edge. The ring topology is chosen in many fiber optic communication networks since it allows to prevent the loss of connection due to a single edge or even a single node failure. The objective is to minimize the total cost of the optical network which is mainly due to the excavation costs. We call this problem Multi-Depot Ring-Star Problem (MDRSP) and we formulate it as an optimization problem in Graph Theory. We present lower bounds andheuristic algorithms for the MDRSP. Computational results onrandomly generated instances and real-life datasets are also
2010
203
1
270
281
Heuristic Algorithms for the Multiple-Depot Ring-Star Problem / R., Baldacci; Dell'Amico, Mauro. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - STAMPA. - 203:1(2010), pp. 270-281. [10.1016/j.ejor.2009.07.026]
R., Baldacci; Dell'Amico, Mauro
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0377221709005281-main.pdf

Accesso riservato

Tipologia: Versione pubblicata dall'editore
Dimensione 690.93 kB
Formato Adobe PDF
690.93 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
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: https://hdl.handle.net/11380/659439
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 30
  • ???jsp.display-item.citation.isi??? 27
social impact