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 o...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.展开更多
This paper deals with a general variant of the reverse undesirable(obnoxious)center location problem on cycle graphs.Given a‘selective’subset of the vertices of the underlying cycle graph as location of the existin...This paper deals with a general variant of the reverse undesirable(obnoxious)center location problem on cycle graphs.Given a‘selective’subset of the vertices of the underlying cycle graph as location of the existing customers,the task is to modify the edge lengths within a given budget such that the minimum of distances between a predetermined undesirable facility location and the customer points is maximized under the perturbed edge lengths.We develop a combinatorial O(n log n)algorithm for the problem with continuous modifications.For the uniform-cost model,we solve this problem in linear time by an improved algorithm.Furthermore,exact solution methods are proposed for the problem with integer modifications.展开更多
This paper is concerned with the problem of modifying the edge lengths of a weighted extended star network with n vertices by integer amounts at the minimum total cost subject to be given modification bounds so that a...This paper is concerned with the problem of modifying the edge lengths of a weighted extended star network with n vertices by integer amounts at the minimum total cost subject to be given modification bounds so that a set of p prespecified vertices becomes an undesirable p-median location on the perturbed network.We call this problem as the integer inverse undesirable p-median location model.Exact combinatorial algorithms with O(p2n logn)and O(p2(n logn+n log nmax))running times are proposed for solving the problem under the weighted rectilinear and weighted Chebyshev norms,respectively.Furthermore,it is shown that the problem under the weighted sum-type Hamming distance with uniform modification bounds can be solved in O(p-n log n)time.展开更多
文摘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.
基金the Sahand University of Technology under the Ph.D.program contract(No.30/15971).
文摘This paper deals with a general variant of the reverse undesirable(obnoxious)center location problem on cycle graphs.Given a‘selective’subset of the vertices of the underlying cycle graph as location of the existing customers,the task is to modify the edge lengths within a given budget such that the minimum of distances between a predetermined undesirable facility location and the customer points is maximized under the perturbed edge lengths.We develop a combinatorial O(n log n)algorithm for the problem with continuous modifications.For the uniform-cost model,we solve this problem in linear time by an improved algorithm.Furthermore,exact solution methods are proposed for the problem with integer modifications.
文摘This paper is concerned with the problem of modifying the edge lengths of a weighted extended star network with n vertices by integer amounts at the minimum total cost subject to be given modification bounds so that a set of p prespecified vertices becomes an undesirable p-median location on the perturbed network.We call this problem as the integer inverse undesirable p-median location model.Exact combinatorial algorithms with O(p2n logn)and O(p2(n logn+n log nmax))running times are proposed for solving the problem under the weighted rectilinear and weighted Chebyshev norms,respectively.Furthermore,it is shown that the problem under the weighted sum-type Hamming distance with uniform modification bounds can be solved in O(p-n log n)time.
