Linear time optimal approaches for reverse obnoxious center location problems on networks

This paper is concerned with a reverse obnoxious (undesirable) center location problem on networks in which the aim is to modify the edge lengths within an associated budget such that a predetermined facility location on the underlying network becomes as far as possible from the existing customer points under the new edge lengths. Exact combinatorial algorithms with linear time complexities are developed for the problem under the weighted rectilinear norm and the weighted Hamming distance. Furthermore, it is shown that the problem with integer decision variables can also be solved in linear time.     

顾客为子树结构的树上反中心选址问题

顾客为子树结构的树上反中心选址问题是在树T上寻找一点(位于顶点处或在边的内部),使得该点与子树结构的顾客之间的最小赋权带加数距离尽可能地大.给出了该问题的一个有效算法,其时间复杂度为O(cn+sum from j=1 to m n_j),其中n_j为各子树T_j的顶点个数,c为不同的子树权重个数,n为树的顶点数.     

Reverse selective obnoxious center location problems on tree graphs

In this paper, we investigate a variant of the reverse obnoxious center location problem on a tree graph \(T=(V,E)\) in which a selective subset of the vertex set V is considered as locations of the existing customers. The aim is to augment or reduce the edge lengths within a given budget with respect to modification bounds until a predetermined undesirable facility location becomes as far as possible from the customer points under the new edge lengths. An \({\mathcal {O}}(|E|^2)\) time combinatorial algorithm is developed for the problem with arbitrary modification costs. For the uniform-cost case, one obtains the improved \({\mathcal {O}}(|E|)\) time complexity. Moreover, optimal solution algorithms with \({\mathcal {O}}(|E|^2)\) and \({\mathcal {O}}(|E|)\) time complexities are proposed for the integer version of the problem with arbitrary and uniform cost coefficients, respectively.     

Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees

This article considers the inverse absolute and the inverse vertex 1-center location problems with uniform cost coefficients on a tree network T with n+1 vertices. The aim is to change (increase or reduce) the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified vertex s becomes an absolute (or a vertex) 1-center under the new edge lengths. First an O(nlogn) time method for solving the height balancing problem with uniform costs is described. In this problem the height of two given rooted trees is equalized by decreasing the height of one tree and increasing the height of the second rooted tree at minimum cost. Using this result a combinatorial O(nlogn) time algorithm is designed for the uniform-cost inverse absolute 1-center location problem on tree T. Finally, the uniform-cost inverse vertex 1-center location problem on T is investigated. It is shown that the problem can be solved in O(nlogn) time if all modified edge lengths remain positive. Dropping this condition, the general model can be solved in O(r_vnlogn) time where the parameter r_v is bounded by ⌈n/2⌉. This corrects an earlier result of Yang and Zhang.     

Robust absolute single machine makespan scheduling-location problem on trees

We investigate a robust single machine scheduling-location problem with uncertainty in edge lengths. Jobs are located at the vertices of a given tree. Given a location for a single machine, the jobs travel to the location and are processed there sequentially. The goal is to find a location of the machine and simultaneously a sequence to minimize the makespan value in the worst-case. We use the concept of gamma-robustness to model uncertainty. Our main result is a polynomial time algorithm.     

A polynomial algorithm for the multicriteria cent-dian location problem

Given a network with several weights per node and several lengths per edge, we address the problem of locating a facility on the network such that the convex combinations of the center and median objective functions are minimized. Since we consider several weights and several lengths, various objective functions should be minimized, and hence we have to solve a multicriteria cent-dian location problem. A polynomial algorithm to characterize the efficient location point set on the network is developed. Furthermore, this model can generalize other problems such as the multicriteria center problem and the multicriteria median problem. Computing time results on random planar networks considering different combinations of weights and lengths are reported, which strengthen the polynomial complexity of the procedure.     

Inverse <Emphasis Type="Italic">p</Emphasis>-median problems with variable edge lengths

The inverse p-median problem with variable edge lengths on graphs is to modify the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified set of p vertices becomes a p-median with respect to the new edge lengths. The problem is shown to be strongly NP{\mathcal{NP}}-hard on general graphs and weakly NP{\mathcal{NP}}-hard on series-parallel graphs. Therefore, the special case on a tree is considered: It is shown that the inverse 2-median problem with variable edge lengths on trees is solvable in polynomial time. For the special case of a star graph we suggest a linear time algorithm.     

