Modeling and solving the bi-objective minimum diameter-cost spanning tree problem - Université de technologie de Troyes Accéder directement au contenu
Article Dans Une Revue Journal of Global Optimization Année : 2014

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

Résumé

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.
Fichier non déposé

Dates et versions

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

Identifiants

Citer

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 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More