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

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.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02291641
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Thursday, September 19, 2019 - 9:52:44 AM
Last modification on : Friday, September 20, 2019 - 1:25:19 AM

Identifiers

Collections

Citation

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, Springer Verlag, 2014, 60 (2), pp.195-216. ⟨10.1007/s10898-013-0124-4⟩. ⟨hal-02291641⟩

Share

Metrics

Record views

11