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

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

Domains: Computer Science [cs]; Operations Research [cs.RO]

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, 2015, 49 (1), pp.143-160. ⟨10.1051/ro/2014029⟩. ⟨hal-02291634⟩