Finding multi-objective supported efficient spanning trees

This article introduces a new algorithm for computing the set of supported non-dominated points in the objective space and all the corresponding efficient solutions in the decision space for the multi-objective spanning tree (MOST) problem. This algorithm is based on the connectedness property of the set of efficient supported solutions and uses a decomposition of the weight set in the weighting space defined for a parametric version of the MOST problem. This decomposition is performed through a space reduction approach until an indifference region for each supported non-dominated point is obtained. An adjacency relation defined in the decision space is used to compute all the supported efficient spanning trees associated to the same non-dominated supported point as well as to define the indifference region of the next points. An in-depth computational analysis of this approach for different types of networks with three objectives is also presented.

Automated summary

This article introduces a new algorithm based on the connectedness property for computing the set of supported non-dominated points and corresponding efficient solutions for the multi-objective spanning tree problem. The algorithm utilizes decomposition of the weight set and adjacency relation in the decision space to determine efficient spanning trees and indifference regions. An in-depth computational analysis is presented for different types of networks with three objectives.