An exact method for solving the bi-objective Minimum Diameter-Cost Spanning Tree Problem

Ernando Gomes de Sousa 1 Andréa Cynthia Santos 2 Dario José Aloise 1
1 UERN - Universidade do Estado do Rio Grande do Norte
2 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
ICD - Institut Charles Delaunay
Abstract : In this work, we propose a procedure to compute Pareto-optimal fronts for the bi-objective Minimum Diameter-Cost Spanning Tree problem (bi-MDCST). The bi-MDCST aims at finding spanning trees with minimum total cost and minimum diameter. Strategic decision problems for high-speed trains infrastructure, as well as tactical and operational optimization problems for network design and transportation can be modeled as bi-MDCST. The proposed exact procedure makes use of components from the multi-objective exact method Parallel Partitioning Method, and Pareto-optimal fronts have been computed for two benchmark instances from the literature. To the best of our knowledge, there are no works dedicated to providing Pareto-optimal fronts for the bi-MDCST.
Keywords : Spanning trees multi-objective optimization Parallel Partitioning Method
Document type :
Journal articles
Complete list of metadatas
https://hal-utt.archives-ouvertes.fr/hal-02291634
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Thursday, September 19, 2019 - 9:47:19 AM
Last modification on : Friday, September 20, 2019 - 1:25:19 AM

Links full text

istex

Identifiers

Collections

ROSAS | UTT

Citation

Ernando Gomes de Sousa, Andréa Cynthia Santos, Dario José Aloise. An exact method for solving the bi-objective Minimum Diameter-Cost Spanning Tree Problem. RAIRO - Operations Research, EDP Sciences, 2015, 49 (1), pp.143-160. ⟨10.1051/ro/2014029⟩. ⟨hal-02291634⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

9

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD