A new approach for the multiobjective minimum spanning tree

作者：Santos J L^*; Pugliese Luigi Di Puglia; Guerriero Francesca

来源：Computers & Operations Research, 2018, 98: 69-83.

DOI：10.1016/j.cor.2018.05.007

• Multicriteria optimization
• Minimum spanning tree

This paper presents a new algorithm for the multiobjective minimum spanning tree problem that can be used with any number of criteria. It is based on a labelling algorithm for the multiobjective shortest path problem in a transformed network. Some restrictions are added to the paths (minimal paths) in order to obtain a one-to-one correspondence between trees in the original network and minimal paths in the transformed one. The correctness of the algorithm is proved as well as the presentation of a short example. Finally, some computational experiments were reported showing the proposed method outperforms the others in the literature. A deep study is also done about the number of nondominated solutions and a statistical model is presented to predict its variation in the number of nodes and criteria. All the test instances used are available through the web page http://www.mat.uc.pt/(similar to)zeluis/INVESTIG/MOMSTimomst.htm.

• 出版日期2018-10