| The minimum spanning tree(MST)problem is one of the most important problems in network optimization,which it has been widely applied in many fields such as communications,transportations and logistics,etc.As an actual problem,the degree-constrained minimum spanning tree(DCMST)problem was firstly proposed by Narula and Ho in 1980 in the design of electrical circuits.The DCMST problem aimed to find the minimum spanning tree of a deterministic network,subject to constraint on each node.Since all the weights are crisp numbers,we can employ classical algorithm to solve the DCMST problem.However,the weights of DCMST problem are usually in the state of indeterminacy in the real network.In order to model indeterminacy network,random network was first proposed by Frank and Hakimi in 1965 for modeling communication network with random capacities.Knowles and David first investigated the DCMST problem with random weights in 2000.While many networks in real life are uncertain networks without historical data,uncertain network was first proposed by Liu in 2010.This paper first investigated the DCMST problem of uncertain network.Based on different criteria for ranking uncertain variables,three types of DCMST models are proposed here: uncertain expected value DCMST model,uncertain ?-DCMST model and uncertain most chance DCMST model.In our daily life,uncertainty and randomness sometimes coexist in a complex network.That means,some weights have no historical data while others may have enough statistical data to obtain their probability distributions.Recently,Liu in 2014 introduced the concept of uncertain random network.This paper first investigates the DCMST of uncertain random network,and a concept of ideal chance distribution is proposed here.In order to seek the degree-constrained spanning tree which is closest to the ideal chance distribution,an uncertain random programming model is formulated here.Finally,a numerical example is provided to illustrate its effectiveness. |
PDF Full Text Request