The multicriteria p-facility median location problem on networks

In this paper we discuss the multicriteria p-facility median location problem on networks with positive and negative weights. We assume that the demand is located at the nodes and can be different for each criterion under consideration. The goal is to obtain the set of Pareto-optimal locations in the graph and the corresponding set of non-dominated objective values. To that end, we first characterize the linearity domains of the distance functions on the graph and compute the image of each linearity domain in the objective space. The lower envelope of a transformation of all these images then gives us the set of all non-dominated points in the objective space and its preimage corresponds to the set of all Pareto-optimal solutions on the graph. For the bicriteria 2-facility case we present a low order polynomial time algorithm. Also for the general case we propose an efficient algorithm, which is polynomial if the number of facilities and criteria is fixed.     

A D.C. biobjective location model

In this paper we address the biobjective problem of locating a semiobnoxious facility, that must provide service to a given set of demand points and, at the same time, has some negative effect on given regions in the plane. In the model considered, the location of the new facility is selected in such a way that it gives answer to these contradicting aims: minimize the service cost (given by a quite general function of the distances to the demand points) and maximize the distance to the nearest affected region, in order to reduce the negative impact. Instead of addressing the problem following the traditional trend in the literature (i.e., by aggregation of the two objectives into a single one), we will focus our attention in the construction of a finite -dominating set, that is, a finite feasible subset that approximates the Pareto-optimal outcome for the biobjective problem. This approach involves the resolution of univariate d.c. optimization problems, for each of which we show that a d.c. decomposition of its objective can be obtained, allowing us to use standard d.c. optimization techniques.     

A Mini-Max Location Problem with Demand Points Arbitrarily Distributed in a Compact Connected Space

Consider a finite set of demand points which exist anywhere on the boundary of a rectangle contained in the two-dimensional Euclidean space. This paper considers the problem of finding an optimal location (on the boundary of the rectangle) which minimizes the maximum average Euclidean distance to the demand points. The method presented is independent of the number of demand points.     

Spherical minimax location problem using the Euclidean norm: Formulation and optimization

The minimax spherical location problem is formulated in the Cartesian coordinate system using the Euclidean norm, instead of the spherical coordinate system using spherical arc distance measures. It is shown that minimizing the maximum of the spherical arc distances between the facility point and the demand points on a sphere is equivalent to minimizing the maximum of the corresponding Euclidean distances. The problem formulation in this manner helps to reduce Karush-Kuhn-Tucker necessary optimality conditions into the form of a set of coupled nonlinear equations, which is solved numerically by using a method of factored secant update with a finite difference approximation to the Jacobian. For a special case when the set of demand points is on a hemisphere and one or more point-antipodal point pair(s) are included in the demand points, a simplified approach gives a minimax point in a closed form.     

The probabilistic 1-maximal covering problem on a network with discrete demand weights

We discuss the probabilistic 1-maximal covering problem on a network with uncertain demand. A single facility is to be located on the network. The demand originating from a node is considered covered if the shortest distance from the node to the facility does not exceed a given service distance. It is assumed that demand weights are independent discrete random variables. The objective of the problem is to find a location for the facility so as to maximize the probability that the total covered demand is greater than or equal to a pre-selected threshold value. We show that the problem is NP-hard and that an optimal solution exists in a finite set of dominant points. We develop an exact algorithm and a normal approximation solution procedure. Computational experiment is performed to evaluate their performance.     

Local search algorithm for universal facility location problem with linear penalties

The universal facility location problem generalizes several classical facility location problems, such as the uncapacitated facility location problem and the capacitated location problem (both hard and soft capacities). In the universal facility location problem, we are given a set of demand points and a set of facilities. We wish to assign the demands to facilities such that the total service as well as facility cost is minimized. The service cost is proportional to the distance that each unit of the demand has to travel to its assigned facility. The open cost of facility i depends on the amount z of demand assigned to i and is given by a cost function \(f_i(z)\). In this work, we extend the universal facility location problem to include linear penalties, where we pay certain penalty cost whenever we refuse serving some demand points. As our main contribution, we present a (\(7.88+\epsilon \))-approximation local search algorithm for this problem.     

Minmax-distance approximation and separation problems: geometrical properties

