We propose the reliability constrained k-rooted minimum spanning forest, a relevant optimization problem whose aim is to find a k-rooted minimum cost forest that connects given customers to a number of supply vertices, in such a way that a minimum required reliability on each path between a customer and a supply vertex is satisfied and the cost is a minimum. The reliability of an edge is the probability that no failure occurs on that edge, whereas the reliability of a path is the product of the reliabilities of the edges in such path. The problem has relevant applications in the design of networks, in fields such as telecommunications, electricity and transports. For its solution, we propose a mixed integer linear programming model, and an adaptive large neighborhood search metaheuristic which invokes several shaking and local search operators. Extensive computational tests prove that the metaheuristic can provide good quality solutions in very short computing times.

Solution of minimum spanning forest problems with reliability constraints / Ahani, Ida Kalateh; Salari, Majid; Hosseini, Seyed Mahmoud; Iori, Manuel. - In: COMPUTERS & INDUSTRIAL ENGINEERING. - ISSN 0360-8352. - 142:(2020), pp. 1-28. [10.1016/j.cie.2020.106365]

Solution of minimum spanning forest problems with reliability constraints

Iori, Manuel
Membro del Collaboration Group
2020

Abstract

We propose the reliability constrained k-rooted minimum spanning forest, a relevant optimization problem whose aim is to find a k-rooted minimum cost forest that connects given customers to a number of supply vertices, in such a way that a minimum required reliability on each path between a customer and a supply vertex is satisfied and the cost is a minimum. The reliability of an edge is the probability that no failure occurs on that edge, whereas the reliability of a path is the product of the reliabilities of the edges in such path. The problem has relevant applications in the design of networks, in fields such as telecommunications, electricity and transports. For its solution, we propose a mixed integer linear programming model, and an adaptive large neighborhood search metaheuristic which invokes several shaking and local search operators. Extensive computational tests prove that the metaheuristic can provide good quality solutions in very short computing times.
2020
20-feb-2020
142
1
28
Solution of minimum spanning forest problems with reliability constraints / Ahani, Ida Kalateh; Salari, Majid; Hosseini, Seyed Mahmoud; Iori, Manuel. - In: COMPUTERS & INDUSTRIAL ENGINEERING. - ISSN 0360-8352. - 142:(2020), pp. 1-28. [10.1016/j.cie.2020.106365]
Ahani, Ida Kalateh; Salari, Majid; Hosseini, Seyed Mahmoud; Iori, Manuel
File in questo prodotto:
File Dimensione Formato  
submitted-file.pdf

Open access

Descrizione: Versione pre print
Tipologia: Versione originale dell'autore proposta per la pubblicazione
Dimensione 786.75 kB
Formato Adobe PDF
786.75 kB Adobe PDF Visualizza/Apri
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/1196312
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 3
social impact