Ordered Weighted Average optimization in Multiobjective Spanning Tree Problem

被引：18

作者：

Fernandez, Elena ^{[1
]}

Pozo, Miguel A. ^{[2
,3
]}

Puerto, Justo ^{[2
,3
]}

Scozzari, Andrea ^{[4
]}

机构：

[1] Univ Politecn Cataluna, Dept Stat & Operat Res, Barcelona Tech, Jordi Girona 1-3, ES-08034 Barcelona, Spain

[2] Univ Seville, IMUS, E-41012 Seville, Spain

[3] Univ Seville, Fac Math, E-41012 Seville, Spain

[4] Univ Niccolo Cusano, Fac Econ, I-00166 Rome, Italy

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2017年 / 260卷 / 03期

关键词：

Combinatorial optimization; Multiobjective optimization; Ordered median; Ordered Weighted Average; Spanning trees; TRAVELING SALESMAN PROBLEM; LOCATION-PROBLEMS; ALGORITHMS; NETWORK; FORMULATIONS; PATH;

D O I：

10.1016/j.ejor.2016.10.016

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

Multiobjective Spanning Tree Problems are studied in this paper. The ordered median objective function is used as an averaging operator to aggregate the vector of objective values of feasible solutions. This leads to the Ordered Weighted Average Spanning Tree Problem, a nonlinear combinatorial optimization problem. Different mixed integer linear programs are proposed, based on the most relevant minimum cost spanning tree models in the literature. These formulations are analyzed and several enhancements presented. Their empirical performance is tested over a set of randomly generated benchmark instances. The results of the computational experiments show that the choice of an appropriate formulation allows to solve larger instances with more objectives than those previously solved in the literature. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：886 / 903

页数：18

共 76 条

[1] On bicriterion minimal spanning trees: An approximation [J].