Approximating connected facility location with buy-at-bulk edge costs via random sampling

In the connected facility location problem with buy-at-bulk edge costs we are given a set of clients with positive demands and a set of potential facilities with opening costs in an undirected graph with edge lengths obeying the triangle inequality. Moreover, we are given a set of access cable types, each with a cost per unit length and a capacity such that the cost per capacity decreases from small to large cables, and a core cable type of infinite capacity. The task is to open some facilities and to connect them by a Steiner tree using core cables, and to build a forest network using access cables such that the edge capacities suffice to simultaneously route all client demands unsplit to the open facilities. The objective is to minimize the total cost of opening facilities, building the core Steiner tree, and installing the access cables. In this paper, we devise a constant-factor approximation algorithm for this problem based on a random sampling technique.     

Locating an obnoxious facility within a polygonal region

The purpose of this paper is to review some of the many instances in which a location analyst must make a decision as to where an obnoxious facility should be placed. An obnoxious facility is one that can be defined as a facility which has undesirable interactions with existing facilities. Examples include equipment which emit pollutants such as particulates, noise and radiation or warehouses that contain flammable materials. Other obnoxious facilities include machines that are potential sources of hazards to nearby machines and workers. The interaction between the obnoxious facility and each existing facility is reflected through a weighting factor. The feasible region is considered to be continuous in the form of a convex or nonconvex simple polygon. Since the new facility is to be located away from the existing facilities, an appropriate criterion for optimization is the MAXIMIN or the MAXISUM criterion. Algorithms are reviewed for two common metrics under both criteria, i.e. Euclidean and rectilinear.     

A linear time algorithm for inverse obnoxious center location problems on networks

For an inverse obnoxious center location problem, the edge lengths of the underlying network have to be changed within given bounds at minimum total cost such that a predetermined point of the network becomes an obnoxious center location under the new edge lengths. The cost is proportional to the increase or decrease, resp., of the edge length. The total cost is defined as sum of all cost incurred by length changes. For solving this problem on a network with m edges an algorithm with running time ${\mathcal{O}(m)}$ is developed.     

Semi-obnoxious location models: A global optimization approach

In the last decades there has been an increasing interest in environmental topics. This interest has been reflected in modeling the location of obnoxious facilities, as shown by the number of important papers published in this field. However, a very common drawback of the existing literature is that, as soon as environmental aspects are taken into account, economical considerations (e.g. transportation costs) are ignored, leading to models with dubious practical interest. In this paper we take into account both the environmental impact and the transportation costs caused by the location of an obnoxious facility, and propose a solution method the well-known BSSS, with a new bounding scheme which exploits the structure of the problem.     

A Polynomial Time Approximation Scheme for Optimal Product-Requirement Communication Spanning Trees

Given an undirected graph with nonnegative edge lengths and nonnegative vertex weights, the routing requirement of a pair of vertices is assumed to be the product of their weights. The routing cost for a pair of vertices on a given spanning tree is defined as the length of the path between them multiplied by their routing requirement. The optimal product-requirement communication spanning tree is the spanning tree with minimum total routing cost summed over all pairs of vertices. This problem arises in network design and computational biology. For the special case that all vertex weights are identical, it has been shown that the problem is NP-hard and that there is a polynomial time approximation scheme for it. In this paper we show that the generalized problem also admits a polynomial time approximation scheme.     

Arbitrarily large jumps of the Golovach function for trees

The ?-search problem on connected topological graphs is considered. The jumps of the Golovach function are studied for trees. As is known, the Golovach function for trees with at most 27 edges has only unit jumps. In the authors’ earlier papers, examples of trees on which the Golovach function has a jump of size 2 were constructed. In the present paper, it is shown that the jumps of the Golovach function for trees may be arbitrarily large. A sharp bound for the size of jumps is given for a sequence of trees constructed in the paper. A theorem about small perturbations of edge lengths for trees is proved, which asserts an arbitrarily small perturbation of the edge lengths of a given tree (whose Golovach function may be degenerate) may yield a new tree whose Golovach function has only unit jumps.     

A review of extensive facility location in networks

A facility is called ‘extensive’ if, for purposes of location, it is too large in relation to its environment regarding the activities of interest for it to be considered as a point. The literature on location on a network of ordinary and obnoxious extensive facilities is reviewed. Suggestions are made for possible directions of future research.     

