Modeling and solving the bi-objective minimum diameter-cost spanning tree problem
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. Copyright Springer Science+Business Media New York 2014
Year of publication: |
2014
|
---|---|
Authors: | Santos, Andréa ; Lima, Diego ; Aloise, Dario |
Published in: |
Journal of Global Optimization. - Springer. - Vol. 60.2014, 2, p. 195-216
|
Publisher: |
Springer |
Subject: | Spanning trees | Multiflow formulation | Multi-objective metaheuristics | Transportation and network design |
Saved in:
Online Resource
Saved in favorites
Similar items by subject
-
It is hard to agree on a spanning tree
Darmann, Andreas, (2014)
-
Relations, models and a memetic approach for three degree-dependent spanning tree problems
Cerrone, C., (2014)
-
Enumeration of spanning trees in planar unclustered networks
Xiao, Yuzhi, (2014)
- More ...
Similar items by person