摘要
In this paper,we first consider the classical p-median location problem on a network in which the vertex weights and the distances between vertices are uncertain variables.The uncertainty distribution of the optimal objective value of the p-median problem is given and the concepts of the α-p-median,the most p-median and the expected p-median are introduced.Then,it is shown that the uncertain p-median problem is NP-hard on general networks.However,if the underlying network is a tree,an efficient algorithm for the uncertain 1-median problem with linear time complexity is proposed.Finally,we investigate the inverse 1-median problem on a tree with uncertain vertex weights and present a programming model for the problem.Then,it is shown that the proposed model can be reformulated into a deterministic programming model.