Gradient-constrained discounted Steiner trees II: optimally locating a discounted Steiner point

A gradient-constrained discounted Steiner tree is a network interconnecting given set of nodes in Euclidean space where the gradients of the edges are all no more than an upper bound which defines the maximum gradient. In such a tree, the costs are associated with its edges and values are associated with nodes and are discounted over time. In this paper, we study the problem of optimally locating a single Steiner point in the presence of the gradient constraint in a tree so as to maximize the sum of all the discounted cash flows, known as the net present value (NPV). An edge in the tree is labelled as a b edge, or a m edge, or an f edge if the gradient between its endpoints is greater than, or equal to, or less than the maximum gradient respectively. The set of edge labels at a discounted Steiner point is called its labelling. The optimal location of the discounted Steiner point is obtained for the labellings that can occur in a gradient-constrained discounted Steiner tree. In this paper, we propose the gradient-constrained discounted Steiner point algorithm to optimally locate the discounted Steiner point in the presence of a gradient constraint in a network. This algorithm is applied to a case study. This problem occurs in underground mining, where we focus on the optimization of underground mine access to obtain maximum NPV in the presence of a gradient constraint. The gradient constraint defines the navigability conditions for trucks along the underground tunnels.     

双会议服务器选址问题研究

中位选址问题一直是管理学科的研究热点,本文考虑平面点集选址问题中的双会议服务器选址问题,该问题可以看成是2中位问题的衍生问题。令P为平面上包含n个点的点集,双会议服务器选址问题即为寻找由该点集构成的一棵二星树,使得这棵树上所有叶子之间的距离和最小。本文给出求解该问题的关键几何结构和最优解算法设计,并证明所给算法时间复杂性为O(n³logn)。     

The Quintile Share Ratio in location analysis

The inequality measure “Quintile Share Ratio” (QSR or sometimes S80/S20) is the primary income inequality measure in the European Union’s set of indicators on social cohesion. An important reason for its adoption as a leading indicator is its simplicity. The Quintile Share Ratio is “The ratio of total income received by the 20% of the population with the highest income (top quintile) to that received by the 20% of the population with the lowest income (lowest quintile)”. The QSR concept is used in this paper in the context of obnoxious facility location where the inequality is in distances to the obnoxious facility. The single facility location problem minimizing the QSR is investigated. The problem is investigated for continuous uniform demand in an area such as a disk, a rectangle, and a line; when demand is generated at a finite set of demand points; and when the facility can be located anywhere on a network. Optimal solution algorithms are devised for demand originating at a finite set of demand points and at nodes of the network. Computational experiments demonstrate the effectiveness of the algorithms.     

Multicriteria Semi-Obnoxious Network Location Problems (MSNLP) with Sum and Center Objectives

Locating a facility is often modeled as either the maxisum or the minisum problem, reflecting whether the facility is undesirable (obnoxious) or desirable. But many facilities are both desirable and undesirable at the same time, e.g., an airport. This can be modeled as a multicriteria network location problem, where some of the sum-objectives are maximized (push effect) and some of the sum-objectives are minimized (pull effect).We present a polynomial time algorithm for this model along with some basic theoretical results, and generalize the results also to incorporate maximin and minimax objectives. In fact, the method works for any piecewise linear objective functions. Finally, we present some computational results.     

A new algorithm for the undesirable 1-center problem on networks

Recent papers have developed efficient algorithms for the location of an undesirable (obnoxious) 1-center on general networks with n nodes and m edges. Even though the theoretical complexity of these algorithms is fine, the computational time required to get the solution can be diminished using a different model formulation and slightly improving the upper bounds. Thus, we present a new O(mn) algorithm, which is more straightforward and computationally faster than the previous ones. Computing time results comparing the former approaches with the proposed algorithm are supplied.     

最小最大后悔准则下新增设施选址策略研究

基于新增设施选址问题,考虑网络节点权重不确定性,以设施中最大负荷量最小为目标,提出最小最大后悔准则下的新增设施选址问题。在网络节点权重确定时,通过证明将网络图中无穷多个备选点离散为有限个设施候选点,设计了时间复杂度为O(mn²)的多项式算法;在节点权重为区间值时,通过分析最大后悔值对应的最坏情境权重结构,进而确定最大后悔值最小的选址,提出时间复杂度为O(2ⁿm²n³)的求解算法;最后给出数值算例。