A center hyperplane in the d-dimensional space minimizes the maximum of its distances from a finite set of points A with respect to possibly different gauges. In this note it is shown that a center hyperplane exists which is at (equal) maximum distance from at least d?+?1 points of A. Moreover the projections of the points among these which lie above the center hyperplane cannot be separated by another hyperplane from the projections of those that are below it. When all gauges involved are smooth, all center hyperplanes satisfy these properties. This geometric property allows us to improve and generalize previously existing results, which were only known for the case in which all distances are measured using a common norm. The results also extend to the constrained case where for some points it is prespecified on which side of the hyperplane (above, below or on) they must lie. In this case the number of points lying on the hyperplane plus those at maximum distance is at least d?+?1. It follows that solving such global optimization problems reduces to inspecting a finite set of candidate solutions. Extensions of these results to a separation problem are outlined.     

A maximumb-matching problem arising from median location models with applications to the roommates problem

We consider maximumb-matching problems where the nodes of the graph represent points in a metric space, and the weight of an edge is the distance between the respective pair of points. We show that if the space is either the rectilinear plane, or the metric space induced by a tree network, then theb-matching problem is the dual of the (single) median location problem with respect to the given set of points. This result does not hold for the Euclidean plane. However, we show that in this case theb-matching problem is the dual of a median location problem with respect to the given set of points, in some extended metric space. We then extend this latter result to any geodesic metric in the plane. The above results imply that the respective fractionalb-matching problems have integer optimal solutions. We use these duality results to prove the nonemptiness of the core of a cooperative game defined on the roommate problem corresponding to the above matching model. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.     

Locating a minisum annulus: a new partial coverage distance model

The problem is to find the best location in the plane of a minisum annulus with fixed width using a partial coverage distance model. Using the concept of partial coverage distance, those demand points within the area of the annulus are served at no cost, while for ‘uncovered’ demand points there will be additional costs proportional to their distances to the annulus. The objective of the problem is to locate the annulus such that the sum of distances from the uncovered demand points to the annulus (covering area) is minimized. The distance is measured by the Euclidean norm. We discuss the case where the radius of the inner circle of the annulus is variable, and prove that at least two demand points must be on the boundary of any optimal annulus. An algorithm to solve the problem is derived based on this result.     

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.     

Some Properties for the Euclidean Distance Matrix and Positive Semidefinite Matrix Completion Problems

The Euclidean distance matrix (EDM) completion problem and the positive semidefinite (PSD) matrix completion problem are considered in this paper. Approaches to determine the location of a point in a linear manifold are studied, which are based on a referential coordinate set and a distance vector whose components indicate the distances from the point to other points in the set. For a given referential coordinate set and a corresponding distance vector, sufficient and necessary conditions are presented for the existence of such a point that the distance vector can be realized. The location of the point (if it exists) given by the approaches in a linear manifold is independent of the coordinate system, and is only related to the referential coordinate set and the corresponding distance vector. An interesting phenomenon about the complexity of the EDM completion problem is described. Some properties about the uniqueness and the rigidity of the conformation for solutions to the EDM and PSD completion problems are presented.     

Fractal pattern growth simulation in electrodeposition and study of the shifting of center of mass

We presented simulation of fractal pattern in electrodeposition (Diffusion limited aggregation) using concept of off lattice walk.It is seen that the growth patterns are based on a parameter called ‘bias’. This parameter ‘bias’ controls the growth of patterns similar to that of electric field in electrodeposition technique. In present study the fractal patterns are grown for different values of ‘bias’. Dendritic patterns grown at lower value of ‘bias’ comprises open structure and show limited branching. As the bias is increased the growth tends to be dense and show more crowded branching. Box counting was implemented to calculate fractal dimension. The structural and textural complexities and are compared with the experimental observations.It was also noted that in the evolution of DLA patterns, the center of mass of the growth is shifted slightly. We tracked the position of the center of mass of simulated electro deposits under different electric field conditions. The center of mass exhibit random walk like patterns and it wanders around the origin or the starting point of the growth.     

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

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

Stop location design in public transportation networks: covering and accessibility objectives

We consider the location of new stops along the edges of an existing public transportation network. Examples of StopLoc include the location of bus stops along some given bus routes or of railway stations along the tracks in a railway system. In order to evaluate the decision assume that potential customers in given demand facilities are known. Two objectives are proposed. In the first one, we minimize the number of stations such that any of the demand facilities can reach a closest station within a given distance of r. In the second objective, we fix the number of new stations and minimize the sum of the distances between demand facilities and stations. The resulting two problems CovStopLoc and AccessStopLoc are solved by a reduction to a classical set covering and a restricted location problem, respectively. We implement the general ideas in two different environments, the plane, where demand facilities are represented by coordinates, and in networks, where they are nodes of a graph.     

