Modeling and solving the bi-objective minimum diameter-cost spanning tree problem - Archive ouverte HAL Access content directly
Journal Articles Journal of Global Optimization Year : 2014

Modeling and solving the bi-objective minimum diameter-cost spanning tree problem

(1) , (2) , (2)
1
2

Abstract

The bi-objective minimum diameter-cost spanning tree problem (bi-MDCST) seeks spanning trees with minimum total cost and minimum diameter. The bi-objective version generalizes the well-known bounded diameter minimum spanning tree problem. The bi-MDCST is a NP-hard problem and models several practical applications in transportation and network design. We propose a bi-objective multiflow formulation for the problem and effective multi-objective metaheuristics: a multi-objective evolutionary algorithm and a fast nondominated sorting genetic algorithm. Some guidelines on how to optimize the problem whenever a priority order can be established between the two objectives are provided. In addition, we present bi-MDCST polynomial cases and theoretical bounds on the search space. Results are reported for four representative test sets.
Not file

Dates and versions

hal-02291641 , version 1 (19-09-2019)

Identifiers

Cite

Andréa Cynthia Santos, Diego Rocha Lima, Dario José Aloise. Modeling and solving the bi-objective minimum diameter-cost spanning tree problem. Journal of Global Optimization, 2014, 60 (2), pp.195-216. ⟨10.1007/s10898-013-0124-4⟩. ⟨hal-02291641⟩

Collections

CNRS UTT LOSI
17 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More