Degree-constrained minimum spanning tree problem with uncertain edge weights

作者：Gao, Xin; Jia, Lifen^*

来源：Applied Soft Computing, 2017, 56: 580-588.

DOI：10.1016/j.asoc.2016.07.054

• Degree-constrained minimum spanning tree
• Uncertainty theory
• Genetic algorithm

Uncertainty theory has shown great advantages in solving many nondeterministic problems, one of which is the degree-constrained minimum spanning tree (DCMST) problem in uncertain networks. Based on different criteria for ranking uncertain variables, three types of DCMST models are proposed here: uncertain expected value DCMST model, uncertain alpha-DCMST model and uncertain most chance DCMST model. In this paper, we give their uncertainty distributions and fully characterize uncertain expected value DCMST and uncertain alpha-DCMST in uncertain networks. We also discover an equivalence relation between the uncertain alpha-DCMST of an uncertain network and the DCMST of the corresponding deterministic network. Finally, a related genetic algorithm is proposed here to solve the three models, and some numerical examples are provided to illustrate its effectiveness.

• 出版日期2017-7
• 单位华北电力大学