Centers and shore points of a dendroid

A bottleneck in a dendroid is a continuum that intersects every arc connecting two nonempty open sets. Every dendroid contains a point called a center which is contained in arbitrarily small bottlenecks. A subset A of a dendroid is a shore set if for every ε>0 there is a continuum in D?A with Hausdorff distance from D less than ε. If a shore set has only one point it is called a shore point. This paper explores the relationship between center points and shore points in a dendroid. We show that if a dendroid contains a strong center, then any finite union of the arc components of the set of shore points is a shore set.     

带惩罚的相同容量k-均值问题的局部搜索算法

经典$k$-均值问题是一类应用广泛的聚类问题,它是指给定$\mathbb{R}^d$中观测点集合$D$和整数$k$,目的是在空间中寻找$k$个点作为中心集合$S$,使得集合$D$中的每个观测点到$S$中离它最近的中心的距离平方求和最小。这是个NP-难问题。经典$k$-均值问题有很多推广,本文研究的带惩罚的相同容量$k$-均值问题就是其中之一。与经典$k$-均值问题相比,惩罚性质是指每个观测点都给定惩罚费用,当某个观测点到最近中心的距离大于惩罚费用时,其对目标函数的贡献就用该观测点的惩罚费用来代替最近的距离的平方,相同容量约束要求每个中心至多连接$U$个观测点。针对这种问题,我们设计了局部搜索算法,该算法在至多选取$（3+\alpha）k$个中心的情况下,可以达到$\beta$-近似,其中,参数$\alpha>34$,$\beta>\frac{\alpha+34}{\alpha-34}$。     

带惩罚的相同容量k-均值问题的局部搜索算法

经典$k$-均值问题是一类应用广泛的聚类问题,它是指给定$\mathbb{R}^d$中观测点集合$D$和整数$k$,目的是在空间中寻找$k$个点作为中心集合$S$,使得集合$D$中的每个观测点到$S$中离它最近的中心的距离平方求和最小。这是个NP-难问题。经典$k$-均值问题有很多推广,本文研究的带惩罚的相同容量$k$-均值问题就是其中之一。与经典$k$-均值问题相比,惩罚性质是指每个观测点都给定惩罚费用,当某个观测点到最近中心的距离大于惩罚费用时,其对目标函数的贡献就用该观测点的惩罚费用来代替最近的距离的平方,相同容量约束要求每个中心至多连接$U$个观测点。针对这种问题,我们设计了局部搜索算法,该算法在至多选取$（3+\alpha）k$个中心的情况下,可以达到$\beta$-近似,其中,参数$\alpha>34$,$\beta>\frac{\alpha+34}{\alpha-34}$。     

Biobjective center – balance graph location model *

In the paper, a new algorithm for finding the absolute center of the graph is proposed. Later on problem of the absolute balance point of the graph is investigated the objective function of which is defined as the difference in the distance from the located facility to the farthest and the nearest demand point. An algorithm for finding it is presented By following the balance criterion it may happen, that the balance point is located too far from the demand points. Conversely, if we are interested not only in the distance to the farthest demand point, but (what is more realistic) also in the structure of the distances, a criterion of balance is appropriate. Consequently, we investigate the center balance constrained model that simultaneously used center and balance criteria. By considering the center and the balance objective in a multiobjective framework, efficient solutions are generated by minimizing former objective such that latter satisfies an upperbound     

Confined location of facilities on a graph

Location problems on a graph are usually classified according to the form that the set of located facilities takes, the specification of the demand location set and the objective function of distances between facilities and demand points. In this paper we suppose that a given number of located facilities is confined to the same number of edges. We consider eight types of optimality criteria: minirnizing(or maximizing) the minimum (or maximum) distance from a demand to its nearest (farthest) facility.     

Optimizing pricing and location decisions for competitive service facilities charging uniform price

In this paper, we present the problem of optimizing the location and pricing for a set of new service facilities entering a competitive marketplace. We assume that the new facilities must charge the same (uniform) price and the objective is to optimize the overall profit for the new facilities. Demand for service is assumed to be concentrated at discrete demand points (customer markets); customers in each market patronize the facility providing the highest utility. Customer demand function is assumed to be elastic; the demand is affected by the price, facility attractiveness, and the travel cost for the highest-utility facility. We provide both structural and algorithmic results, as well as some managerial insights for this problem. We show that the optimal price can be selected from a certain finite set of values that can be computed in advance; this fact is used to develop an efficient mathematical programming formulation for our model.