Authors
Andréa Cynthia Santos, Diego Rocha Lima, Dario José Aloise,
Title
Modeling and solving the bi-objective minimum diameter-cost spanning tree problem
In
Journal of Global Optimization
Volume
60
Issue
2
Pages
195–216
Publisher
Springer US
Year
2014
Indexed by
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.
Affiliations
Offprint